什么是 O(💕)？学习大 O 二次时间复杂度

还有什么比大O符号更吓人的计算机科学主题吗？别被它的名字吓到，大O符号其实没那么复杂。它非常容易理解，你不需要是数学天才也能掌握。在本教程中，你将通过JavaScript示例学习大O符号的基础知识，以及二次时间复杂度的概念。

这是关于大O符号系列文章的第四篇。如果您想及时了解最新动态，请订阅我的每周新闻简报《解决方案》。

大O符号解决了什么问题？

• 大 O 符号可以帮助我们回答“它是否可扩展？”这个问题。
• Big O 表示法为我们提供了一种与其他开发人员（以及数学家！）讨论性能的共同语言。

快速回顾

在本系列的前两篇文章中，我们探讨了常数时间复杂度和线性时间复杂度，即 O(1) 和 O(n)。如果您是第一次阅读本系列文章，建议您先阅读《什么是大 O 表示法？》

什么是大O？

大O符号是一种用于衡量算法增长速率的系统。它从数学角度描述了算法在时间和空间上的复杂度。我们不以秒（或分钟！）来衡量算法的速度，而是衡量完成算法所需的运算次数。

O 是“Order of”（阶数）的缩写。因此，如果我们讨论的算法的阶数为 O(n² ^)，我们就说它的阶数或增长率是 n² ^，即二次复杂度。

Big O 是如何运作的？

大O符号衡量的是最坏情况。

为什么？

因为我们不知道我们不知道的事情。

我们需要知道我们的算法究竟表现得有多差，这样我们才能评估其他解决方案。

最坏情况也称为“上限”。我们所说的“上限”是指算法执行的最大操作次数。

还记得这张桌子吗？

它按增长率从快到慢列出了常见订单。

我们在“大O线性时间复杂度”一节中学习了O(n)，即线性时间复杂度。我们暂时跳过O(log n)，即对数时间复杂度。在学习了O(n² ^)，即二次时间复杂度之后，理解O(log n)会更容易。

在深入探讨 O(n ^{2) 之前，}让我们先回顾一下 O(1) 和 O(n)，即常数和线性时间复杂度。

O(1) 与 O(n)：常数时间复杂度与线性时间复杂度

以下函数求一组数字的总和。

const nums = [1,2,3,4,5,6,7,8,9,10];

const sumHarder = arr => {
   let sum = 0;
   for (let i = 0; i < arr.length; i++) {
       sum += arr[i];
   }
   return sum;
}

const result = sumHarder(nums);

什么是大O？

在）。

为什么？

它的增长率与输入成正比。随着输入的增长，运算次数也会线性增长。我们的函数对于每个输入都需要执行相同次数的运算，因此它的时间复杂度是线性的，即 O(n)。

我们还能做得更好吗？

我们在《如何计算 1 到 n 的整数之和》一书中学到了小卡尔·弗里德里希·高斯发现的一个小技巧：

n ( n + 1 ) / 2

如果我们把这个方程式翻译成 JavaScript：

const sumSmarter = arr => arr.length * (arr.length + 1) / 2;

现在我们的函数阶数是多少？

O(1)，即常数时间。

为什么？

无论输入数据的大小如何，我们的算法都会执行相同次数（或恒定次数）的操作。

数学时间🧮🕝

“二次”是一个用来描述平方或2次方的华丽形容词。

它源自拉丁语quadrus，意思是，你猜对了，正方形。

数学中的平方是什么？

一个数的平方就是这个数乘以它自身的结果。

二的二次方，即 2² 2^2，等于 2³ 2 * 2，即 4。

3 的 2 次方，即 3² 3^2，等于 3³ 3 * 3，即 9。

你早就知道了。

如果我们绘制二次方程的图像，我们会得到一条抛物线：

我们只关心抛物线的右侧（或正值），因为我们无法回到过去。

然而。

说到时间，数学时间结束了。

回到大O。

O(n² ^)：二次时间复杂度

如果一个算法的时间复杂度为 O(n)，即线性时间复杂度，那么它执行的操作次数与输入成正比。

如果一个算法的时间复杂度是 O(n² ^{) 呢？}

🔑 它执行的操作次数与输入的平方成正比。

这个例子中发生了什么？

const fruit = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];

const matcher = array => {
   for (let i = 0; i < array.length; i++){
       for (let j = 0; j < array.length; j++){
           if (i !==j && array[i] === array[j]){
               return `Match found at ${i} and ${j}`;
           }
       }
   }
   return 'No matches found 😞'; 
}

我们声明一个水果数组并将其传递给matcher()函数。matcher()函数随后遍历该数组。对于数组中的每个元素，我们再次遍历数组。如果数组索引不同，但索引处的元素相同，则返回匹配水果的位置。如果没有找到匹配项，则返回失望。

执行了多少次手术？

我们的外层循环执行n 次迭代。我们的内层循环也执行n 次迭代。但是，内层循环每次迭代都对应着外层循环的n次迭代。

当i值为 0 时，我们迭代j10 次。

当i为 1 时，我们迭代j10 次。

ETC。

而不是 O(n) 或 O(n + n)，而是 O(n * n) 或 O(n ^2)。

目前，我们已经熟悉以下几种时间复杂度：O(1)、O(n) 和 O(n² ^)。为了便于比较，下表列出了它们随输入数量变化的增长情况：

正如我们所看到的，O(n ²⁾本身就不是很好，而且随着输入规模的增加，情况只会变得更糟。

还记得这张图表吗？

正如我们所看到的，O(n ²⁾非常糟糕。

但这还不是最糟糕的！

计算复杂度

以下是在计算大 O 二次时间复杂度时常见的陷阱和误区。

删除非主导术语

在这个人为设计的例子中，发生了什么？

const summer = (num, t = false) => {
   let sum = 0;

   if (t === 'quadratic'){
       for (i = 0; i <= num; i++){
           for (j = 0; j < num; j++){
               sum += j;
           }
       }
   } else if (t === 'linear') {
       for (i = 0; i <= num; i++){
           sum += i;
       }
   } else {
       return num * (num + 1) / 2;
   }
   return sum;
}

如果满足第一个条件，我们就运行嵌套迭代，函数的阶数为 O(n ^2)。

如果满足第二个条件，我们就运行一次迭代，函数的阶数为 O(n)。

如果这两个条件都不满足，则我们的函数是 O(1)。

我们的函数的实际阶数是多少？

我们可以将其计算为 O(n ² + n + 1)。

我们为什么不这样做呢？

在使用大 O 表示法来衡量算法的增长率时，我们真正想知道的是什么？

我们想知道最坏的情况是什么。

这里是n^2。

这是主要术语。

我们之前学过，要舍弃常数项。

我们还舍弃了n非主导项，因为它没有提供任何有意义的额外信息。是否n影响算法的增长率无关紧要。无论有没有它，我们的算法仍然是二次函数。

我们真正想知道的是函数的阶数，而不是它的具体实现细节。所以上面的例子是 O(n² ^)。

带偏移量的迭代

如果我们对算法进行一点小的优化会发生什么matcher()？

const fruit = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];

const matcher = array => {
   for (let i = 0; i < array.length; i++){
       for (let j = i + 1; j < array.length; j++){
           if (array[i] === array[j]){
               return `Match found at ${i} and ${j}`;
           }
       }
   }
   return 'No matches found 😞'; 
}

如果我们正在检查是否匹配，我们知道它永远不会出现在数组的同一索引位置。

我们可以用 初始化内循环let j = i + 1，这样内循环的迭代器就始终比外循环的迭代器领先一个元素。

这样我们就可以删除语句i !== j中的操作if。

问题在于：内循环j将运行多少次？

我们来列个表格吧！

假设我们有一个包含五个元素的数组。当外层循环中的迭代器i的值为 0 时，内层循环中的迭代器j的值为i加 1。随着i值的增加， j执行的迭代次数相应减少。

如果数组长度是可变的，或者未知，我们该如何计算内层循环的迭代次数？

第一次执行外层循环时，执行内层循环n - 1。

第二次外层循环运行时，内层循环也会运行n - 2。

第三次，n - 3。

嘿！这看起来有点眼熟。我们以前在哪里见过这种图案？

这与计算从 1 到 n 的连续整数之和非常相似。

我们可以用以下公式计算：

n * ( n - 1 ) / 2

我们可以用数学魔法来简化它。

虽然它不是严格意义上的平方，^但请记住，在大O表示法中，我们不关心细节。因此，我们忽略常数，并将各项相乘，结果为n²。

让我们把它形象化：想象一个函数，它记录i和j的值对，输出如下：

[
      [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 4 ] ],
                [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ] ],
                          [ [ 2, 3 ], [ 2, 4 ] ],
                                    [ [ 3, 4 ] ]
]

看出规律了吗？

它是半个方阵。

我们可以这样写：

( n * n ) / 2

如果去掉常数（除数），它就只是n ²。

在《破解编程面试》一书中，盖尔·拉克曼·麦克道尔引导我们思考代码的含义。

这意味着什么？

我们的函数是比较i和j这两对数据。

要比较的对的总数为i * j，或者，因为我们使用的是相同的输入，所以为n * n，即n ²。

但是！我们只比较j大于i 的配对，这大约是配对总数的一半。

我们永远不会比较j小于i 的数对。

我们同样可以这样写：

( n * n ) / 2

再说一遍，如果我们忽略细节，那就是 O(n ^2)。

两个输入

如果我们的函数接受两个长度不一、不确定的输入，该怎么办？

const matcher = (arr1, arr2) => {
   for (let i = 0; i < arr1.length; i++){
       for (let j = 0; j < arr2.length; j++){
           if (arr1[i] === arr2[j]){
               return `Match found at arr1[${i}] and arr2[${j}]`;
           }
       }
   }
   return 'No matches found 😞'; 
}

这是 O(n² ^{) 吗？}

仅当两个数组的长度相等，即n 时。

因为我们不知道我们不知道什么，所以我们需要分别对待每个值。

所以这是O(n * m)。

在数学中，这被称为多线性函数。下次技术面试时不妨试试这个！

大O二次时间复杂度

O(n² ⁾是否具有可扩展性？

我们还可以做得更糟。

我们肯定可以做得更好。

我们将在下一个教程中看到具体方法。

在本教程中，你学习了大 O 符号表示的二次时间复杂度的基础知识，并学习了 JavaScript 中的示例。敬请期待本系列教程的第四部分，我们将探讨 O(log n)，即对数时间复杂度。如果你想随时了解最新动态，请订阅我的每周新闻简报《解决方案》。