《算法设计与分析基础知识.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析基础知识.ppt（115页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、主讲：李淑琴L2013.9课程简介（课程设置意义）nDonald Donald E.knuthE.knuth（19741974年获图灵奖）年获图灵奖）：计算机科学就是：计算机科学就是算法的研究算法的研究n算法是计算机科学的核心，在众多的计算机应用领域也充算法是计算机科学的核心，在众多的计算机应用领域也充满了各种算法满了各种算法 n算法是程序设计的精髓，程序设计的实质就是构造解决问算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言题的算法，将其解释为计算机语言 n掌握算法分析的基本方法与算法设计的基本策略是一个软掌握算法分析的基本方法与算法设计的基本策略是一个软件工
2、作者的必备条件件工作者的必备条件n本课程是计算机科学与技术专业的专业必修课本课程是计算机科学与技术专业的专业必修课课程简介（课程设置意义）n李开复李开复 谷歌公司担任全球副总裁兼大中华区总裁、微软谷歌公司担任全球副总裁兼大中华区总裁、微软公司全球副总裁。李博士于公司全球副总裁。李博士于19981998创办微软中国研究院创办微软中国研究院n写篇文章写篇文章“算法的力量算法的力量”n算法是计算机科学领域最重要的基石之一算法是计算机科学领域最重要的基石之一n编程语言虽然该学，但是学习计算机算法和理论更重要，编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离
3、其宗的因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论是那些算法和理论n既能用科学家的严谨思维来求证，也能用工程师的务实手既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题段来解决问题而这种思维和手段的最佳演绎就是而这种思维和手段的最佳演绎就是“算算法法”。n有人也许会说：有人也许会说：“今天计算机这么快，算法还重要吗今天计算机这么快，算法还重要吗?”?”其实永远不会有太快的计算机，因为我们总会想出新的应其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，
4、价格也在不断下降。可我们不要忘记，需要在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先造出大量数据（照片，视频，语音，文本等等）。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。增长。互联网的信息流量和日志容量也在飞快增长。n每天每天GoogleGoogle的网站要处理十亿个以上的搜索，的网站要处理十亿个以上的搜索，GMailGMail要储要
5、储存几千万用户的存几千万用户的2G2G邮箱，邮箱，Google EarthGoogle Earth要让数十万用户同要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。每个用户。如果没有好的算法，这些应用都无法成为现实。课程简介（课程目的）本课程主要介绍计算机科学领域及其应用领域有本课程主要介绍计算机科学领域及其应用领域有代表性算法设计方法，同时介绍算法分析的基础知代表性算法设计方法，同时介绍算法分析的基础知识，旨在培养学生分析问题和解决问题的能力。通识，旨在培养学生分析问题和解决
6、问题的能力。通过本课程的学习，使学生过本课程的学习，使学生掌握算法设计的基本方法掌握算法设计的基本方法，熟悉算法分析的基本技术熟悉算法分析的基本技术，并能熟练运用一些常用，并能熟练运用一些常用算法解决实际问题，为学生进一步学习奠定良好的算法解决实际问题，为学生进一步学习奠定良好的基础基础。教材与参考书n教材自编教材“算法设计与分析”吴敏华n参考书n算法设计技巧与分析 沙特M.H.Alsuwaiyel著 吴伟昶 方世昌等译 电子工业出版社n算法设计与分析 郑宗汉 郑晓明 清华大学出版社n计算机算法基础 余祥宣等 华中理工大学出版社n计算机算法：设计与分析引论 美S.巴斯著 朱洪等译 复旦大学出版
7、社n算法分析与设计 王晓东 清华大学出版社n课时安排课时安排授课：授课：5454学时，学时，1-181-18周，周一下午（周，周一下午（6-86-8节）节）n成绩评定：成绩评定：课堂参与（课堂参与（1010分）、作业（分）、作业（3030分）、考试成绩（分）、考试成绩（6060分）分）n考试方式：考试方式：闭卷闭卷,笔试笔试考试、课时安排主要内容介绍n第1章算法设计与分析基础n第2章递归与分治策略n第3章动态规划n第4章贪心算法n第5章回溯法n第6章分支限界法n第7章随机化算法nNP-完全问题n图的遍历第1章 算法设计与分析基础学习要点学习要点:u理解算法的概念。理解算法的概念。u理解什么是程
8、序，程序与算法的区别和内在联系。理解什么是程序，程序与算法的区别和内在联系。u掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。u掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。u掌握算法分析常用数学方法掌握算法分析常用数学方法1.1 引言引言算法的定义和特征算法的定义和特征n算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。n算法算法是由若干指令组成的有穷序列是由若干指令组成的有穷序列，满足性质：，满足性质：10算法五个重要特征：算法五个重要特征：n确切性确切性:算法的每一步骤必须有确切的定义；算法的每一步骤必须有确切的定义；n输入：输入：零个或多个外
9、部量作为输入，所谓零个或多个外部量作为输入，所谓0 0个输入是个输入是指算法本身给定了初始值；指算法本身给定了初始值；n输出：输出：至少产生一个量作为输出。以反映对输入数据至少产生一个量作为输出。以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；加工后的结果。没有输出的算法是毫无意义的；n可行性：可行性：算法中有待实现的运算都是基本运算。算法算法中有待实现的运算都是基本运算。算法原则上能够精确地运行，而且人们用笔和纸做有限次原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。运算后即可完成。n有穷性有穷性：算法中每条指令的执行次数是有限的，执行：算法中每条指令的执行次数是有限
10、的，执行每条指令的时间也是有限的。每条指令的时间也是有限的。30003000年也行年也行算法与程序算法与程序程序与算法的不同：程序与算法的不同：（1 1）程序是算法用某种程序设计语言的）程序是算法用某种程序设计语言的 具体实现具体实现。（2 2）程序可以不满足算法的有限性。）程序可以不满足算法的有限性。-性质性质5 5算法与程序算法与程序n n例如操作系统，是一个在无限循环中执行的程序，例如操作系统，是一个在无限循环中执行的程序，例如操作系统，是一个在无限循环中执行的程序，例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。因而不是一个算法。因而不是一个算法。因而不是一个算法。n n
11、操作系统的各种任务可看成是单独的问题，每一个操作系统的各种任务可看成是单独的问题，每一个操作系统的各种任务可看成是单独的问题，每一个操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来问题由操作系统中的一个子程序通过特定的算法来问题由操作系统中的一个子程序通过特定的算法来问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。实现。该子程序得到输出结果后便终止。实现。该子程序得到输出结果后便终止。实现。该子程序得到输出结果后便终止。问题求解问题求解(Problem Solving)证明正确性分析算法设计程序n理解问题理解问题n精确解或
12、近似解精确解或近似解n选择数据结构选择数据结构n算法设计策略算法设计策略n设计算法设计算法例：旅行商问题设一个商人一天之内要到五个城市去推销货物。已知一个城市到其它城市的花费，希望从某个城市出发，走遍其它4个城市，找到花费最小的路线。n已知：5个城市的道路通畅情况和相应的花费n了解：出发城市，一天是否能走遍5个城市n 是否考虑货物推销的花费n 每个城市是否只能到达一次n 最后是否回到出发城市n 城市之间是否有优先到达的关系n求解：依次通过5个城市的顺序，要求花费之和最小n模型的选择：无向图-用5个点表示5个城市，用边表示5个城市之间的道路，用数组表示花费矩阵。n算法设计：n假设有n个城市n对n
13、个城市从1 到n编号，出发地为城市1n实际找一个从2到n的一个排列，一个排列对应一条路线n可从所有排列中找一个花费最小的路线程序实现程序实现nscanf(n,C);ni=1;min=;nwhile(i=(n-1)!)n 形成从2到n的第 i 种排列；n 计算这种排列的费用cost；n if(cost min)n min=cost;记录这种排列；n i+;n n打印最小花费路线及费用。例2 证明在n（n 2）个人的团体中，总有 两个人在此团体中恰好有相同个数的朋友。n分析：建立数学模型。以顶点代表人，二人如果是朋友，则在代表他们的顶点间连上一条边，这样可得无向简单图G，每个人的朋友数即图中代表他
14、的顶点的度数，于是问题转化为图中的命题：n阶无向简单图G中必有两个顶点的度数相同。n解：用反证法，设G中各顶点的度数均不相同，则度数列为0，1，2，n-1，说明图中有孤立顶点，这与有n-1度顶点相矛盾（因为是简单图，其中的n-1度顶点必与其它n-1个顶点均邻接），所以必有两个顶点的度数相同。1.1.3 描述算法描述算法描述算法有多种方式描述算法有多种方式:1.1.可以采用可以采用伪代码伪代码(PseudocodePseudocode)来描述算法来描述算法 伪代码是伪代码是介于自然语言和程序设计语言之间的方法介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以它采
15、用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。结合自然语言来设计。伪代码伪代码优点：优点：表达能力强，抽象性强，容易理解表达能力强，抽象性强，容易理解 使用伪代码的使用伪代码的目的目的是为了使被描述的算法可以容易地是为了使被描述的算法可以容易地以任何一种编程语言实现以任何一种编程语言实现伪代码的使用（1）n伪代码伪代码(PseudocodePseudocode)是一种算法描述语言。使用伪代码的目的是为了是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)(Pascal
16、,C,Java,etc)实现。因此，伪代码必实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自须结构清晰，代码简单，可读性好，并且类似自然语言。然语言。n书中所用部分伪代码的语法规则书中所用部分伪代码的语法规则 （1 1）在伪代码中，每一条指令占一行，指令）在伪代码中，每一条指令占一行，指令后不跟任何符号（后不跟任何符号（PascalPascal和和C C中语句要以分号结尾）中语句要以分号结尾）；伪代码的使用（2）（2 2）使用与结构化程序语言类似的结构，如）使用与结构化程序语言类似的结构，如if-if-then-else then-else、forfor、whilewhile等；
17、书写上的等；书写上的“缩进缩进”表示程序中的分支结构。同一模块的语句有相表示程序中的分支结构。同一模块的语句有相 同的缩进量，次一级模块的语句相对其父模块同的缩进量，次一级模块的语句相对其父模块 缩进量缩进量（3 3）在伪代码中，变量名和保留字不区分大小）在伪代码中，变量名和保留字不区分大小 写，这一点和写，这一点和PascalPascal相同，与相同，与C C或或C+C+不同；不同；（4 4）在伪代码中，变量不需声明，但变量局部于特）在伪代码中，变量不需声明，但变量局部于特 定过程，不能不加显示的说明就使用全局变量定过程，不能不加显示的说明就使用全局变量伪代码的使用（3）（5 5）数组元素的
18、存取有数组名后跟）数组元素的存取有数组名后跟“下标下标”表表 示。例如示。例如AjAj指示数组指示数组A A的第的第j j个元素。符号个元素。符号 “”用来指示数组中值的范围。用来指示数组中值的范围。例：例：A1A1jj表示含元素表示含元素A1,A2,A1,A2,Aj Aj的子数组；的子数组；(6)(6)赋值语句用符号赋值语句用符号表示，表示，例例B1.n A1.nB1.n A1.n (7)(7)函数值利用函数值利用 “return(return(函数返回值函数返回值)”语句语句 来返回来返回 2.采用高级语言描述算法描述算法高级程序设计语言的主要高级程序设计语言的主要好处是好处是：（1 1）
19、高级语言更接近算法语言，易学、易掌握，一般工程技）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；术人员只需要几周时间的培训就可以胜任程序员的工作；（2 2）高级语言为程序员提供了结构化程序设计的环境和工具，）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；使得设计出来的程序可读性好，可维护性强，可靠性高；（4 4）把繁杂琐碎的事务交给编译程序，所以自动把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造
20、性劳动，提高程序质量。精力从事更重要的创造性劳动，提高程序质量。（3 3）高级语言不依赖于机器语言，与具体的计算）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、机硬件关系不大，因而所写出来的程序可植性好、重用率高；重用率高；1.3 算法复杂性分析算法复杂性分析n算法复杂性算法复杂性=算法运行所需要的计算机资源的算法运行所需要的计算机资源的量量n需要时间资源的量称为需要时间资源的量称为时间复杂性时间复杂性，需要的空间，需要的空间 资源的量称为资源的量称为空间复杂性空间复杂性n算法复杂性算法复杂性依赖于算法要解的依赖于算法要解的问题的规模问题的规模、算法的算法的
21、输入输入和和算法本身算法本身。1.2.1 算法复杂性分析的必要性算法复杂性分析的必要性例：搜索。例：搜索。给定已经排好序的n个元素,现在要在这些元素中找出一个特定的元素x。可以用顺序搜索和二分搜索。算法算法1.1 Linearseach（顺序搜索（顺序搜索)输入：n个元素的数组A1.n和元素x输出：如果x=Aj,1j n,则输出j,否则输出0 1.j=1；2.while(jn)and(xAj)3.j=j+1 4.end while 5.if x=Aj then return j else return 0 定义：定义：查找算法的平均查找长度平均查找长度 (Average Search Leng
22、th)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中:n 为表长，Pi 为查找表中第i个记录的概率，且 ，Ci为找到该记录时，曾和给定值比较过的关键字的个数。分析顺序查找的时间性能在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表顺序表而言，Ci=iASL=P1+2 P2+(n-1)Pn-1+nPn1.2.1 算法复杂性分析的必要性算法复杂性分析的必要性算法算法1.1 Binaryseach（折半查找、二分查找）折半查找、二分查找）输入：n个元素的数组A1.n和元素x输出：如果x=Aj,1j n,则输出j,否则输出0 1.low=1；high=n;j=0 2
23、.while(low high)and(j=0)3.mid=4.if x=Amid then j=mid 5.else if x50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。1.2.1 算法复杂性分析的必要性算法复杂性分析的必要性n n排排序序：将将一一组组杂杂乱乱无无章章的的数数据据排排列列成成一一个个按按元元素有序的序列。素有序的序列。n n排排序序的的时时间间开开销销:排排序序的的时时间间开开销销是是衡衡量量算算法法好好坏坏的的最最重重要要的的标标志志。排排序序的的时时间间开开销销可可用用算算法法执执行行中中的的数数据据比
24、比较较次次数数与与数数据据移移动动次次数数来来衡衡量量。在在此此给给出出算算法法运运行行时时间间代代价价的的大大略略估估算算一一般般都都按按平平均均情情况况进进行行估估算算。对对于于那那些些受受对对象象元元素素序序列列初初始始排排列列及及对对象象个个数数影影响响较较大大的的，需需要要按最好情况和最坏情况进行估算。按最好情况和最坏情况进行估算。插入排序 插入排序的基本方法是：每步将一个待排序的对象，插入排序的基本方法是：每步将一个待排序的对象，按其元素大小，插入到前面已经排好序的一组对象的适按其元素大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。当位置上，直到对象全部插入
25、为止。各各趟趟排排序序结结果果21254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*160825i=10 1 2 3 4 5 temp21254925*160849i=221254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*1608i=40 1 2 3 4 5 temp21254925*1608i=5i=325*16081649161621254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*08i=4 时的排序过程时的排序过程0 1 2 3 4 5 temp2125
26、4925*完成160816i=4j=3i=4j=22525*161621254925*080 1 2 3 4 50 1 2 3 4 5 temp214925*080 1 2 3 4 5 temp21254925*160816162521i=4j=1i=4j=0i=4j=-116输入：输入：n n个元素的数组个元素的数组A1.nA1.n输出：按非降序排列的数组输出：按非降序排列的数组A1.nA1.n 1.for i=2 to n 1.for i=2 to n 2.x=Ai 2.x=Ai 3.j=i-1 3.j=i-1 4.while(j 4.while(j0 0）andand（AjAjx x）5
27、.Aj+1=Aj5.Aj+1=Aj 6.j=j-1 6.j=j-1 7.end while 7.end while 8.Aj+1=x 8.Aj+1=x 9.end for 9.end for算法算法1.5 Insertionsort算法分析算法分析n n待排序的对象个数为待排序的对象个数为待排序的对象个数为待排序的对象个数为 n n，该算法的主程序执行该算法的主程序执行该算法的主程序执行该算法的主程序执行n n-1-1趟。趟。趟。趟。n n元素比较次数和对象赋值次数与对象元素的初始排列元素比较次数和对象赋值次数与对象元素的初始排列元素比较次数和对象赋值次数与对象元素的初始排列元素比较次数和对象
28、赋值次数与对象元素的初始排列有关。有关。有关。有关。n n最最最最好好好好情情情情况况况况下下下下，排排排排序序序序前前前前对对对对象象象象已已已已经经经经按按按按非非非非降降降降序序序序排排排排列列列列，每每每每趟趟趟趟只只只只需需需需与与与与前前前前面面面面的的的的有有有有序序序序对对对对象象象象序序序序列列列列的的的的最最最最后后后后一一一一个个个个对对对对象象象象的的的的元元元元素素素素比比比比较较较较1 1次次次次，赋赋赋赋值值值值2 2 次次次次对对对对象象象象，总总总总的的的的元元元元素素素素比比比比较较较较次次次次数数数数为为为为 n n-1 1，对对对对象象象象赋值次数为赋值
29、次数为赋值次数为赋值次数为 2(2(n n-1)1)。n n最最最最坏坏坏坏情情情情况况况况下下下下，第第第第 i i 趟趟趟趟时时时时第第第第 i i 个个个个对对对对象象象象必必必必须须须须与与与与前前前前面面面面 i-1i-1个个个个对对对对象象象象都都都都做做做做元元元元素素素素比比比比较较较较，并并并并且且且且每每每每做做做做 1 1 次次次次比比比比较较较较就就就就要要要要做做做做 1 1 次次次次数数数数据据据据赋赋赋赋值值值值。则则则则总总总总的的的的元元元元素素素素比比比比较较较较次次次次数数数数KCNKCN和和和和对对对对象象象象赋赋赋赋值值值值次次次次数数数数RMNRMN
30、 选择排序的基本思想是：每一趟选择排序的基本思想是：每一趟(例如第例如第 i 趟，趟，i=1,n-1)在后面的在后面的 n-i+1 个待排序对象中选出元素最小的个待排序对象中选出元素最小的对象对象,作为有序对象序列的第作为有序对象序列的第 i 个对象。待到第个对象。待到第 n-1 趟作趟作完，待排序对象只剩下完，待排序对象只剩下1个，就不用再选了。个，就不用再选了。选择排序简单选择排序简单选择排序21254925*16080 1 2 3 4 52125*i=1492516251608490825*4921i=2i=3081625*2521初始初始最小者最小者 08交换交换21,08最小者最小者
31、 16交换交换25,16最小者最小者 21交换交换49,214925*0 1 2 3 4 525*i=52516084925*4921结果结果i=408162521最小者最小者 25*无交换无交换最小者最小者 25无交换无交换25211608各趟排序后的结果各趟排序后的结果选择排序算法（p8）n输入：输入：n个元素的数组个元素的数组A1.nn输出：按非降序排列的数组输出：按非降序排列的数组A1.nn 1.for i1 to n-1n 2.kin 3.for j i+1 to nn 4.if AjAk then k jn 5.end forn 6.if kI then 交换交换Ai 与与Akn
32、7.end for 算法分析算法分析 n n直接选择排序的元素比较次数直接选择排序的元素比较次数直接选择排序的元素比较次数直接选择排序的元素比较次数KCNKCNKCNKCN与对象的初始排列与对象的初始排列与对象的初始排列与对象的初始排列无关。第无关。第无关。第无关。第 i i i i 趟选择具有最小元素对象所需的趟选择具有最小元素对象所需的趟选择具有最小元素对象所需的趟选择具有最小元素对象所需的比较次比较次比较次比较次数数数数总是总是总是总是 n-i-n-i-n-i-n-i-1 1 1 1 次次次次.因此，总的元素比较次数为因此，总的元素比较次数为因此，总的元素比较次数为因此，总的元素比较次数
33、为对象的对象的对象的对象的赋值次数赋值次数赋值次数赋值次数与对象序列的初始排列有关。当这组对象的与对象序列的初始排列有关。当这组对象的与对象序列的初始排列有关。当这组对象的与对象序列的初始排列有关。当这组对象的初始状态是按其元素从小到大有序的时候，对象的赋值次数初始状态是按其元素从小到大有序的时候，对象的赋值次数初始状态是按其元素从小到大有序的时候，对象的赋值次数初始状态是按其元素从小到大有序的时候，对象的赋值次数RMN RMN=0=0，达到最少。达到最少。达到最少。达到最少。最坏情况是每一趟都要进行交换，总的对象赋值次数为最坏情况是每一趟都要进行交换，总的对象赋值次数为最坏情况是每一趟都要进
34、行交换，总的对象赋值次数为最坏情况是每一趟都要进行交换，总的对象赋值次数为RMNRMN=3(=3(n n-1)-1)。归并排序n n归并，是将两个或两个以上的有序表合并成一个新的归并，是将两个或两个以上的有序表合并成一个新的归并，是将两个或两个以上的有序表合并成一个新的归并，是将两个或两个以上的有序表合并成一个新的有序表。有序表。有序表。有序表。n n对象序列对象序列对象序列对象序列 中有两个有序表中有两个有序表中有两个有序表中有两个有序表A A p p A A q q 和和和和A A q q+1+1 A A r r。它们可合并成一个有序表，存于另一对象序它们可合并成一个有序表，存于另一对象序
35、它们可合并成一个有序表，存于另一对象序它们可合并成一个有序表，存于另一对象序列列列列B B中，然后再放入中，然后再放入中，然后再放入中，然后再放入A A p p A A r r 中。中。中。中。n n这种归并方法称为这种归并方法称为这种归并方法称为这种归并方法称为2-2-路归并路归并路归并路归并 (2-way merging)(2-way merging)。n n其基本思想是：设两个有序表其基本思想是：设两个有序表其基本思想是：设两个有序表其基本思想是：设两个有序表A A p p A A q q 和和和和A A q q+1+1 A A r r 的对象个数的对象个数的对象个数的对象个数(表长表长
36、表长表长)分别为分别为分别为分别为 n1n1和和和和 n2n2，变量变量变量变量 p p和和和和q q分别是两表分别是两表分别是两表分别是两表=当前检测指针。设表当前检测指针。设表当前检测指针。设表当前检测指针。设表B B是归并后的新有是归并后的新有是归并后的新有是归并后的新有序表，变量序表，变量序表，变量序表，变量 k k 是它的当前存放指针。是它的当前存放指针。是它的当前存放指针。是它的当前存放指针。p q q+p q q+1 1 r rinitListinitLists ts tp rp rk kmergeListmergeListn n当当当当 p p 和和和和q q都在两个表的表长内
37、变化时，根据都在两个表的表长内变化时，根据都在两个表的表长内变化时，根据都在两个表的表长内变化时，根据AAp p 与与与与AAq q 的元素的大小，依次把元素小的对象排放到新的元素的大小，依次把元素小的对象排放到新的元素的大小，依次把元素小的对象排放到新的元素的大小，依次把元素小的对象排放到新表表表表BBk k 中；中；中；中；n n当当当当 p p 与与与与 q q中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一 个表中个表中个表中个表中的剩余部分照抄到新表的剩余部分照抄到新表的剩余部分照抄到新表的剩余部分照抄到新表BB
38、k k 中。中。中。中。合并两个已排序的表（MERGE)（P6)ment:Bp.r是个辅助数组n2.sp;t q+1;k pn3.while sq and trn4.if As At thenn Bk Asn s s+1n7 .else n Bk Atn t t+1n end ifn k k+1n end while n If s=q+1 then Bk.r At.rn else Bk.r As.qn end ifn Ap.r Bp.rn 合并算法分析n n如果两个字数组的大小分别为如果两个字数组的大小分别为如果两个字数组的大小分别为如果两个字数组的大小分别为n1n1n1n1和和和和n2,n2
39、,n2,n2,则合并则合并则合并则合并后的数组为后的数组为后的数组为后的数组为n=n1+n2,n=n1+n2,n=n1+n2,n=n1+n2,当当当当n1n2n1n2n1n2n1n2时，元素比较次时，元素比较次时，元素比较次时，元素比较次数在数在数在数在n1n1n1n1到到到到n-1n-1n-1n-1之间之间之间之间n n如果两个数组个数大致相等时，比较次数在如果两个数组个数大致相等时，比较次数在如果两个数组个数大致相等时，比较次数在如果两个数组个数大致相等时，比较次数在n/2n/2n/2n/2到到到到n-1n-1n-1n-1之间之间之间之间n n此算法的元素赋值次数为此算法的元素赋值次数为此
40、算法的元素赋值次数为此算法的元素赋值次数为2n2n2n2n自底向上合并排序算法自底向上合并排序算法n n自底向上合并排序算法就是利用两路归并过程进行排自底向上合并排序算法就是利用两路归并过程进行排自底向上合并排序算法就是利用两路归并过程进行排自底向上合并排序算法就是利用两路归并过程进行排序的。其基本思想是：序的。其基本思想是：序的。其基本思想是：序的。其基本思想是：假设初始对象序列有假设初始对象序列有假设初始对象序列有假设初始对象序列有 n n 个对象，首先把它看成是个对象，首先把它看成是个对象，首先把它看成是个对象，首先把它看成是 n n 个个个个长度为长度为长度为长度为 1 1 的有序子序
41、列的有序子序列的有序子序列的有序子序列 (归并项归并项归并项归并项)，先做两两归并，得到，先做两两归并，得到，先做两两归并，得到，先做两两归并，得到 n/2n/2 个长度为个长度为个长度为个长度为 2 2 的归并项的归并项的归并项的归并项 (如果如果如果如果 n n 为奇数，则最后一为奇数，则最后一为奇数，则最后一为奇数，则最后一个有序子序列的长度为个有序子序列的长度为个有序子序列的长度为个有序子序列的长度为1)1)；再做两两归并，；再做两两归并，；再做两两归并，；再做两两归并，如此，如此，如此，如此重复，最后得到一个长度为重复，最后得到一个长度为重复，最后得到一个长度为重复，最后得到一个长度
42、为 n n 的有序序列。的有序序列。的有序序列。的有序序列。自底向上合并排序排序算法自底向上合并排序排序算法lenlen=1=1lenlen=2=2lenlen=4=4lenlen=8=8lenlen=16=16自底向上合并排序算法（自底向上合并排序算法（P10)n输入：输入：n n个元素的数组个元素的数组A1.nA1.nn输出：按非降序排列的数组输出：按非降序排列的数组A1.nA1.nn 1.tl 1.tln 2.while tn 2.while tnn 3.st;t2s;i0;3.st;t2s;i0;n 4.while i+t n 4.while i+t nn 5.MERGE(A,i+1,
43、i+s,i+t)5.MERGE(A,i+1,i+s,i+t)n 6.ii+1 6.ii+1n 7.end while 7.end whilen 8.if i+sn then 8.if i+s0;p(n)=(nd);复杂性类与o符号n例：所有的二次函数都属于同一等价类例：所有的二次函数都属于同一等价类n2n用f(n)g(n)来表示f(n)是o(g(n)的，用这个记号可以简明地表示复杂性的层次n1log 1log lognlogn lognlognnn3/43/4nnnlognnlognnn2 222n nn!2n!2n2n21.3如何估计算法的运行时间如何估计算法的运行时间 对于一个具体的算法，
44、如何来估算算法的运行时间呢？将算法中所有的基本操作所耗费的时间相加，固然能得到算法精确的运行时间。但是，这往往是很难做到的。已经发展了一些直接分析技术来估算算法的运行时间。n1.3.1 计算迭代次数计算迭代次数n1.3.2 计算基本运算的频度计算基本运算的频度n1.3.3 使用递推关系使用递推关系1.3.1 1.3.1 计算迭代次数计算迭代次数n通常，程序的运行时间和程序的迭代次数成比例。因此计算程序的迭代次数就可以作为算法运行时间的指示器。这在很多算法中都可以得到应用，如查找、排序等等。小结：非递归算法分析的基本法则小结：非递归算法分析的基本法则n（1）for/while 循环循环n循环体内
45、计算时间循环体内计算时间*循环次数；循环次数；n（2）嵌套循环）嵌套循环n循环体内计算时间循环体内计算时间*所有循环次数；所有循环次数；n（3）顺序语句）顺序语句n各语句计算时间相加；各语句计算时间相加；n（4）if-else语句语句nif语句计算时间和语句计算时间和else语句计算时间的较大者。语句计算时间的较大者。1.3.2 1.3.2 计算基本运算的频度计算基本运算的频度 对于有些算法，要像前面那样准确地分析算法的运行时间非常麻烦，有时甚至是不可能的。这时候，可以使用频度分析，我们将在后续章节中进行讲解。(单源最短路径、Prim算法等等)定义：基本运算定义：基本运算 如果算法中的一个元运
46、算具有最高频度，所有其他元运算频度均在它的频度的常数倍内，则称这个元运算为基本运算。例：例：Merge中的赋值运算是基本运算。中的赋值运算是基本运算。n计算基本运算的频度的思想是 确定一种基本运算和应用渐近表达式来寻找出这种运算执行的阶，这个阶就将是算法运行的阶。n在一些算法中，所有的元运算都不是基本运算。如：两种或者更多的运算结合在一起的频度与算法的运行时间成正比。n输入：白菜棵数nn输出：按收割顺序存放白菜编号的数组B1.Void reap(int B,int n)2.nInt i,j,k,s,t;nInt*A=new intn;nj=0;k=j;s=nnFor(i=0;in;i+)n A
47、i=i+1;nWhile(jn)n t=3;s=0;n for(i=0;it,i+)n if(-k!=0)n As+=Ai;n else n Bj+=Ai;k=3;Bj+=Ai;k=3;n n n nDelete A;n While和 for循环的循环次数未知或不确定，这是取赋值操作作为基本操作。第14行执行赋值语句n次；第12行执行赋值语句2n次；这样算法运行时间为n在一些算法中，所有的元运算都不是基本运算。如：两种或者更多的运算结合在一起的频度与算法的运行时间成正比。n例：例：1.28 假设有一个假设有一个n个整数的数组个整数的数组A1.n和一和一个正整数个正整数k,1kn,要求把要求把A
48、中前中前k个整个整数相乘，把余下的相加。数相乘，把余下的相加。此例没有基本运算，运行时间正比于加法和乘法总的运算次数。1.3.2 1.3.2 使用递归方程使用递归方程n递归方程的解法已经被研究地比较深入，我们将在第二章中介绍。对于递归算法，可以使用递归方程来分析算法的运行时间。有的时候，非递归算法也可以使用递归方程来分析其运行时间。1.3.4 1.3.4 最坏情况和平均情况分析最坏情况和平均情况分析n有些算法的运行时间，基本取决于问题的规模的大小，而与输入的具体数据无关，如计算一个大小为n的数组元素之和；两个矩阵相加等。但是有些算法的运行时间，不仅与问题规模的大小有关，而且还与输入的具体数据有
49、关。如插入排序算法。n分析时间复杂性是由三种方法：最坏情况的分析、平均情况的分析、最好情况的分析。实际中主要关心最坏情况的分析，有时也考论平均情况的分析，而很少考虑最好情况的分析。1.3.5 1.3.5 最坏情况分析最坏情况分析1.3.6 平均情况分析平均情况分析两种耗费标准n（1）均匀耗费标准n 每执行一条指令（基本语句）需要一个单位时间n 每个数据需要占用一个单位空间n（2）对数耗费标准n 实际计算机字长是有限的，且长度固定n 一个整数n在内存中至少要占用log2n+1个二进制位，n 当位数超过机器字长时，一个存储单元装不下，n 数值之间的运算也不能用一个语句来实现n 因而程序的时空耗费与
50、数据的长度有直接关系n 令：L（i）=log2i+1 i0n 1 i=0n则执行一条语句的时空耗费为f(L(i)n例1：读入字母表=1，2上的字符串，检查串中1和2的个数是否相同。nint x,num=0;nscanf(x);nwhile(x!=0)n if(x=1)num+;n else num-;n scanf(x);n nif(num=0)printf(“个数相同n”);nelse printf(“个数不相同n”);n算法分析：n均匀耗费标准n设字符串的长度为n，循环体中的if语句共执行n次nT(n)=O(n)nS(n)=O(1)n对数耗费标准n在最坏情况下，num的值依次为1、2、3。