为什么要进行算法分析？
预测算法所需的资源
计算时间（CPU 消耗）
内存空间（RAM 消耗）
通信时间（带宽消耗）预测算法的运行时间
在给定输入规模时，所执行的基本操作数量。
或者称为算法复杂度（Algorithm Complexity）
如何衡量算法复杂度？
- 内存（Memory）
- 时间（Time）
- 指令的数量（Number of Steps）
- 特定操作的数量
- 磁盘访问数量
- 网络包数量
- 渐进复杂度（Asymptotic Complexity）
算法的运行时间与什么相关？
- 取决于输入的数据。（例如：如果数据已经是排好序的，时间消耗可能会减少。）
- 取决于输入数据的规模。（例如：6 和 6 * 109）
- 取决于运行时间的上限。（因为运行时间的上限是对使用者的承诺。）
算法分析要保持大局观（Big Idea），其基本思路：
- 忽略掉那些依赖于机器的常量。
- 关注运行时间的增长趋势。
| 复杂度 | 符号 | 描述 |
|---|---|---|
| 常量（Constant） | O(1) | 操作的数量为常数，与输入的数据的规模无关。 n = 1,000,000 -> 1-2 operations |
| 对数（Logarithmic） | O(log2 n) | 操作的数量与输入数据的规模 n 的比例是 log2 (n)。n = 1,000,000 -> 30 operations |
| 线性（Linear） | O(n) | 操作的数量与输入数据的规模 n 成正比。 n = 10,000 -> 5000 operations |
| 平方（Quadratic） | O(n2) | 操作的数量与输入数据的规模 n 的比例为二次平方。 n = 500 -> 250,000 operations |
| 立方（Cubic） | O(n3) | 操作的数量与输入数据的规模 n 的比例为三次方。 n = 200 -> 8,000,000 operations |
| 指数（Exponential） | O(2n) O(kn) O(n!) | 指数级的操作，快速的增长。 n = 20 -> 1048576 operations |