算法分析与设计-第一章.ppt

1、算法分析与设计,授课教师：彭 卫 邮箱： 欢迎大家一起讨论！,参考书目,1. Anany Levitin (美) ,潘彦译. 算法设计与分析基础. 清华大学出版社,2004 2. 吴伟,方世昌等译. 算法设计技巧与分析. 电子工业出版社 3. D.E.Knuth,管记文译. 计算机程序设计技巧. 国防工业出版社.1978(第一卷),1982(第二卷) 4. 卢开澄. 计算机算法导引. 清华大学出版社,2000 5. 邹海明,余祥宣. 计算机算法基础. 华中理工大学出版社,1996 6. Jeffery J. McConell. Analysis of Algorithms: an active

2、 learning approach. 高等教育出版社,2003 7. T.H.Cormen C.E.Leiserson R.L.Rivest and C.Stein. Introduction to Algorithms, 2nd edition. 高等教育出版社,2002 8. 王晓东. 算法设计与分析. 清华大学出版社,2003 9 徐士良. C常用算法程序集. 清华大学出版社,1998 10. 王晓东. 计算机算法设计与分析. 电子工业出版社,2001,本课程所需知识,数据结构； 一门计算机语言C, Basic, Fortran,汇编,Delphi等； 一些高等数学方面的知识； 计算机

3、基础知识； 冷静的头脑+热诚的心；,何谓算法,算法的定义,算法的概念,几个容易造成含糊的定义,算法； 计算机语言； 数据结构：计算机中存储、组织数据的方式，数据的自然本性决定了其数据结构； 一种有趣的说法，即： 程序：算法+数据结构； 事实上，有一本书就被称之为程序=算法+数据结构。,算法设计与分析课程目的,1.了解计算领域中不同问题的一系列标准算法； 2.学会分析各种算法的效率； 3.学会设计新算法；,算法的特点,1. 算法的每一个步骤都必须清晰、明确； 2.同一个问题，可能有几种不同的算法来解决； 3. 针对同一个问题的不同算法，也许会出现不同的计算效率； 什么是计算计算效率？,一个例子,

4、如何求出两个整数：m和n的最大公约数 （什么是公约数？什么是最大公约数？） 公约数：能同时被整除的称为公约数； 例如：16/4=8，则4为10和22的公约数 24/4=6， 10能被整除的整数有： 22能被整除的整数有： 10和22的公约数有：？ 最大公约数是：？ 如何使用计算机程序来计算最大公约数？,一种最笨的、最简单、也是最可靠的计算最大公约数算法,算法的结构化表示（以便获得n和m的最大公约数）： 1.算出n的全部可被整除数； 2.算出m的全部可被整除数； 3.找出1，2步骤中的相同值； 4.找出3步骤中的最大值； 1. 知道如何编程实现吗？ 2. 伪代码表示？,次笨的方法,1.求出n和m

5、的最小值； 2.分别使用n和m来除以这个最小值； 3.若都能同时除尽，则可获得最大公约数，若不能，将这个数减1后再来除，直至同时除尽为止，即可找到最大公约数。 例如，求16和24的最大公约数； 1. 求出16和24中的最小值：16； 2. 则24/16,16/16,能否同时除尽？那么，16减1后再除，即24/15，15/15，能否除尽？还不行吗？那就再减1，当减到8时，24/8，16/8，你能想到16和24的最大公约数是多少吗？,次笨方法的结构化说明,1. 求出n和m的最小值，t=min(n,m); 2. 检查t值，如果t=0，则发出错误信息；如 ，则进行下一步； 3. 计算n/t，如为整数，

6、可表示为mod(n/t)=0，则转向4；否则，转向5； 4. 如果mod(m/t)=0，则停止并返回值t；否则，转向5； 5. t=t-1并转向2； 要是同学们没有问题，则谈谈伪代码的时候终于来到了！,伪代码,官方的说法：伪代码是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。 介于自然语言与编程语言之间。 我的说法：就是为了让大家有一个共同语言，作用类似于世界语，以便让我们未来的程序师们可以互相理解； 幸运的是，伪代码并没有统一的规范，也即是可以按照个

7、人的意思来编制。,可悲的例子，可恨的计算机语言们！（一个判断例子）,IF (p=2) OR (j3) THEN ERROR; ELSE P=3; Pascal语言 IF (p=2) |(j3) ERROR; ELSE P=3; C 语言 IF (p=2) | (j3) ERROR; ELSE P=3; end Matlab语言,伪代码(All computer languages involving：),赋值语句 数值判断语句：等于，不等于，大于，小于； 逻辑判断语句：与，或，非，异或； 分支语句：假如，则 循环语句：在范围内，重复；当满足，则重复； Break; /注释语句,次笨方法的伪代码

8、说明,欧几米德算法（较优）,求出 ： t=mod(m/n); 再求出：t1=mod(n/t); 循环，直到 tm=mod(tm-1/tm-2)=0; 此时，tm-2为最大公约数； 例如，m=64,n=24; t1=mod(64/24)=16;mod(24/16)=8;mod(16/8)=0;这样，可知最大公约数是8；,欧几米德算法伪码说明,比较这3种算法,1.时间上，更快的是？ 2.内存， 更少的是？ 我们可以得到的结论：？,算法的设计及分析过程,一些重要的问题类型,排序 查找 串处理 图问题 组合问题 几何问题 数值问题,基本数据结构,数组 链表 栈 树 图 计算机是对数据的操作，数据的组织

9、方法（数 据结构）是由要解决的问题决定的，可以决定 算法的效率和应用。 数据结构=数据+数据之间的关系,几个例子,一个学生的学号，可以使用什么类型的数据结构？ 一个班级内的学生学号，可以使用什么类型的数据结构表示？查询？排序？ 班级内按照学号顺序来进行体检，可以使用什么类型的数据结构表示？查询？排序？ 班级内按照省份、市、县进行分类，可以使用什么类型的数据结构表示？查询？排序？ 班级内按照座位号进行分类，可以使用什么类型的数据结构表示？查询？排序？,数组， 例如：一个已知长度的字符串,链表，例如：一个长度变化的字符串,图，例如：一个计算机网络,图，例如：一个族谱,所有数据结构的基本操作,插入新

10、数据 删除新数据 更新新数据 查找 排序,算法的效率,先由一个例子开始： 在一个序列中查找一个值： 例如， 在13， 57，89，0，63，43，4，7，8，4，36，5，72，34中找出5，能否写出查找的伪代码？,伪代码,能否指出，这里的计算量是多少？ 什么情况下，效率最高？ 什么情况下，效率最低？ 计算量与字符串长度的关系？,几种特殊情况,1. 5 ， 57，89，0，63，43，4，7，8，4，36， 13 ，72，34 2. 13 ， 57，89，0，63，43，4，7，8，4，36， 5 ，72，34 3. 57，89，0，63，43，4，7，8，4，36， 13 ，72，34 ，

11、5 ,结论,算法效率与所用时间和资源有关； 算法的效率与输入规模有关； 算法的效率与输入的分布和待解决问题有关； 一般使用最坏情况作为性能的度量,例子：冒泡算法（伪代码）,能否告诉我，有多少次比较？即有多少次：,冒泡程序的运算量,共有多少次比较操作？ 当i=1时，有多少次比较操作：n-1 当i=2时，有多少次比较操作：n-2 当i=2时，有多少次比较操作：n-3 当i=n-1时.有多少次比较操作：1 则总的比较操作是：,公式的简化,现代计算机所处理的输入规模都很大，因此为了简化计算，实际中可以做如下简化： 1.计算公式中的常系数可以忽略；例如： 2.当存在多阶项时，忽略低阶项，保留高阶项： 例如：,一阶n和二阶(1-100),一阶n和二阶(1-10000),二阶 和二阶(1-10),二阶 和二阶(1-1000),(1-1000),算法的效率比较,1.一个算法的运行时间，一般与输入值属性有关； 2. 为了更好地细化比较算法的优劣，一般预先将算法分成若干类型； 例如，,算法分析的渐进分析,当你已经得到了你所设计算法的计算量时，如何与其它人的算法做比较呢？ 答案就是：使用算法的渐进分析； 注意，这里的渐进分析方法是全世界所有程 序员们所公认的方法，不是带有中国特色或 者四川、成都特色的分析方法。,定义1 表示法(thete-notation),从上面的中庸且晦涩难懂的定