3.3 算法的复杂度
计算复杂度（computational complexity）：
- 时间复杂度：解决特定规模的问题所需的时间的分析
- 空间复杂度：所需计算机内存的分析
时间复杂度¶
在输入具有一定规模时，算法的时间复杂度可以用算法所需的运算次数表示。
用于度量时间复杂度的运算：整数比较、整数加法、整数乘法、整数除法等其他基本运算
时间复杂度用所需运算次数而不是计算机实际使用的事件表示，因为执行基本运算时不同计算机需要的时间不同。
最坏情形复杂度
指的是该算法用于具有一定输入规模的问题时所需要的最多的运算次数。最坏情景分析告诉我们一个算法需多少次运算就能保证给出问题的解答。
平均情形复杂度
求解针对一定规模的问题的所有可能的输入所用到的运算的平均数
矩阵乘法的复杂度：\(\Theta (mkn)\)
深入理解¶
| Complexity | 复杂度 | Terminology |
|---|---|---|
| \(\Theta (1)\) | 常数 | Constant complexity |
| \(\Theta (log \ n)\) | 对数 | Logarithmic complexity |
| \(\Theta (n)\) | 线性 | Linear complexity |
| \(\Theta (n \ log \ n)\) | 线性对数 | Linearithmic complexity |
| \(\Theta (n^b)\) | 多项式 | Polynomial complexity |
| \(\Theta (n^b), \ where b > 1\) | 指数 | Exponential complexity |
| \(\Theta (n!)\) | 阶乘 | Factorial complexity |
算法复杂度 \(\not =\) 问题复杂度
- 易解性（tractable） 与 难解（instractable）：一个能用多项式最坏情形复杂度（或更优）的算法求解的问题成为 易解性。
- 不可解的（unsolvable）与可解的（solvable）
没有多项式最坏情形时间复杂度的算法能求解，但是一旦有了一个解答，却可以用多项式时间内验证。
- NP类：能以多项式时间内验证解的问题，易解问题属于P类 缩写NP是指 非确定性多项式（nondeterministic polynomial）时间
- NP完全问题（NP-complete problem）：只要其中任何一个问题能用一个多项式时间最坏情形算法来求解，那么NP类的所有问题都能用多项式时间最还清醒求解。
- P Vs NP：绝大数理论计算机科学家相信，\(P \not = NP\)。目前还没有成功证明，\(P = NP\)。P与NP问题是数学科学中最著名的问题之一。