时间复杂度

定义

用来估计程序的执行常数操作¹的时间花销的指标，叫做 big O，记为 $O(\cdot )$

其他说明

• 时间复杂度$O(\cdot )$表示的是算法在最差情况下的常数操作¹时间花销。

Attention

必须是能够人为构建出最差情况下的前提下才适用。

如果对于某一个算法，其在算法内部通过引入随机性的方式使得人们无法通过构建特定的输入来实现最差情况，那么在计算该算法时间复杂度时需要计算其时间复杂度的平均期望，而不能直接适用最差情况下的时间复杂度。

• 对于$O(\cdot )$相同的两个算法，如果一定要比较它们的优劣，则必须通过实际代码的运行来比较具体的时间消耗。
• 数据量很小时，时间复杂度和执行时间可能不相关，主要原因在于小数据量时不同运算的常数操作时间差距可能就比较明显了。例如，插入排序之类的平方算法可能比归并排序之类的准线性算法速度更快。这也就说明，在实际生产时，我们可以根据数据量来灵活的选择不同的算法。

Footnotes

1. 常数操作指的是和数据量（或者矩阵尺寸）无关的操作，比如两个数求和 arr[1]+2. (如果是链表的数据结构，则不是常数操作，因为要从头找到对应的元素，数组就是常数操作。 ↩ ↩²