数据结构 - 复杂度基本概念 - 《数据结构与算法》

什么是大O
时间复杂度
空间复杂度
参考

什么是大O

先理解一段枯燥的定义。

若存在常量k和n0,使算法A在解决规模n>=n0的问题时，需要的问题单元不大于k*f(n),则算法A为f(n)阶，表示为O(f(n))。

O(f(n))定义中的条件n >=n 0正式阐明了问题规模足够大的概念，一般地，有很多k和n值可以满足这个定义。大O表示法的几个数学属性有助于简化算法分析。在讨论这些属性是要记住，O(f(n))意为f(n)阶，O并不是一个函数。_
上面两段话中我们提炼到的信息有：

大O表示法正确的读法是xxx阶，比如，A算法的事件复杂度是O(n)，就应该说A算法的时间复杂度是n阶；
大O表示法括号中的东西其实是一个函数，大O表示法整体的意思就是，这个算法的复杂程度和该函数等价。基于这个理解，再看下上面定义中所谓 “ 存在常量k和n0，使算法A在解决规模n>=n0的问题时，需要的问题单元不大于k*f(n) ” 这句话无非就是告诉你，某函数的复杂度和函数的常量系数无关，也就是说，3n、5n和n或者100n、kn，只要k是常量，都是O(n)。

这就是所谓大O表示法，这个东西用“最坏情况下就是这样（和f(n)一样）”的思想来测评问题。_

时间复杂度

简单说，这是对于代码运行时长的定性描述。
事件复杂度不是说计算的快慢，而是说随着问题规模的增大，所消耗时间的增速的快慢。问题规模可以简单理解为输入数据集合的个数吧。
一个生动的例子：

“算法的运行时间以不同的速度增加”这句话应该如何理解呢？下面我们通过来看看这句话到底想表达什么。小明现在需要编写一个查找算法，这个算法服务于学校图书馆，目的是帮助童鞋们能够快速的找到自己需要的书籍所在位置。假设小明现在只会“二分查找”和“简单查找”。一方面，二分查找的速度很快，小明必须在 10 秒钟内找到书籍所在位置，否则童鞋们没有更多耐心等待。另一方面，简单查找算法编写起来更容易，因此出现 bug 的可能性更小。为了检验这两种算法的耗时，小明决定计算两种算法在列表包含 100 个元素的情况下需要的时间。假设检查一个元素需要 1 毫秒。使用简单查找时，小明必须检查 100 个元素，因此需要 100 毫秒才能查找完毕。而使用二分查找时，只需检查 7 个元素（log2 100大约为7），因此需要 7 毫秒就能查找完毕。然而，实际要查找的列表可能包含 10 亿个元素，在这种情况下，简单查找需要多长时间呢？二分查找又需要多长时间呢？小明使用包含 10 亿个元素的列表运行二分查找，运行时间为 30 毫秒（log2 1 000 000 000大约为30）。他心里想，二分查找的速度大约为简单查找的 15 倍，因为列表包含 100 个元素时，简单查找需要 100 毫秒，而二分查找需要 7 毫秒。因此，列表包含 10 亿个元素时，简单查找需要 30 × 15 = 450 毫秒，完全符合在 10 秒内查找完毕的要求。小明决定使用简单查找。这是正确的选择吗？不是。实际上，小明错了，而且错得离谱。列表包含 10 亿个元素时，简单查找需要 10 亿毫秒，相当于 11 天！为什么会这样呢？因为二分查找和简单查找的运行时间的增速不同。

上面也说到过，大O表示法指出了最糟糕情况下的运行时间，下面是一幅常见的各种时间复杂度的增长图，纵坐标表示复杂程度，横坐标表示问题空间大小。
这幅图要记住 O(log n) 最优秀，优于O(n)，O(n)优于O(n log n), O(n log n)优于O( n)
O(log n) < O(n) < O(n log n) < O( n)

举几个例子，看下对应代码：

O(1)时间复杂度

const cjj = 'ze';
const lqq = cjj + 'mayBeOne2b';

O(n)时间复杂度

for (let i = 0; i < n; i += 1) {
  console.log('giao~')
}

O(n^2)时间复杂度
```
for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {
  console.log('giao~')
}
}
```
O(logN)时间复杂度
```
let i = 1;
while (i < n) {
   i *= 2;  
}
```
（2的多少次方是n ，就是logN）
再次总结：
1. 算法的速度指的并非时间，而是操作数的增速;
2. 谈论算法的速度时，说的是随着输入的增加，其运行时间将以什么样的速度增加;

空间复杂度

空间复杂度类似时间复杂度，是对一个算法在运行过程中临时占用存储空间大小的量度，是从空间的角度衡量算法优劣的。
空间复杂度的代码例子例如：

O(1)空间复杂度
```
let cjj = 'ze';
cjj += 'mayBeOne2b';
```

O(n)空间复杂度

const arr = [];
for (let i = 0; i < n; i += 1) {
  console.log('giao~');
arr.push(i);
}

参考

算法概念：大O表示法/小o表示法/Ω/Θ
什么是大O表示法
 如何理解算法的空间复杂度？