时间复杂度 与 P,NP,NPc

P,NP,NPc

http://blog.csdn.net/liyangbing315/archive/2010/05/06/5563800.aspx

首先说个基本概念----时间复杂度：并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O(n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。

P（polynomial）问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题.

NP(nondeterministic polynomial)问题:是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。Hamilton回路问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路），我要找一个图的哈密顿路径，随便给我一个解，我都可以在P时间内检查它是不是哈密顿路径，P问题是属于NP问题的，因为给定一个P问题，我可以在P时间内找到答案，那么任意给我一个解，我简单的比较解和答案是不是相同，就可以回答yes/no，整个时间是P，符合定义。

NPC(nondeterministic polynomial complete)问题:是这样的一类问题，首先他是属于NP的，而且他是NP问题里面最难解决的问题,难到什么程度？只要其中某个问题可以在P时间内解决，那么所有的NP问题就都可以在P时间内解决了。证明一个问题是NPC问题也很简单,先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它.

NP-hard(nondeterministic ponomial hard)问题:是这样的问题，只要其中某个问题可以在P时间内解决，那么所有的NP问题就都可以在P时间内解决了。NP-c问题就是NP-hard问题。但注意NP-hard问题它不一定是NP问题，比如，下围棋就是NP-hard问题，但不是NP问题，我们要在一个残局上找一个必胜下法，告诉我们下一步下在哪里。显然，我们找不这个解，而且更难的是，就算有人给我了一个解，我们也无法在P时间内判断它是不是正确的。NP-Hard问题满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。



本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/liyangbing315/archive/2010/05/06/5563800.aspx