关于 NP 问题网上胡写的太多了！

这里的解释绝对是最清楚，原文摘自 http://www.matrix67.com/blog/archives/105

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

时间复杂度可以分为几种情况：

1、不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有 O ( 1 ) O(1) O(1)的时间复杂度，也称常数级复杂度；

2、数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 O ( n ) O(n) O(n)，比如找 n n n 个数中的最大值；

3、而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于 O ( n 2 ) O(n^2) O(n2)的复杂度。

4、还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 O ( a n ) O(a^n) O(an)的指数级复杂度，甚至 O ( n ! ) O(n!) O(n!)的阶乘级复杂度。

注意是不会存在 O ( 2 ∗ n 2 ) O(2*n^2) O(2∗n2) 的复杂度，因为前面的那个 “ 2 ” “2” “2”是系数，根本不会影响到整个程序的时间增长。

同样地， O ( n 3 + n 2 ) O (n^3+n^2) O(n3+n2)的复杂度也就是 O ( n 3 ) O(n^3) O(n3) 的复杂度。因此，我们会说，一个 O ( 0.01 ∗ n 3 ) O(0.01*n^3) O(0.01∗n3) 的程序的效率比 O ( 100 ∗ n 2 ) O(100*n^2) O(100∗n2) 的效率低，尽管在 n n n 很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终 O ( n 3 ) O(n^3) O(n3) 的复杂度将远远超过 O ( n 2 ) O(n^2) O(n2)。我们也说， O ( n 100 ) O(n^{100}) O(n100) 的复杂度小于 O ( 1.0 1 n ) O(1.01^n) O(1.01n) 的复杂度。

我们作进一步归类为：

O ( 1 ) O(1) O(1) 表示一次操作即可直接取得目标元素（比如字典或哈希表）， O ( n ) O(n) O(n) 意味着先要检查 n n n 个元素来搜索目标, O ( l o g ( n ) ) O(log(n)) O(log(n)) 如二分搜索算法

当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

P类问题是可以找到一个能在多项式时间内解决它的算法

NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

举个例子：我人品很好，在程序中需要枚举时，我可以一猜一个准。

现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？

我说，我人品很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。

于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。这就是NP问题

NP-Complete 满足两个条件：

约化：例如，求解一个一元一次方程 A A A 和求解一个一元二次方程 B B B，你若会求解 B B B ，你一定会求解 A A A。那么我们说，A 可以约化为 B。 B B B 的时间复杂度高于或者等于 A A A的时间复杂度。

NP hard 满足 NPC 的第二条件，但不一定是 NP 问题。 因为它不一定是NP问题。即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上，由于 NP-Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。