时间复杂度

简介

时间复杂度是计算机科学对程序耗时的一种衡量手段，时间复杂度通用使用O符号来表示，其衡量纬度通常使用输入数据的长度，最终写成O(f(n))。

数据复杂度中的大O用来表示算法时间复杂的渐近上界，因为对于同一个算法，在不同的输入情况下，计算的次数会存在较大的差异，例如插入排序，在数据有序的情况下其时间复杂度是O(n)，但是在数据无序的情况下，其时间复杂度是会O（n²），所以我们提到插入排序其时间复杂度是O（n²）。

快速排序在数据逆序的情况下时间复杂度是O（n²），但是平均情况下，快速排序的时间复杂度是O（n*log（n））。O表达的近似复杂度一般情况描述的更加偏向一般情况下的时间复杂度，而不是严格的上界。

除了O之外，还有下列符号也是描述时间复杂度的符号；

• Θ，表示准确的时间复杂度，即时间复杂度的上界下界(tight)
• ο，表示算法复杂度的上界(not tight)，例如快速排序的上界时间复杂度是o（n²）。
• Ω，表示渐进下界，该复杂度是最优情况下的近似复杂度。
• ω，表示下界，表示最优情况下严格的时间复杂度。

应用

常用的时间复杂度有O（n³）、O（n²）、O（n*log（n））。

时间复杂度在计算过程中，去忽略常数项系数，该常数项系数是指所有低于最高阶项的计算因子。

常见的计算项的阶度高低如下：

O（2ⁿ）> O（n³）> O（n²）> O（n*log（n））> O（n）> O（log（n））> O（1）