时间复杂度

定义：算法语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n) = O(f(n)) 它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。”

这种用个大写的 O 来代表算法的时间复杂度的记法有个专业的名字叫 “大 O 阶” 记法。那么通过对上述的例子进行总结，我们给出算法的时间复杂度（大 O 阶）的计算方法。

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

举例：

int n = 100000;        // 执行了 1 次

for (int i = 0; i < n; i++) {        // 执行了 n + 1 次
    for (int j = 0; j < n; j++) {        // 执行了 n*(n+1) 次
        printf("i = %d, j = %d\n", i, j);        // 执行了 n*n 次
    }
}

for (int i = 0; i < n; i++) {        // 执行了 n + 1 次
    printf("i = %d", i);        // 执行了 n 次
}

printf("Done");        // 执行了 1 次

执行总次数 = 1 + (n + 1) + n(n + 1) + nn + (n + 1) + 1 = 2n^2 + 3n + 3 这里 n^2 表示 n 的 2 次方。

1. 执行总次数 = 2n^2 + 3n + 1 这里 n^2 表示 n 的 2 次方；
2. 执行总次数 = 2n^2 + 3n + 1 这里 n^2 表示 n 的 2 次方；
3. 执行总次数 = n^2 这里 n^2 表示 n 的 2 次方；

最后得到上面那段代码的算法时间复杂度表示为： O(n^2) 这里 n^2 表示 n 的 2 次方。

各个时间复杂度效率高低：

O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < { O(2^n) < O(n!) < O(n^n) }

---

时间复杂度这个东西，其实更准确点说应该是描述一个算法在问题规模不断增大时对应的时间增长曲线。所以，这些增长数量级并不是一个准确的性能评价，可以理解为一个近似值，时间的增长近似于 logN、NlogN 的曲线。

对增长数量级的常见假设的总结.jpg 二维图解.jpg