本文共 1472 字，大约阅读时间需要 4 分钟。
时间复杂度
先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。 复杂度可以分为两种级别：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。 P问题 在多项式复杂度时间内能解决它的算法的问题。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。 NP问题 具有多项式复杂度的不确定性问题 or可以在多项式时间内验证一个解的问题 or在多项式时间内可以才出一个解的问题 在某些情况下，求一个解很难，但是验证一个解要容易的多 NP问题与P问题的关系 P问题必然是NP问题，因为可以用多项式解决的问题必然可以用多项式验证。但是两者并不等价接下来，为了说明NP问题，我们先引入一个概念，
约化（reducibility）, 也叫做归约。A问题可以归约到B问题的含义是：可以用解决B问题的方法解决A问题，即问题A可以转化为问题B。这里有一个很重要的直观意义，B的时间复杂度高于或等于A的时间复杂度，即问题B并不比问题A简单。 约化还有一条重要的性质，即可传递性，很好理解不必赘述了。 约化的概念 如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。 注意，这里说的可约化是指可多项式地约化，即变换输入的方法是能在多项式时间内完成的，约化的过程只有用多项式的时间内完成才有意义。 从上述描述中可以看出，虽然时间复杂度在增加，但是归约后的问题适用范围更加广泛了，继续设想，如果时间复杂度继续增加，进一步对问题进行归约，那么最终我们可以得到一个可以解决所有NP问题的超级NP问题，那么它是否存在呢？答案是肯定的，事实上，这种问题不是一个，而是一类，就是传说中的NPC问题。接下来给出称为NPC问题必须具备的两个条件 NPC问题 ·第一，它要是一个NP问题 ·第二，所有的NP问题都可以约化到它既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
NP-Hard问题 NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。！！！NPC问题不是一纸空谈，不是以太这种靠想像出来现实中不存在的东西。实际上，逻辑电路是NPC问题的鼻祖
NP问题一直是信息学的巅峰～～～高山仰止，期待有志者的探索。。。
转载地址：http://yqqpi.baihongyu.com/