P&NP
2019-11-26 本文已影响0人
Joe_Chestnut
P（polynomial time) 多项式时间
O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(n^4) …
例如： 求数组最大值 arr[] 一次循环比较
NP（nondeterministic polynomial time) 有一个问题 还有一个解 如果能在多项式时间内判断这个解是不是该问题的解
例如： 有一个数组 给一个解100 在多项式时间内判断100是不是该数组的最大值
NP Complete （一个问题是np问题，但是暂时没法在多项式时间内解决）
能在P时间内判定，但不能在P时间内解决的，能找到一个特解，但找到全部解超过多项式时间
例如下面的问题 找到满足条件的x1,x2,…xn需要O(2^n)
