目录
- 时间复杂度-大 O 标记
1. 时间复杂度-大 O 标记
大 O，说的是字母 O，而不是数字 0。这个符号用来描述在某种数据结构上执行某种操作的效率。有很多种衡量效率的方法：你可以衡量这种数据结构消耗了多少内存、在最坏的情况下消耗的时间、它花费的平均时间是多少等等。
在这篇中，你将会统计操作的平均时长。
通常，数据量增加不会使操作变快。大多数情况下是相反的，但有时候变化很小甚至没有差别。大 O 标记用来精确地描述这种情况。你能用一个具体的函数来表示运行时间和数据量的关系。
大 O 标记被写作O(与 n 相关的函数)，括号中的n就表示数据结构中数据的数量，而与 n 相关的函数则大约表示操作将要消耗的时间。
“大约”，确实有点讽刺，但是它有特定的含义：当n非常大时函数的渐进值。假设n是很大很大的数，当你将参数从n修改为n + 1时，考虑一些操作的性能会怎样变化。
注意：这些都是算法复杂度分析中的一部分，如果你想深入探索的话，就多读些计算机科学类的书籍。这样你会掌握一些分析复杂度的数学方法、不同效率之间的微小差异、关于未知机器模型的更细化公式的假设以及许多你能想到或想不到的有趣的东西。
常见的大 O 性能测量如下（性能由高到低）：
- O(1)(常数时间)：无论数据结构中有多少数据，这个函数都调用同样次数的操作。这是最理想的性能。
- **O(log n)(对数): **这个函数调用的操作次数随着数据结构中的数据量对数级增长。这已经是很好的性能了，因为相比较数据结构中的数据的数量它的增长速度要慢得多。
- O(n)（线性）：函数调用的操作次数随着数据结构的数据量线性增长。这是比较好的性能，但是如果数据集合较大就不合适了。
- O(n (log n))：这个函数调用的操作次数是由数据结构中的数据量的对数乘以数据结构中的数据量。可以预见的是，这是现实中对性能的最低容忍度。较大的数据结构会执行更多的操作，对于数据量较小的数据结构来说增长是较为合理的。
- O(n²)（平方）：这个函数调用操作的次数是数据量的平方 - 这算是比较差的性能中最好的一个。哪怕你处理的数据集很小，它也会很快变慢。
- O(2^n)（指数）：函数调用的操作次数与数据量是2的n次方的关系。这会导致很差的性能并很快就变得特别慢。
- O(n!) (阶乘)：函数调用的操作次数与数据量之间是阶乘的关系。实际上，这是性能最差的情况。例如，在一个有 100 个数据的结构中，操作次数是一个长度为158的数字。
