资源描述：
《绪论与算法效率分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第1章绪论与算法效率分析★算法概念★问题求解过程★重耍的问题类型★数据结构简要回顾★算法效率分析框架★渐近符号和基本效率类型★非递归算法效率分析★递归算法的效率分析★木章习题★参考教材★算法概念？为什么学习算法西华大学数学与计算机学院黄襄念《算法：计算的灵魂》算法不仅是计算机科学的一个分支，更是计算机科学的核心。而且，可以毫不夸张地说，它和绝大多数的科学、商业和技术是和关的。？学习要求熟悉掌握求解不同问题的各种标准算法，且具备设计新算法和分析算法效率的能力。计算机应用领域不断拓展，不断地学习、研究新的算法。？算法应用例1.博弈算法AI
2、（人工智能）和PR（模式识别）领域象棋、围棋、跳棋等机器着法研究。2.图像识别字符识别一一各国各民族文字、特殊字符、数理化符号等。生物特征识别一一如指纹、掌纹、虹膜、人脸、脚卬等。?数据结构与算法设计数据结构一一研究不同数据结构的作用和效率。西华大学数学与计算机学院黄襄念算法设计一一研究不同算法的实用性和效率。算法+数据结构=程序程序功能设计包括“行为设计”和“结构设计"行为设计一一求解问题的详细步骤，并用某种方法进行描述。（算法设计）结构设计一一算法所需的、高效的数据结构（计算机存储和组织数据的方式）有了算法和数据结构，以某种程序设
3、计语言予以实现一一程序？算法的定义什么是算法？没有一个公认的术语来描述。基本共识：算法是一系列解决问题的指令，对符合规范的输入，能在有限时间内获得预期的输出。图示如下问题算法西华大学数学与计算机学院黄襄念输入COMPUTER输出？算法的特点1.有穷性一一有限步内完成。2.确定性一一每一步是确定的，不能有二义性。3.可行性一一（1）每一步有意义。如：不能被零除。（2）每一步能求解八如：sin（x）>1不能求解。4.输入须检查输入值值域合法性。5.输岀一一输出问题的解，无输出的算法没有意义。*同一问题可能存在多种求解算法，其效率有差
4、异。如多种排序法。【例】求两个正整数m和n的最大公约数记号l：m和n的最大公约数gcd(m,n),表示能够整除ni和n的西华大学数学与计算机学院黄襄念最大正整数，FLm>n.记号2：mmodn表示m除以n的余数。？【算法1】欧氏算法一一公元前3世纪《几何原木》反复执行一一gcd(m,n)=gcd(n,mmodn)结束条件直到mmodn=0最大公约数最后的m例：gcd(60,24)=?结构化语言描述1.若n=0,输岀结果m,计算结束。否则，转2.思考1：m,n为负数时怎么处理？思考厶2个以上的数时如何处理？gcd(m,n)=gcd(60
5、,24)=gcd(24,12)=gcd(12,0)=122.r<—mmodn.3.mn,nr,转1.伪码描述算法Euclid（叫n）四华大学数学与计算机学院黄襄念//计算m和n最大公约数的欧氏算法//输入：两个不全为0的非负整数m>n//输出：m和n的垠大公约数whilen^Odo{r<—mmodnm<—nn<—rreturnm}问题2：如果in和n没有公约数，木算法是否支持这种情况？答：支持例：（63,22）—（22,⑼t（19,3）->（3,1）t（1,0）->1问题1：算法一定收敛吗?（n值最后一定为0?）观察分析（理论证明略）
6、每一次循环，mmodn,n值变小，但不会变成负数即n>r>0.整数n越来越小，最终变成0（算法收敛）?【算法2】连续整数检测算法算法设计思想：最大公约数不会大于m和n西华大学数学与计算机学院黄襄念tn).l.t是公约数？【Y】输出结果t(最大公约数)。【N】转2.2.t>1?【转1.[N]输出结果t.(t=?)例如(64,24)*24,23,22,…，12.当1=12时，算法结束结构化语言描述1.将min(m,n)赋值给t2.m除以t,若余数为0,转3。否贝山转43.n除以t,若余数为0,输出结果。否则：转44.t减
7、1,返回2注意，忽略了一些编程细节：输入值合法性检查。若输入m或n为0,算法出错。所以，输入值的值域检查很重要?【算法3】质因数算法算法设计思想西华大学数学与计算机学院黄襄念（屮学寻找最大公约数的方法）1.找岀m所有质因数一一不能再被整除的因数2.找出n所有质因数一一包括重复质因数如8=2x2x20个2重复）3.从1、2所得质因数屮找出所有的公因数一一包括重复的公因数4.第3步所得公因数相乘=结果一一最大公约数举例：求gcd（60,24）质因数分解式：60=2x2x3x524=2x2x2x3最大公约数为：gcd（60,24）=2x2x
8、3=12两个问题要解决1：求m和n所有质因数算法（用两个质因数数组存放）2：求两数组公共元素的算法（有序数组）问题2算法较易设计，请大家思考下面考虑问题1算法设计：求正整数N的全部质因数算法求正整数N全部质因数的算法算法
