算法的时间复杂度
我之前理解的时间复杂度，是指的解决一个问题所需要的时间。但其实并不准确，时间复杂度应该是 当问题规模扩大后，程序需要的时间长度增长得有多快。
时间复杂度有两种类型：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，它的复杂度是计算机不能接受的。
P和NP
P问题：可以找到一个 多项式的时间里 解决该问题的算法
NP问题：可以在多项式时间内找到一个解，用来解决该问题。换言之，如果我猜了一个解，并且可以在多项式的时间内验证它是对的，那么这个问题就是一个NP问题
有一个算法可以在多项式时间里可以解决该问题，那就一定可以在多项式时间内验证一个解是否正确，也就是说 P问题都是NP问题。那么反过来是否成立呢？NP问题是否都是P问题？
规约和NPC
规约：
一个问题A可以规约为问题B的含义即是：
- 可以用问题B的解法解决问题A
- 问题A可以“变成”问题B。
- 如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同
《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。
A规约为B，那么意味着B的解题的算法更广，同时意味着B的复杂度更高。
NPC问题：
是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以规约成它。这种超级NP问题就是NPC问题。
NPC问题不仅有一个，它是有很多个。由于规约的传导性，如果找到一个问题，能够规约到NPC问题，那么这个问题也是NPC问题了。
如果NPC有多项式时间复杂度的算法能够解，那么所有NP问题也就有了多项式时间复杂度算法能够解，那么也就意味着P=NP。
然而事实是，目前人们无法证明NPC有多项式时间复杂度的算法能够解（也无法证明没有），但是大家更倾向于没有（直觉吧）
所以在通常意义上，说该问题是NPC问题，其实是想表示该问题没有一个多项式时间复杂度的算法，一般这种问题，都是通过“搜索”来解决的。
标签：多项式,复杂度,NPC,问题,算法,NP,运筹学 From： https://www.cnblogs.com/4PrivetDrive/p/17604763.html