算法第1章算法概述详解优秀PPT.ppt

《算法第1章算法概述详解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《算法第1章算法概述详解优秀PPT.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算法设计与分析计算机算法设计与分析计算机算法设计与分析主讲人：袁运浩E-mail:yhyuanjiangnan.edu 计算机科学与技术系江南高校物联网工程学院1计算机算法设计与分析l 课时数：48节l 上课：1-16周l 成果：卷面成果（70%）+平常成果（30%）l 教材：计算机算法设计与分析,王晓东,电子工业出版社,2012l参考书：l (1)算法设计与分析,郑宗汉,郑晓明,清华高校出版社l (2)算法导论,Thomas H.Cormen编著.潘金贵等译,机械工业出版社2计算机算法设计与分析3主要内容介绍第第1 1章章算法概述算法概述第第2 2章章递归与分治策略递归与分治策略第第3

2、 3章章动态规划动态规划第第4 4章章贪心算法贪心算法第第5 5章章回溯法回溯法第第6 6章章分支限界法分支限界法3计算机算法设计与分析4意念与现实意念与现实(1):一个例子一个例子给你一个无限容积的罐子和无限个球，球从给你一个无限容积的罐子和无限个球，球从1 1起先连续编号起先连续编号 在在差差1 1分分钟钟到到零零点点时时：将将标标号号为为1 11010的的1010个个球球放放进进罐罐子子，然后将然后将1010号球从罐子里拿出。号球从罐子里拿出。在在差差1/21/2分分钟钟到到零零点点时时：将将标标号号为为11112020的的1010个个球球放放进进罐罐子，然后将子，然后将2020号球从罐

3、子里拿出。号球从罐子里拿出。在在差差1/41/4分分钟钟到到零零点点时时：将将标标号号为为21213030的的1010个个球球放放进进罐罐子，然后将子，然后将3030号球从罐子里拿出。号球从罐子里拿出。就就这这样样将将游游戏戏进进行行下下去去。假假定定放放球球和和取取球球不不占占时时间间，请请问问，当时钟指向零点时，罐子里还剩多少个球？当时钟指向零点时，罐子里还剩多少个球？4计算机算法设计与分析5意念与现实意念与现实(2):一个例子一个例子这这个个答答案案很很干干脆脆：无无穷穷多多个个球球！全全部部编编号号不不是是10n10n（n1n1）的的球球在在放放进进罐罐子子里里后后就就不不会会再再拿拿

4、出出来来；而而在在到到达达零零点点之之前前这这种种放放球球、取取球球的的次次数数是是无无限限的的。因因此此，罐罐子子里里面面的的球球在在零零点点时将是多数个。时将是多数个。你很确信这个答案吗？你很确信这个答案吗？现在来让我们变更拿球的方式，将每次拿10、20、30号球分别变为拿1、2、3号球，即第x次拿球，所拿出来的球的编号是x。结果又会怎样呢？这个时候，奇妙的事情发生了。这个罐子里面的球数将为0。对于随意一个球，设其编号为n，则在差(1/2)n-1分钟到零点时该球将被取出。也就是说，对于随意球n，在零点时它都不在罐子里。因此，零点时罐子里球的个数为0。5计算机算法设计与分析6意念与现实意念与

5、现实(3):一个例子一个例子对对于于有有些些人人来来说说，这这个个答答案案似似乎乎不不行行接接受受。但但又又的的确确找找不不到到驳斥的方法。你能找出来吗？驳斥的方法。你能找出来吗？或或许许这这个个答答案案是是合合理理的的，因因为为拿拿球球依依次次的的变变更更使使得得算算法法发发生生了变更，即我们事实上探讨的是两个算法。了变更，即我们事实上探讨的是两个算法。可可细细致致一一想想又又觉觉得得不不对对，因因为为两两个个算算法法都都是是每每次次放放进进 10 10 个个球球，拿拿出出1 1个个球球，即即从从根根本本上上说说，这这是是两两个个一一样样的的算算法法，怎怎么会有截然相反的结果呢么会有截然相反

6、的结果呢?6计算机算法设计与分析7意念与现实意念与现实(4):一个例子一个例子假假如如我我们们再再次次变变更更试试验验中中拿拿球球的的方方式式，将将拿拿某某个个特特定定标标号号的的球球改改为为取取出出随随意意标标号号的的球球，即即在在差差1 1分分钟钟到到零零点点时时，将将标标号号为为1 11010的的1010个个球球放放进进罐罐子子，然然后后从从罐罐子子里里随随意意拿拿出出一一个个球球；在在差差1/21/2分分钟钟到到零零点点时时，将将标标号号为为11112020的的1010个个球球放放进进罐罐子子，然然后后从从罐罐子子里里随随意意拿拿出出一一个个球球；在在差差1/41/4分分钟钟到到零零点

7、点时时，将将标标号号为为21213030的的1010个个球球放放进进罐罐子子，然然后后从从罐罐子子里里随随意意拿拿出出一个球一个球这种拿球方式又将产生何种结果呢？这种拿球方式又将产生何种结果呢？答案是仍旧是答案是仍旧是0 0太太不不行行思思议议了了吧吧！这这三三个个本本质质相相同同的的算算法法怎怎么么有有如如此此匪匪夷夷所所思思的的结结果果呢呢？假假如如非非要要说说这这三三个个算算法法有有什什么么不不同同，就就是是拿拿球球时的标号不同。时的标号不同。但莫非标号的不同使最终球的数量发生了变更但莫非标号的不同使最终球的数量发生了变更?7计算机算法设计与分析8意念与现实意念与现实(5):一个例子一个

8、例子没没错错，就就是是这这个个标标号号对对结结果果产产生生了了深深远远影影响响。从从某某种种意意义义上上说说，标标号号是是虚虚的的，它它只只存存在在于于我我们们的的想想象象中中，但但的的确确对对现现实实结结果果产产生生了了影影响响，即即我我们们的的思思维维使使算算法法发发生生了了变变更更。或或许许从从另另一一个个角角度度来来看看，这这个个问问题题就就是是：没没有有就就是是无无穷穷，无无穷穷就就是是没没有有。它它们们之之间间或或许许根根本本没没有有什什么么不不同同，它它们们的的不不同同只只存存在在于于人人们们的的想想象象或或者者意意念念中中。或或许许这这是是为为什什么么无无穷穷的的符符号号 是是

9、由由两两个个0 0连连接接而而成成的的，从从左左右右两两面面看看都都是是无无有有，而而从从中中间间看看则则是无穷。是无穷。从这个意义上说，算法是一种思维方式（算法是一种思维方式（Algorithmic Thinking），或者说一种哲学），或者说一种哲学。8计算机算法设计与分析一个最简洁的算法：一个最简洁的算法：1.起床起床2.吃早点吃早点3.上早自习上早自习4.上课上课5.吃午饭吃午饭6.上课上课7.吃晚饭吃晚饭8.上晚自习上晚自习9.睡觉睡觉9计算机算法设计与分析10计算机算法设计与分析1111计算机算法设计与分析1212计算机算法设计与分析131.1.2 算法及其重要性质算法及其重要性质

10、 算法：是指解决问题的一种方法或一个过程。算法：是指解决问题的一种方法或一个过程。算法是由若干条指令组成的有穷序列，满足性质：算法是由若干条指令组成的有穷序列，满足性质：(1)(1)输入：有输入：有0 0个或多个由外部供应的量作为算法的输入。个或多个由外部供应的量作为算法的输入。(2)(2)输出：算法产生至少一个量作为输出。（输出：算法产生至少一个量作为输出。（1 1个或多个）个或多个）(3)(3)确定性：组成算法的每条指令是清晰，无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。(4)(4)有有限限性性：算算法法中中每每条条指指令令的的执执行行次次数数是是有有限限的的，执执行行每每条指令

11、的时间也是有限的。条指令的时间也是有限的。13计算机算法设计与分析14算法与程序的区分算法与程序的区分 程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)。例例如如，操操作作系系统统是是一一个个在在无无限限循循环环中中执执行行的的程程序序，因因而而不不是一个算法。是一个算法。操操作作系系统统的的各各种种任任务务可可看看成成是是单单独独的的问问题题，每每一一个个问问题题由由操操作作系系统统中中的的一一个个子子程程序序通通过过特特定定的的算算法法来来实实现现。该该子子程程序得到输出结果后便终止。序得到输出结果

12、后便终止。14计算机算法设计与分析151.1.3 算法的描述方法算法的描述方法15计算机算法设计与分析1616计算机算法设计与分析1717计算机算法设计与分析1818计算机算法设计与分析1919计算机算法设计与分析2020计算机算法设计与分析2121计算机算法设计与分析2222计算机算法设计与分析2323计算机算法设计与分析2424计算机算法设计与分析251.2 算法困难性分析算法困难性分析25计算机算法设计与分析26算法困难性算法困难性 算算法法困困难难性性的的凹凹凸凸体体现现在在运运行行该该算算法法所所须须要要的的计计算算机机资资源源的的多多少少上上：所所需需资资源源越越多多，算算法法困困

13、难难性性越越高高；反反之之，所所需需资资源源越少，算法困难性越低。越少，算法困难性越低。算法的困难性有：时间困难性与空间困难性算法的困难性有：时间困难性与空间困难性 时间困难性：算法运行所须要的时间资源量时间困难性：算法运行所须要的时间资源量 空间困难性：算法运行所须要的空间资源量空间困难性：算法运行所须要的空间资源量 选选用用算算法法应应遵遵循循的的一一个个重重要要原原则则：当当给给定定的的问问题题有有多多种种算算法法时，选择其中困难性最低者时，选择其中困难性最低者 26计算机算法设计与分析27算法困难性算法困难性(1)时间/空间资源的量只依靠于算法要解的问题的规模、算法的输入和算法本身的函

14、数。分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示困难性，那么，应当有C=F(N,I,A)一般把时间困难性和空间困难性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在困难性函数名当中）27计算机算法设计与分析28算法困难性算法困难性(2)设一台计算机所供应的元运算有k种，分别记为O1,O2,Ok同时，设每执行一次这些元运算所须要时间分别为t1,t2,tk对于给定的算法A，设用到元运算Oi的次数为ei=ei(N,I),那么明显，对于不同的明显，对于不同的N和和I，T(N,I)有多种可能的值。有多种可能的值。对于给定问题规模，算法

15、对于给定问题规模，算法A的时间困难性究竟是多的时间困难性究竟是多少？少？28计算机算法设计与分析291.2.1 最好、最坏与平均状况最好、最坏与平均状况最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：其中D DN N是规模为N的合法输入的集合合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入.实践表明：可操实践表明：可操作性最好且最有作性最好且最有实际价值的时间实际价值的时间困难性困难性 是DN中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。29计算机算法设计与分析3030计算机算法设计与分析3131计算机算

16、法设计与分析3232计算机算法设计与分析算法渐近困难性算法渐近困难性设T(N)是算法A的困难性函数，一般满足：当 N+，T(N)+，即 对于T(N)，若存在t(N)，使得当N+，T(N)-t(N)/T(N)0，那么就说t(N)是T(N)的渐近性态，或称为算法A的渐近困难性。在数学上，t(N)是T(N)的渐近表达式，是T(N)略去低阶项留下的主项。例如，t(N)比T(N)简洁。33计算机算法设计与分析341.2.2 渐近符号渐近符号算法复杂性在渐近意义下的阶：渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数正函数。O的定义的定义：如果存在正的常数C和自然数N0，使得当NN0

17、时有f(N)Cg(N)，则称函数f(N)当N充分大时有上界，且g(N)是它的一个上界上界，记为f(N)=O(g(N)。即f(N)的阶不高于的阶不高于g(N)的阶的阶。例如：（1）由于对全部的N1有3N4N，则3N=O(N)（2）由于对全部的N1有N+10241025N，则N+1024=O(N)（3）由于对全部的N1有N2 N3，则N2=O(N3)（4）由于对全部的N10有2N2+11N-103N2，则2N2+11N-10=O(N2)34计算机算法设计与分析351.2.2 渐近符号渐近符号 依据O的定义，简洁证明它有如下运算规则：(1)O(f)+O(g)=O(max(f,g)；(2)O(f)+O

18、(g)=O(f+g)；(3)O(f)O(g)=O(fg)；(4)假如g(N)=O(f(N)，则O(f)+O(g)=O(f)；(5)O(Cf(N)=O(f(N)，其中C是一个正的常数；(6)f=O(f)。35计算机算法设计与分析361.2.2 渐近符号渐近符号 的定义：假如存在正的常数的定义：假如存在正的常数C C和自然数和自然数N0N0，使得当，使得当N N N0N0时有时有f(N)f(N)Cg(N)Cg(N)，则称函数，则称函数f(N)f(N)当当N N充分大时下有界，充分大时下有界，且且g(N)g(N)是它的一个下界，记为是它的一个下界，记为f(N)=(g(N)f(N)=(g(N)。即。即

19、f(N)f(N)的阶的阶不低于不低于g(N)g(N)的阶。的阶。的定义的定义：定义f(N)=(g(N)当且仅当f(N)=O(g(N)且f(N)=(g(N)。此时称f(N)与g(N)同阶同阶。o o的定义：对于随意给定的的定义：对于随意给定的0 0，都存在正整数，都存在正整数N0N0，使，使得当得当N N N0N0时有时有f(N)/g(N)f(N)/g(N),则称函数则称函数f(N)f(N)当当N N充分大时的阶充分大时的阶比比g(N)g(N)低，记为低，记为f(N)=o(g(N)f(N)=o(g(N)。例如，例如，4NlogN+7=o(3N2+4NlogN+7)4NlogN+7=o(3N2+4NlogN+7)。36计算机算法设计与分析3737计算机算法设计与分析3838计算机算法设计与分析3939计算机算法设计与分析4040计算机算法设计与分析4141计算机算法设计与分析4242计算机算法设计与分析4343计算机算法设计与分析4444计算机算法设计与分析4545计算机算法设计与分析4646计算机算法设计与分析4747