P和NP问题总结.docx
5星 · 超过95%的资源 需积分: 24 189 浏览量
2019-09-18
19:33:35
上传
评论
收藏 1.18MB DOCX 举报 
P Vs NP 问题
1.什么是 P 问题？
P 是 polynomial（多项式），一个问题如果能在多项式时间（ polynomial
time）内解决，那这个问题就是 P 问题。如：排序问题
2.什么是多项式时间和非多项式时间
（1）多项式时间可以表示为 a
n
+b
n-1
+…+z
如：O(1), O(logn), O(n), O(nlog
n
), O(n
2
), O(n
3
), O(n
4
)
（2）非多项式时间，如 O(a
n
),O(n!)
3.P 问题举例
假如一个数组 arr[], 有 n 个元素，求该数组的最大值
解法：设第一个值为最大值，用一个 for 循环，对后面的元素进行检测，不停
更新最大值，等同于遍历整个数组，所需时间为 O(n)。
4.什么是 NP 问题？
NP 是 nondeterministic polynomial（非确定性多项式），假设有一个问题，
有一个值，如果在多项式时间内证明这个值是原问题的解，就叫做 NP 问题
（它不讨论能不能在 P 时间内解决）；
或换一种说法：如果你作了正确的解决方案，现可以在一个合理的时间量检验
它的方案是否正确。如：车辆路径规划，电路设计。
即所谓的找一个解很难，验证一个解很容易的问题。
评论10
最新资源