复杂度与NP完全性

无论是处理业务逻辑,还是解决数学问题,程序员的脑海里都必须有对问题的解决方案有准确的、完整的描述,也就是算法。我不讨论算法的各种性质和定义,这次主要是总结算法复杂度几种描述方式以及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.

坚持原创文章分享,您的支持将鼓励我继续创作!