到底什么是NP问题，NP hard问题，NP完全问题？ In 世界杯晋级规则 @2025-07-08 09:33:00
关于 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
(
l
o
g
(
n
)
)
,
O
(
n
a
)
O(1),O(log(n)),O(n^a)
O(1),O(log(n)),O(na) 等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；
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)) 如二分搜索算法
另一种是
O
(
a
n
)
O(a^n)
O(an) 和
O
(
n
!
)
O(n!)
O(n!) 型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。
当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
再说 P 问题
P类问题是可以找到一个能在多项式时间内解决它的算法
再说 NP 问题
NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
举个例子：我人品很好，在程序中需要枚举时，我可以一猜一个准。
现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？
我说，我人品很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。
于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。这就是NP问题
再说 NPC 问题（NP完全）问题
NP-Complete 满足两个条件：
首先它是一个NP问题所有的NP问题都可以约化（Reducible）到它，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索
约化：例如，求解一个一元一次方程
A
A
A 和求解一个一元二次方程
B
B
B，你若会求解
B
B
B ，你一定会求解
A
A
A。那么我们说，A 可以约化为 B。
B
B
B 的时间复杂度高于或者等于
A
A
A的时间复杂度。
最后说NP难问题
NP hard 满足 NPC 的第二条件，但不一定是 NP 问题。 因为它不一定是NP问题。即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上，由于 NP-Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。