第1章算法概述.ppt

计算机算法设计与分析,郭艺辉 广东金融学院 计算机科学与技术系 办公室：1622 电话：13503000588，37215835 Email：校内邮箱 gdufguo126.com,计算机算法设计与分析,教材：计算机算法设计与分析-王晓东 参考资料： 算法设计与分析 郑宗汉 清华大学出版社 计算机算法基础（第三版） 余祥宣 华中科技大学出版社 算法设计与分析基础(第2版) 作者:(美) 译者: 潘彦 清华大学出版社,主要章节介绍,第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略,计算机算法设计与分析,算法：是指解决问题的一种方法或一个过程。更严格地讲，算法是由若干条指令组成的又穷序列，且满足下述4条性质： 输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。,计算机算法设计与分析,程序： 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,百鸡问题,公元前5世纪末，中国古代数学家张丘建在他的算经中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？,百鸡问题,算法A的程序代码如下： For x = To 100 For y = To 100 For z = To 100 If (x+y+z=100) And (5* x + 3 * y + z/3 = 100) Then List1.AddItem Str(x) + “ “ + Str(y) + “ “ + Str(z) End If Next z Next y Next x,算法的描述方法,百鸡问题,算法B程序代码如下： For x = To 20 For y = To 33 Z=100-x-y If 5* x +3* y + z/3 = 100 Then List1.AddItem Str(x) + “ “ + Str(y) + “ “ + Str(z) End If Next y Next x,百鸡问题,运算结果是计算机B先把结果运算出来。为什么会这样呢？ 我们来分析一下，算法A需要执行××约100万次内循环，而算法B只需要执行2×3约714次内循环。,货郎担问题,货郎担问题(Traveling Salesman Problem，简称“TSP”) 中国邮路问题，旅行商问题等,是计算机算法理论历史上的经典问题。在过去几十年中，它成为许多重要算法思想的测试平台，同时也促使一些新的理论领域的产生，比如多面体理论和复杂性理论。 货郎担问题：某售货员要到若干个城市销售货物,已知各城市之间的距离,要求售货员选择出发的城市及旅行路线,使每一个城市仅经过一次,最后回到原出发城市,而总路程最短。,穷举法货郎担问题,穷举法版本的货郎担问题 输入：城市个数n,费用矩阵c；输出：旅行路线t,最小费用min 1. void salesman_problem(int n,float 14. 15. ,穷举法货郎担问题,个城市会产生！个排列，于是售货员共有！条路线可供选择。采用穷举法逐一计算每一条线路的费用，从中找出费用最小的路线，便可求出问题的解。 当时，运行时间是秒，算法可行；当时，运行时间是小时，算法可接受； 当时，运行时间是天，算法不实用；当时，运行时间是万七千年，该算法不可取！,算法复杂性,算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。 一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I)（通常，让A隐含在复杂性函数名当中）。,算法复杂性,算法的时间复杂性越高，算法的执行时间越长；反之，执行时间越短。算法的空间复杂性越高，算法所需的存储空间越多；反之越少。在算法的复杂性分析中，对时间复杂性的分析考虑得更多。 设一台抽象计算机提供的元运算有k种,分别记作O1 ,Ok ，设这些元运算每执行一次所需时间分别为t1 , t2,tk ,设算法A中用到Oi的次数为 ei, i=1,k,则 ei= ei(N,I ),T=T(N,I)=,算法复杂性,以上分别是最坏情况下、最好情况下和平均情况下的时间复杂性。 其中 DN:规模为N的所有合法输入的集合； I*: DN中达到Tmax (N)的一个输入； I : DN中达到Tmin (N)的一个输入； P(I): 出现输入为I的概率。,算法复杂性,没有一个方法能准确地计算算法的具体执行时间。这一事实是基于如下原因的：算法的执行时间，不但取决于算法是怎样实现的，也取决于算法是用什么语言编写的，用什么编译系统实现的，编译系统所生成代码的质量如何，在什么样的计算机上执行的，而不同计算机的性能、速度都不相同，致使在同一台计算机上执行，加法指令和乘法指令的执行时间差别就很大。人们无法对所有这些都作出准确的统计。,算法复杂性,实际上，在评估一个算法的性能时，也并不需对算法的执行时间作出准确的统计。这是因为人们在分析算法的性能，或把两个算法的性能进行比较时，对时间的估计是相对的，而不是绝对的。而且，人们所关心的并不是较小的输入规模，而是在很大的输入实例下算法的性能。 算法的运行时间经常和算法的输入规模成正比，而算法的输入规模又经常和循环次数存在着某种联系。对算法中的循环次数进行统计，可以很好地表示算法的运行时间。,鸡问题,鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，钱买鸡，问翁、母、雏各几何？ 算法A的程序代码如下： For x = To n For y = To n For z = To n If (x+y+z=n) And (5* x + 3 * y + z/3 = n) Then List1.AddItem Str(x) + “ “ + Str(y) + “ “ + Str(z) End If Next z Next y Next x,鸡问题,T(n)=(n+1)(n+1)(n+1)=n3+3n2+3n+1 当n增大时，例如当n=100万时，算法的执行时间主要取决于式的第一项，而第二、三、四项对执行时间的影响，只有它的几十万分之一，可以忽略不计。,算法复杂性渐进性态,复杂性的渐进性态 1).渐进性态 设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在一个函数 ，使得当n ,有 (T(n)- ) / T(n)0 称 是T(n)当 n 时的渐进性态或渐进复杂性. 例如 T(n)=3n2+4nlogn+7, 则 可以是（）？,算法复杂性渐进性态,复杂性的渐进性态 1)渐进性态 设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在一个函数 ，使得当n ,有 (T(n)- ) / T(n)0 称 是T(n)当 n 时的渐进性态或渐进复杂性。 假如运行时间T(n)=n3+2n2+5n，求时间复杂度？ 在数学上,T(n)与 有相同的最高阶项.可取 为略去T(n)的低阶项后剩余的主项.当n充分大时我们用 代替T(n)作为算法复杂性的度量,从而简化分析。,大O表示法,注意，随着n的增大，第一项的常数系数4对算法的执行时间也变得不重要，即，我们在对算法复杂性进行分析的时候，只要考察当问题的规模充分大时，算法复杂性在渐进意义下的阶。,大O表示法,设f(N)和 g (N) 是定义在正整数集上的正函数： 大O表示法 (算法运行时间的上界 )（最坏） 若存在正常数c和自然数N0，使得当 N N0 时,有f(N)cg (N)，则称函数 f(N )在N充分大时有上界, 且 g(N)是它的一个上界, 记为 f(N) = O(g (N), 也称 f(N) 的阶不高于g (N) 的阶。 例如：T(n)=n3+3n2+3n+1，求运行时间上界，用大O表示法表示。,算法的渐进复杂性,常见的多项式阶有: O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 常见的指数阶有: O(2n)O(n!)O(nn),算法的渐进复杂性的阶对于算法的效率有着决定性的意义: 多项式阶算法(有效算法):时间复杂性与规模N 的确定的幂同阶. 指数阶算法:时间复杂性与规模N 的一个指数函数同阶.,算法的渐进复杂性,