103课程算法课件

1、第一章 绪论2012年秋季学期ComuterAlorithms-roductiontoDesignandysis，SaraBasse,AllenVanGelder，高等教育1.1roduction算法不仅是计算机科学的一个分支，它更是计算机科学的，而且，可以毫不夸张地说，它和绝大多数的科学、商业和技术都是相关的David Harel算法：计算的算法可以解决哪些问题找出人类DNA中所有100000中，确定人类DNA的30亿种化学基对的各种序列快速地和检索互联网数据电子商务活动中各种信息的加密及签名制造业中各种资源的有效分配确定地图中两地之间的最短路径各种数学、几何计算（矩阵、方程、集合）旅行商问

2、题有n个城市,已知任意2城市之间的距离, 一名推销员要拜访这n个城市，如何找到在拜访每个地点一次后再回到起点的最短路径。在一个图中，从图的一个顶点出发，沿着图中的边，经过所有顶点各一次，这条路线就称之为路；如果最终又回到了起点，则称为回路。有最短回路的图称之为回路即是要求所有图。回路中最短的一条路径。方法一找出所有可能的回路计算所有找出最短的回路的路径长度回路穷举法的时间复杂度O(n!)n=21,21!=5.11*1019,设每条路径需要CPU时间1ns，需要1620多年才能完成方法二一步步回溯，有好的下来回路就保留A21123B12E183CD4分支限界法分支限界法类似于回溯法，也是一种在问

3、题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。A22113B8E方法三1123A分支限界法CD24B81 3CE CDE4D12 34312E C D1244123CD CEE211AAA目前最短的回路长度=19A22113B8E方法二1123A分支限界法CD24B81 3CE CDE4D12 34312E C D1244123CD CEE211AAA目前最短的回路长度=

4、13G 邻接矩阵V 栈W 保存最短路径图b 表示点是否进栈top 为栈顶指针，p为当前查看结点，L为当前路径长度方法四贪心算每次选择最近的点，总代价会比较小，但是局部最优，不一定是全局最优解。A12213B8E1123CD4方法五图的规模更大采用分治的：将一个大的区域分成多个小区域，分别求出每一个小区域的最优解，并以最优的方式将各个区域连接起来本课程主要内容介绍、研究、分析计算机解决问题常用的一些算法算法的时间和空间分析算法设计的技术：分治、贪心、深度优先搜索、动态规划等研究问题本身的计算复杂性plete问题启发式算法说明描述工具JAVA1.2节相关数学知识-1.3节上述2节+基本的数据结构知

5、识自己复习补习1.4yzingAlgorithmsandProblems算法评价的准则：（1）正确性（2）时间（3）空间（4）简单性、清晰性（5）优化正确性证明对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。算法：方法和指令序列确定输入和输出的关系一般方法：数学归纳法正确性证明的内容方法的正确性证明算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序的正确性证明可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式

6、方法等1.4.2 Amount of work done算法本身选用的策略问题的规模书写程序的语言编译产生的机器代码质量机器执行指令的速度一个特定算法的运行工作量只依赖于问题的规模算法时间复杂度1.4.2 Amount of work done从算法中选取一种对于所研究来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。T(n)=O(f(n)随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。1.4.2 Amount of work done问题

7、基本操作Find x in an array of namesComparison of x win entryhe arrayMultiply two matriwithMultiplication of two realreal entriesnumbersSort an array of numbersComparison of two array entries1.4.3平均和情况分析算法的时间复杂性问题的规模+具体的输入情况情况下的时间复杂性| IDn W(n)=maxt(I)平均情况下的时间复杂性 pr(I )t(I )A(n)=I查找算法为例说明w(n),A(n)1.5 渐进时间

8、复杂性设f,g是定义域为自然数的函数，f(n)=O(g(n):若存在正数c和n0，使得对一切nn0,0f(n)cg(n)limf (n) c g(n)n练习f(n)=n3/2, g(n)=37n2+120n+12证明：gO(f),fO(g)设f,g是定义域为自然数的函数，f(n)=(g(n):若存在正数c和n0，使得对一切 nn0,0cg(n) f(n)limf (n) 0g(n)n设f,g是定义域为自然数的函数，f(n)=(g(n):f(n)=O(g(n), f(n)=(g(n)(g) O(g)O(g)limf (n) c,0 c g(n)no,的定义设f,g是定义域为自然数的函数f(n)=

9、o(g(n):若任意正数c ,存在n0 ,使得对一切nn0,0f(n) cg(n)f(n)= (g(n):若任意正数c,存在n0 ,使得对一切nn0,0 cg(n) f(n)O,o,第二种理解法求复杂性函数阶的极限方法limf (n) s若g(n)n当s0时，f(n)与g(n)同价， f(n) =(g(n)当s=0时，f(n)比g(n)阶低， f(n) =O(g(n)当s=无穷时， f(n)比g(n)阶高f(n) =(g(n)证明规则O(f(n)+O(g(n) = O(maxf(n),g(n)对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1

10、f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。则对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n)= 2c3h(n) = O(maxf(n),g(n) .算法分析中常见的复杂性函数小规模数据中等规模数据最优算法问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法

11、。例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。P与NP问题多项式级的复杂度：O(1),O(n),O(logn),O(n2)等非多项式级的复杂度：O(an),O(n！)等P与NP问题P问题-可以由一个确定型图灵机在多项式表达的时间内解决NP问题-其肯定解可以在给定正确信息的多项式时间内验证的判定问题组成或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出合。的集P与NP问题求n个数的平均数P问题分解因子问题比如把44427因数分解，过程复杂，验证容易，175*251NP问题回路NP问题P与NP问题P属于NPP=N

12、P？NP问题不一定都是难解，比如，简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题Reducibility 约化，归约一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。求解一个一元一次方程和求解一个一元二次方程：前者可以约化为后者，即知道如何解一个一元二次方程那么一定能解出一元一次方程。Reducibility 约化，归约问题A可约化为问题B”：B的时间复杂度高于或者等于A的时间复杂度。即，问题A不比问题B难约化的性质：传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。“可约化”是指的可“多项式

13、地”约化(Polynomial-timeReducible)，问题同时满足下面两个条件是一个NP问题；就是问题：(2) 所有的NP问题都可以约化到它。证明一个问题是问题：先证明它是一个NP问题，再证明其中一个已知的问题能约化到它，这样就可以说它是既然所有的NP问题都能约化成问题了。问题，那么只要任意一个问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。问题是求NP中判定问题的一个子类比如前面说的回路问题就是一个问题。问题的历史并，cook在1971年找到了第一个问题，此后人们又陆续发现很多可能已经有3000多个了。所以，问题，现在一般认为问题是难解间的算法

14、。类似，因为他不太可能存在一个多项式时回路/路径问题，货郎担问题，问题，最小边覆盖问题，等等很多问题都是问题，所以都是难解。NP-Hard问题一个问题是NP-Hard问题，如果所有的NP问题都可以约化到它。它满足问题定义的第二条但不一定要满足第一条（NP-Hard问题要比问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不的研究范围，因为它不一定是NP问题。问题发现了多项式级的算法，NP-Hard问列入即使题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有。的时间复杂度更高从而更难以解决P真的容易处理吗？一个需要101000n时间题与一个需要10-100002n时间的问1.一个时间复杂度n1000与一个时间复杂度2n/1000的问2.题它只考虑了情况的复杂度。可能现实世界中的有些3.问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这个问题可能有一个多项式的平均时间，但情况是指数式的，所以该问题不属于P。它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案