NP- 学习研究生课程.pptVIP

NP问题 Nondeterministic  Polynomial ;1、时间复杂度; A、不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度； B、数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值； C、而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。 D、还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是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!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。 因此：当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。 ;;问题 ;2、P类问题 ;NP例1：;NP例2：;之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。;关键是，人们想知道，是否所有的NP问题都是P类问题。 ;4、NPC问题;约化;约化;NPC定义;NPC问题解法;NP-Hard问题 ;P类、NP类、NPC类问题关系;解决NP=P?的途径;NP完全问题的求解;NP完全问题的近似解法;TSP问题;NP完全问题的研究现状（千年数学难题）