算法设计与分析-第2章

1、算法设计与分析算法设计与分析清华大学出版社清华大学出版社第二章第二章 算法分析基础算法分析基础2.1 算法的时间复杂性分析算法的时间复杂性分析2.2 算法的空间复杂性分析算法的空间复杂性分析2.3 最优算法最优算法算法设计与分析算法设计与分析清华大学出版社清华大学出版社2.1 算法分析算法分析 算法分析（算法分析（Algorithm Analysis）：对算法所需）：对算法所需要的两种计算机资源要的两种计算机资源时间和空间进行估算时间和空间进行估算 时间复杂性（时间复杂性（Time Complexity） 空间复杂性（空间复杂性（Space Complexity）算法分析的目的：算法分析的目的

2、： 设计算法设计算法设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法 选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者算法设计与分析算法设计与分析清华大学出版社清华大学出版社时间复杂性分析的关键：时间复杂性分析的关键：问题规模：输入量的多少；问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时间基本语句：执行次数与整个算法的执行时间 成正比的语句成正比的语句for (i=1; i=n; i+) for (j=1; j=n; j+) x+;问题规模：问题规模：n基本语句：基本语句：x+2.1.1 输入规模和基本语句输入规模和基本语句 算法设计与分析算法

3、设计与分析清华大学出版社清华大学出版社2.1.2 算法的渐进分析算法的渐进分析 1. 大大O符号符号定义定义2.1 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有，都有T( (n)cf( (n) )，则称，则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之前的之前的情况无关情况无关紧要紧要T( (n) )cf( (n) )算法设计与分析算法设计与分析清华大学出版社清华大学出版社例如：例如：当有当有T T( (n n) ) 100100n n5 5取取n n0 05 5，对任意，对任意n n n n0 0，有：，有：T T( (

4、n n) ) 100100n nn n=101=101n n令令c c101101， f f( (n n)=)=n n，有：，有：T T( (n n) ) cncn= =cfcf( (n n) )所以所以T T( (n n)=)=O O( (f f( (n n) =O=O( (n n) ) 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2.1.3 最好、最坏和平均情况最好、最坏和平均情况 例：例： 在一维整型数组在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相相等的元素（假设该数组中有且仅有一个元素值为等的元素（假设该数组中有且仅有一个元素值为k） int Find(i

5、nt A , int n) for (i=0; i + += = =15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii= = - -= =- -+ += = + += =- - -= = 222112222225)2(52)2(52) 1 (25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+ + + + += =+ + + += =+ + += =+ += =- - -LL算法设计与分析算法设计与分析清华大学出版社清华大学出版社3. 通用分治递推式通用分治递推

6、式大小为大小为n的原问题分成若干个大小为的原问题分成若干个大小为n/b的子问题，的子问题，其中其中a个子问题需要求解，而个子问题需要求解，而cnk是合并各个子问题是合并各个子问题的解需要的工作量。的解需要的工作量。 + += = =1)(1)(ncnbnaTncnTk = =kkkbkkabanObannObanOnTb)()log()()(log算法设计与分析算法设计与分析清华大学出版社清华大学出版社2.2 算法的空间复杂性分析算法的空间复杂性分析 算法在运行过程中所需的存储空间包括算法在运行过程中所需的存储空间包括：1. 输入输出数据占用的空间输入输出数据占用的空间2. 算法本身占用的空间

7、算法本身占用的空间3. 执行算法需要的辅助空间执行算法需要的辅助空间 例例2.2中起泡排序算法的空间复杂性为中起泡排序算法的空间复杂性为O(1); 例例2.3中合并算法的空间复杂性为中合并算法的空间复杂性为O(n+m). 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2.3 最优算法最优算法 如何计算一个问题的计算复杂性下界，也就如何计算一个问题的计算复杂性下界，也就是求解该问题的任何算法所需的时间下界。是求解该问题的任何算法所需的时间下界。v 对于某个算法，能否得到该问题的最优算法，对于某个算法，能否得到该问题的最优算法，是否还存在更有效的算法？是否还存在更有效的算法？算法设计与分

8、析算法设计与分析清华大学出版社清华大学出版社定义定义2.2 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有，都有T( (n)cg( (n) )，则称，则称T( (n) )=( (g( (n)n0问题规模问题规模n执执行行次次数数n0之 前 的之 前 的情 况 无 关情 况 无 关紧要紧要T( (n) )cg( (n) )2.3.1 问题的时间复杂性下界问题的时间复杂性下界 算法设计与分析算法设计与分析清华大学出版社清华大学出版社例：例： T( (n) )5n28n1当当n1时，时，5n28n15n28nn 5n29n5n29n214n2O( (n2) )当当n1

9、时，时，5n28n15n2( (n2) )算法设计与分析算法设计与分析清华大学出版社清华大学出版社确定一个问题的计算复杂性下界的简单方法是，确定一个问题的计算复杂性下界的简单方法是，对问题的输入中必须要处理的元素进行计数，同对问题的输入中必须要处理的元素进行计数，同时必须对输出的元素进行计数。因为任何算法至时必须对输出的元素进行计数。因为任何算法至少要读取所有要处理的元素，并写出它的全部输少要读取所有要处理的元素，并写出它的全部输出，这种计数方法产生的是一个出，这种计数方法产生的是一个平凡的下界平凡的下界。2.3.2 平凡下界平凡下界 算法设计与分析算法设计与分析清华大学出版社清华大学出版社许

10、多算法的工作方式都是对输入元素进行比较，许多算法的工作方式都是对输入元素进行比较，例如排序和查找算法，因此可以用判定树来研究例如排序和查找算法，因此可以用判定树来研究这些算法的时间性能。判定树是满足如下条件的这些算法的时间性能。判定树是满足如下条件的二叉树：二叉树：2.3.3 判定树模型判定树模型 1 1、每一个内部结点对应一个形如、每一个内部结点对应一个形如x=yx=y的比较，如的比较，如果关系成立，则控制转移到该结点的左子树，或果关系成立，则控制转移到该结点的左子树，或者，控制转移到该结点的右子树；者，控制转移到该结点的右子树；2 2、每一个叶子结点表示问题的一个结果。、每一个叶子结点表示

11、问题的一个结果。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法设计与分析算法设计与分析清华大学出版社清华大学出版社2.3.4 算法的后验分析算法的后验分析 算法的后验分析（算法的后验分析（Posteriori）也）也称算法的实验分析，它是一种事后计称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对算的方法，通常需要将算法转换为对应的程序并上机运行。应的程序并上机运行。算法设计与分析算法设计与分析清华大学出版社清华大学出版社一般步骤：一般步骤：1. 明确实验目的明确实验目的 2. 决定度量算法效率的方法，为实验准备算法的决定度量算法效率的方法，为实验准备算法的程序实现

12、程序实现3. 决定输入样本，生成实验数据决定输入样本，生成实验数据 4. 对输入样本运行算法对应的程序，记录得到的对输入样本运行算法对应的程序，记录得到的实验数据实验数据5. 分析得到的实验数据分析得到的实验数据 算法设计与分析算法设计与分析清华大学出版社清华大学出版社表格法记录实验数据表格法记录实验数据 129,799113,06391,27478,69267,27253,01039,99224,30311,966次数次数900080007000600050004000300020001000规模规模散点图记录实验数据散点图记录实验数据 执行次数或时间 问题规模n算法设计与分析算法设计与分析清华大学出版社清华大学出版社1.3 实验项目实验项目求最大公约数求最大公约数 1. 实验题目实验题目求两个自然数求两个自然数m和和n的最大公约数。的最大公约数。2. 实验目的实验目的 复习数据结构课程的相关知识，实现课程间的平滑过渡；复习数据结构课程的相关知识，实现课程间的平滑过渡； 掌握并应用算法的数学分析和后验分析方法；掌握并应用算法的数学分析和后验分析方法； 理解这样一个观点：不同的算法能够解决相同的问题，这理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。些算法的解题思路不同，复杂程度不同，解题效率也不同。算法设计与分析