论P类问题和NP类问题
很多人认为NP问题就是在P时间内解不出来的问题
P是Polynomial（翻译：多项式），Polynomial time是多项式时间的意思
所以P类问题是在多项式时间内可以求解的判定问题是P类问题，简单说就是在o（1）、o（n）、o（logN）、o（NlogN）、o（n^2）、o（n^3）、o（n^4）……内可以解决的问题则为P类问题，o（2^n）则不是P类问题
比如：
给你一个数组arr[n]，让你求解里面的最大值
我们可以设计一个o（n）的算法，即设定m = arr[0]为最大值，然后不断向后遍历，如果有一个量比m大，为 m = 这个量
我们只需要设计一个for循环即可。
由于这个题目可以在o（n）内解决，所以这个题目为P类问题
NP类问题，NP其实是Nondeterministic Polynomial，而不是non Polynomial
定义：如果有一个问题和一个解，我们可以在多项式时间内来确定一个解是否是这个问题的解
比如:
给你一个数组arr[n]，和x=9，请确定arr[n]中的最大值是否为x
同理，我们可以设置一个for循环，来解决这个问题
总结：最大值问题是P类问题，也是NP类问题
再举一个例子
中位数（median）
给你一个数组arr[n]，求出中位数m
首先我们确定一下是不是P类问题
（1）我们可以先排序（sort）【o（NlogN）】
（2）arr[n/2]【o（1）】
所以这个问题是P类问题
我们再确认一个是不是NP类问题。
（1）随便找一个数字x = 9
（2）判断x是否是中位数，我们只需找出多少个比9大和多少个比9小的数量，若相等则为中位数【o（N）】
所以这个问题也可以是NP类问题。
为什么有人认为NP类问题是在o（）时间内无法解决的问题呢？
因为他们把NP类问题和NP完全问题（Nondeterministic Polynomial Complete）混在了一起，这两者不是等价的。
NP完全问题的定义：我们无法在P时间（Polynomial Time）内将问题解出，但是我们可以验证X是不是这个问题的解。
总结：NP类问题包括P类问题，NP类问题含有P类问题和NP Complete问题。
这里我们举一个NP Complete问题
SAT问题：
给你很多boolean变量 x1,x2,x3,……,xn
现在将所有的boolean的变量组合成CNF算式
在括号中随意放3个xn，且括号的数量可以无限，例如
（x1 || x2 || x3）&&（x1 || !x2 || !x3）&&（!x1 || x4 || x5）
问是否存在 x1……x5 使得上述式子等于true
因为我们可以在0（1）内判断是否为true，所以是NP类问题，
但是x1……x5，我们无法确定是多少，只能不断枚举爆破，所以求出答案的过程需要o（2^n）很明显这个不是一个多项式时间问题了，所以这个问题不是P类问题。
