大 O 符号

几乎所有编码难题都有多种解决方法。虽然所有方法都能解决问题，但可以根据性能和效率对它们进行排序。工程师们使用的一个标准系统是大 O 符号。

因此，与其计算根据计算能力而变化的秒数，不如通过计算计算机在算法中必须执行的简单操作的数量来获得一致且标准化的结果。计算机执行算法所需的时间与其必须执行的操作数量成正比。因此，操作数量越多，执行所需的时间就越长。

现在我们已经建立了分析算法运行时间的标准，让我们来计算一下解决方案中简单操作的数量

解决方案 1

1. function addUpto(n) {
2.   return n * (n + 1) / 2;
3. }

解决方案 1 总共包含三 (3) 个简单操作。

一次乘法n * ...
一次加法n + 1和
一次除法。解决方案 1... / 2中的运算次数不会随着输入 ( n ) 的幅值增加或减少而改变。无论n有多大或多小，运算次数始终为 3。

解决方案 2

1. function addUpto(n) {
2.   let total = 0;
3.   for (let i = 1; i <= n; i++) {
4.     total += i;
5.   }
6.   return total;
8. }

在溶液 2中

第 2 行显示 1 个变量赋值let total = 0;
第 3 行显示：
- 1 变量赋值let i = 1;，
- n次比较i <= n;，
- n 次加法和n 次变量赋值i++。
第 4 行显示n 次加法和n次变量赋值。

它还使用了一个运行n次的循环。因此，如果n为 5，循环将运行五次。但是，根据计算方式的不同，操作次数可能低至2n，也可能高达5n + 2。因此，无论精度如何，操作次数都大致与n 成比例增长。

因此，与解决方案 1不同，解决方案 2中计算操作次数要复杂得多。大 O 符号不一定关心精度，只关心总体趋势。

基于上述内容，“大 O 符号的时间复杂度是衡量算法的运行时间如何随着输入的增长而增长的标准。”

通过大 O 符号对算法的运行时间/时间复杂度进行分类时可用的各种术语包括以下内容。

常数 O(1)

时间复杂度为常数的算法，其运行时间不会因输入（ n ）的增减而受到显著影响。随着输入（n）值的增长，算法的运行时间基本保持不变。

线性 O(n)

当算法的运行时间与其输入（ n）成比例时，该算法被描述为具有线性时间复杂度。

二次 O(n^2)

具有二次时间复杂度的算法，其运行时间的缩放比例大约为其输入（n ）的平方。因此，随着n值的增加，算法的运行时间也会增加n^2。

解决方案 1

1. function addUpto(n) {
2.   return n * (n + 1) / 2;
3. }

因此，解决方案 1的大 O是O(1)（读作 O of 1 ）。这意味着随着n 的增加，计算机需要执行的简单操作的数量保持不变。

解决方案 2

1. function addUpto(n) {
2.   let total = 0;
3.   for (let i = 1; i <= n; i++) {
4.     total += i;
5.   }
6.   return total;
8. }

解决方案 2具有较大的 O O(n)（读作 O of n）。这意味着操作次数受限于其输入（n）的倍数。

空间复杂度

空间复杂度通常与运行给定算法所需的内存量有关。

辅助空间复杂度：不考虑输入占用的空间，算法所需的空间/内存。

就本博文的范围而言，空间复杂度是指辅助空间复杂度。

思考空间复杂度时的有用技巧

大多数原语（布尔值、数字、未定义、空值）都是常量空间O(1)。
字符串需要O(n)空间（其中n是字符串的长度）。
引用类型通常是O(n)，其中n是数组的长度，或者在对象的情况下是键的数量。

1. function sum(arr) {
2.   let total = 0;
3.   for (let i = 0; i < arr.length; i++) {
4.      total += arr[i];
5.   }
6.   return total;
7.  }

上述函数将给定数组的所有数值元素相加，并返回总数。
由于我们只关心函数/算法所需的内存/空间，因此我们将忽略提供给函数的数组的长度。因此，我们唯一关心的占用空间的元素在第 2 行和第 3 行。

在第 2 行和第 3 行，无论提供给函数/算法的数组的大小/长度如何，它都会占用一个数字 (0) 的空间。第 2 行 => let total = 0。第 3 行 =>let i = 0

因此，和函数相对于辅助空间复杂度的大O是O(1)。

1. function double(arr) {
2.   let newArr = [];
3.   for (let i = 0; i < arr.length; i++) {
4.      newArr.push(2 * arr[i]);
5.   }
6.   return newArr;
7.  }

函数double接受一个数字数组并返回一个新数组，其中输入数组的每个元素都加倍。

需要注意的一点是，实例化了一个空数组，并且根据输入数组的长度，实例化数组所需的内存在第 4 行按比例增加。因此double函数的空间复杂度为O(n)。

对数简介

虽然一些常见的算法可以归类为常数O(1)、线性O(n)和二次O(n^2)空间和时间复杂度，但仍有许多算法无法用上述方法充分描述。这些算法涉及更复杂的数学表达式，例如对数。

对数是指数的逆。正如除法和乘法是一对，指数和对数也是一对。

O(log n)对数空间和时间复杂度用和表示O(nlog n)

结论

总而言之，这里有一些关于大 O 符号需要记住的事情。

为了分析算法的性能，我们使用大 O 符号
大 O 符号可以让我们从高层次上理解算法的时间或空间复杂度。
Big O 符号不一定关心精度，只关心一般趋势（线性、二次或常数）
时间或空间复杂度（以 Big O 衡量）仅取决于算法，而不取决于运行算法所使用的硬件。

封面图片由Jeremy Perkins 在 Unsplash 上提供

文章来源：https://dev.to/adafia/big-o-notation-3oi6

大 O 符号

大 O 符号

目录

什么是大 O 符号？

好处

时间和空间复杂度

问题 1

解决方案 1

解决方案 2

讨论

时间复杂度

让我们来回答第一个问题“更好就意味着更快吗？”

解决方案 1

解决方案 2

常数 O(1)

线性 O(n)

二次 O(n^2)

解决方案 1

解决方案 2

空间复杂度

思考空间复杂度时的有用技巧

对数简介

结论