算法第1章绪论与算法效率分析

《算法第1章绪论与算法效率分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析授课教师：钟世芬电话：87720985课件制作：黄襄念老师感谢黄老师的辛劳制作！参考教材参考教材作者：（美）AnanyLevitin译者：潘彦出版社：清华大学丛书名：国外经典教材·计算机科学与技术定价：45.00￥市场价：36.00￥第1章绪论与算法效率分析算法的概念算法问题求解过程重要的问题类型基本数据结构回顾算法效率分析框架渐进符号和基本效率类型非递归算法效率分析递归算法效率分析本章习题参考教材算法的概念算法的概念为什么学习算法：DavidHarel在《算法：计算的灵魂》中的描述：算法不仅是计算机科学的一个分支，更是计算机科学的核心。而且，可以毫不夸张地说，它和绝大多数的

2、科学、商业和技术是相关的。对于一个即将从事计算机专业的人士来说，学习算法都是必要的，了解计算领域中不同问题的一系列标准算法，并且具备设计新算法和分析算法效率的能力。随着计算机应用领域（工作和生活）的不断拓展，需要不断地学习和研究算法。算法应用领域例：（1）工作方面：AI（人工智能）、PR（模式识别）算法的研究。（2）生活方面：机器博弈算法的研究（象棋、围棋等）。算法设计与数据结构算法设计与数据结构：数据结构主要关心的是不同的数据结构（逻辑的）在计算机解题中的作用和效率，而算法设计与分析关心的是不同的算法设计的实用性和效率。这使得这两门课程在某种程度上有所重叠，但无法相互代替。算法＋数据结构

3、＝程序程序功能设计包括：行为设计和结构设计。行为设计：对要解决的问题，提出达到目的所需要实施的步骤序列。并对这些步骤加以必要细化，用某种方法进行描述，其结果就是算法。——算法设计（得到具体问题的算法）结构设计：设计算法所需要的高效的数据结构。有了好的算法和数据结构，以某种程序设计语言予以实现——程序。算法的定义：什么是算法？没有一个公认的用语来描述。针对其含义的基本共识：算法是一系列解决问题的清晰的指令，对符合一定规范的输入，能在有限时间内获得所要求的输出。图示如下：算法的几个特点算法的几个特点：（定义的内涵）（1）有穷性：有限时间内完成。如计算n！；穷举法解旅行商问题。（2）确定性：算法

4、的每一步必须是确定的，不能有两可的解释。（3）可行性：一是每一步必须是有意义的，如约束优化的可行域判定；二是每一步能够达到预期目的。如求sinx>1的解不可行。（4）输入：输入的值域必须仔细定义；（下例可见）（5）输出：获得问题的解，无输出的算法是没有意义的。（多种）（6）同一问题求解，可能存在几种不同的算法，执行效率有所差异。COMPUTER问题算法输入输出算法一：欧氏几何求最大公约数算法例：求两个不全为零的非负整数m和n的最大公约数记号一：记m和n的最大公约数为gcd(m,n)，表示能够整除m和n（即余数为零）的最大正整数。记号二：mmodn表示m除以n所得余数。算法一：欧几里得（公元

5、前3世纪）所著《几何原本》解法重复执行下列等式，直到mmodn（余数）等于0：（结束条件）gcd(m,n)=gcd(n,mmodn)最后m的取值就是最大公约数。例如gcd(60,24)计算如下：gcd(m,n)=gcd(60,24)=gcd(24,12)=gcd(12,0)=12（等式）欧氏算法的结构化描述：1.如果n=0，返回m值为结果输出，计算结束！否则，转2步；2.r=mmodn;（赋值）3.m=n,n=r（赋值）,转1步。（变量交换）欧氏算法的伪码描述欧氏算法的伪码描述：（伪码较流程图描述更为先进，建议采用）模块：Euclid(m,n)//计算m,n最大公约数的欧氏算法//输入：两

6、个不全为0的非负整数m>n//输出：m，n的最大公约数whilen≠0do{r←mmodnm←nn←r}returnm问题一：该算法一定收敛吗？（是否会停止循环，输出结果呢）观察分析：设m>n，r=mmodn每一次循环（mmodn）后，新n值会变小，但不会变成负数；即除数n大于余数r（n>r>0）。余数作为下一轮新n值（n←r），因此，n越来越小，最终变成0。问题二：如果m和n没有公约数呢？本算法是否支持这种情况。答案：支持。例子：(63,22)→(22,19)→(19,3)→(3,1)→(1,0)→1算法二：连续检测算法算法二：连续整数检测算法连续检测算法的设计思想：根据定义，最大公约数

7、不会大于m和n，设t=min{m,n}。我们现在开始检测t是否为公约数：若是公约数，那么t就是最大公约数；否则，我们就将t简单地减1（t=t-1或t-=1或t--），继续判定t是否为公约数：若是则输出结果；否则继续上述循环，即t继续减下去，最终减到1为止。例如(64,24)，先用t=24尝试，然后是23，22，……，当尝试到12时，算法结束。（整除的判定，即余数为0）连续检测算法的结构化描述：1.将min{m,n}赋值给