无论是处理业务逻辑，还是解决数学问题，程序员的脑海里都必须有对问题的解决方案有准确的、完整的描述，也就是算法。我不讨论算法的各种性质和定义，这次主要是总结算法复杂度几种描述方式以及P、NP和NP完全性。
复杂度
时间复杂度
算法的时间复杂度可以定性的描述 随着输入规模变大，算法耗时增长的快慢。
插入排序最坏情况是 $O(n^2)$ ，归并排序最坏情况是 $O(nlogn)$ ，这表示插入排序随着输入规模的增大，耗时呈 平方级别 的增长；而归并排序的耗时呈 nlogn级别 的增长，所以这两个函数增长的阶不在同一个级别上。这样的定性分析，我们可以知道当输入规模n很大时（比如n=10,000），在两者之间，应该选择归并排序。这里强调的是耗时的增长，并不说明插入排序比归并排序慢，当n很小时(比如n=15)，插入排序可能比归并排序耗时短。
渐进记号
描述算法时间复杂度有五种记号： $\Theta、O、\Omega, o、\omega$ 。这五种记号又叫做 渐进记号，它们本表示函数集合，以 $\Theta$ （读作：大Theta）为例：
$\Theta(g(n)) = { f(n): 存在正常数 c_1, c_2 和n_0，使得当n \geq n_0 时，有 0 \leq c_1g(n) \leq f(n) \leq c_2g(n)}$
比如我们通过精密的分析得到了插入排序的耗时为 $f(n) = 2n^2-n+17$ ，我们若能找到合适的 $c_1, c_2, n_0$ 使得 $使得当n \geq n_0 时，有0 \leq c_1g(n) \leq f(n) \leq c_2g(n) $，就能证明插入排序的时间复杂度为 $\Theta(n^2)$ 。
下面是其余四个记号的描述：
$O(g(n)) = { f(n): 存在正常数 c和n_0，使得当n \geq n_0 时，有 f(n) \leq cg(n)}$ ，渐进上界
$\Omega(g(n)) = { f(n): 存在正常数 c 和n_0，使得当n \geq n_0 时，有 cg(n) \leq f(n) }$，渐进下界
$o(g(n)) = { f(n): 对于任意正常数 c，存在n_0使得当n \geq n_0 时，有 f(n) \leq cg(n) }$，非渐进紧确上界
$\omega(g(n)) = { f(n): 对于任意正常数 c，存在n_0使得当n \geq n_0 时，有 cg(n) \leq f(n) }$，非渐进紧确下界
记号 $O$ (读作大O) 和 $o$ (读作小o)的区别是：$O$ 可能不紧，因为只需要存在一个正常数 $c$ 即可，例如函数$2n^2 \in O(n^2)$ 是紧确的 ，但 $2n \in O(n^2)$ 却不是。 $o$ 记号表示 非渐进紧确 的上界，所以 $ 2n^2 \notin o(n^2)$ 而 $2n \in o(n^2)$ 。记号 $\Omega$ 和 $\omega$ 的道理是一样的。
我们可以说插入排序的最坏情况运行时间是 $O(n^2)$ ，而不能说 $\Theta(n^2)$ 。因为若数组已经有序，则插入排序耗时为 $\Theta(n)$ ，显然 $\Theta(n) \in O(n^2)$ ，但 $\Theta(n) \notin \Theta (n^2)$ 。
我们不能说插入排序的运行时间是 $O(n^2)$ 。如果一个算法的运行时间是 $O(n^2)$ ，这表明存在一个函数 $f(n)$，对于任意大小为n的数据，算法运行时间为 $f(n)$ ，而与数据无关。
等式分析
我们可能见过下面的式子 $T(n) = 2T(\frac{n}{2}) + \Theta(n)$，记号 $\Theta$ 本表示集合，却出现在了等式的右边。
当渐进记号出现在等式(或不等式)的一边，这表示一个 匿名函数，我们并不关心函数具体是什么。例如 $2n^2+3n+1 = 2n^2 + \Theta(n)$，这里的 $\Theta(n)$ 代替了 $3n+1$ 。这样的作坊有助于我们略去等式中无关紧要的细节。
当渐进记号出现在等式(或不等式)的两边，这表明 无论等号左边的匿名函数如何选择，总有办法选取等号右边的匿名函数使等式成立，例如 $2n^2 + \Theta(n) = \Theta(n^2)$ 。
这样以来，即可将其链起来得到：
$2n^2+3n+1 = 2n^2 + \Theta(n)= \Theta(n^2)$
最终得到 $2n^2+3n+1= \Theta(n^2) $，这种分析方式直观、简便又高效。
NP完全性
P（Polynomial）类问题：能在多项式时间内被解决的问题。
有些问题是能写出算法解决的，无非是加减乘除、逻辑运算，这些都是按照一定步骤进行就能得到结果的，若算法的时间复杂度是 $O(n^k)$(k为某个常数)，则该问题就输入P类问题。 例如找到一个数组中最大的数，找到点集中距离最短的两个点。
NP（Non-Deterministic Polynomial）类问题：能在多项式时间内被验证的问题。
有些问题不能写出算法得到最优解，但可以通过 猜算 得到一个解，在猜出一个解之后，需要判断这个解是否为正解，判断是否为正解的算法若在多项式时间内运行完，则该问题就是NP类问题。比如大质数问题，没有算法能计算得到下一个质数是多少，但我们能在多项式时间内判断一个数是不是质数。
P类问题也叫做 易解 问题，而NP类问题又叫 难解 问题。显然 $P \subseteq NP$ 。因为能在多项式时间内解决的问题，它的一个解肯定能在多项式时间内验证（跑一次算法得到一个解即可）。P 是否等于 NP 是目前的一个世界难题。
假设A是一个NP问题，若A与NP中的任何一个问题是一样难的，则A是NP完全问题。目前发现的NPC问题有21个：Wiki:NP-completeness，所有的NP问题都能规约到这21个问题中的一个。
参考资料
[1] NP问题, 2019-03-23.
[2] 一文读懂什么是P问题、NP问题和NPC问题, 2019-03-23.
[3] P问题、NP问题、NPC问题（NP完全问题）、NPH问题和多项式时间复杂度, 2019-03-23.
[4] Thomas H.Cormen et al., 殷建平等译, 算法导论(原书第三版), 机械工业出版社, 2012.
