《大话数据结构》之算法的时间复杂度

算法的时间复杂度一般是指算法的最坏执行情况（最大执行次数）。

1. 大O表示法

衡量算法的复杂度（一般指时间复杂度）通常使用大O表示法，其推导的一般方式为：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项乘积的常数。

最终得到的结果就是大O阶。

2. 常用的大O阶

• 常数阶
  O(1)：如顺序结构的复杂度或是分支结构（if--else--），执行次数恒定，不会随n变化而变化。
• 线性阶
  O(n)：如循环结构，根据循环次数决定。
• 对数阶
  O(logn): 例如如下循环

int count = 1;
while(count < n) {
    count = count * 2;
    /** 时间复杂度为O(1)的顺序步骤序列 */
}

如上所示，x为执行次数，2^x = n，即x = log2n，故时间复杂度为O(logn)。

• 平方阶
  O(n^2)：如双重嵌套循环。

3. 常见的时间复杂度排列

耗费时间从小到大依次为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)