第1章 算法分析

赵慧娟hjzhao,1,算法设计与分析,课程地位专业必修课开发系统软件及大型应用软件等的重要基础课程目标培养算法设计与分析的能力掌握常见的算法设计技术及其在具体问题中的应用掌握算法的分析评价方法教材算法设计与分析王红梅清华大学出版社,2,课程介绍,3,课程介绍,课程的主要内容算法的基本概念和常见符号算法设计的常用技术蛮力法、分治法、减治法动态规划、贪心法、回溯法、分枝限界法概率算法、近似算法、计算复杂性理论算法的评价：复杂度分析,4,课程介绍,参考书籍王晓东算法设计与分析清华大学出版社ThomasH.Cormen,CharlesE.LeIntroductiontoAlgorithms中文版：算法导论机械工业出版社课程网站网络教学平台算法设计与分析课程介绍/教学日历/电子教案/习题等课程资料,学时40hrs（理论）+8hrs（实验）实验所需语言C/C+/,5,课程介绍,考核平时（出勤10%+作业20%）+期末考试（70%）答疑时间：周一第3大节地点:信息学院307e-mail:hjzhao,6,课程介绍,算法的基本概念算法分析方法,7,第1章绪论,8,1.1算法的基本概念,1）算法的概念及特征2）算法的重要性3）算法的描述方法4）算法设计的过程5）重要的问题类型,解决问题的方法；对特定问题求解步骤的一种描述，是指令的有限序列；满足下面的特征：输入：0/n个输出：1/n个有穷性：有穷步，有穷时间确定性：每一条指令必须有确切的含义可行性：基本操作的有限次执行,1）算法（Algorithm）的概念,与算法相关的术语,算法数据结构程序,算法与程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如操作系统不是一个算法，是一个在无限循环中执行的程序。算法与数据结构算法是灵魂：不了解施加于数据上的算法就无法决定如何构造数据数据结构是基础：算法的结构和选择又常常在很大程度上依赖于数据结构。,理由1：算法-程序的灵魂问题的求解过程：分析问题设计算法编写程序整理结果程序设计研究的四个层次：算法方法学语言工具理由2：提高分析问题的能力算法的形式化思维的逻辑性、条理性,2）学习算法的重要性,3）算法设计的一般过程,1理解问题2预测所有可能的输入3.在精确解和近似解间做选择4.确定适当的数据结构5算法设计技术6描述算法7跟踪算法8分析算法的效率9根据算法编写代码,3）算法设计的一般过程,欧几里德算法,m,n,r,例：欧几里德算法辗转相除法求两个自然数m和n的最大公约数,4）算法的描述方法,A.自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段,输入m和n；求m除以n的余数r；若r等于0，则n为最大公约数，算法结束；否则执行第步；将n的值放在m中，将r的值放在n中；重新执行第步。,欧几里德算法的自然语言描述,B.流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次,4）算法的描述方法,欧几里德算法的流程图描述,C.程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数,4）算法的描述方法,#includeintCommonFactor(intm,intn)intr=m%n;while(r!=0)m=n;n=r;r=m%n;returnn;voidmain()coutCommonFactor(63,54)endl;,欧几里德算法的C+语言描述,D.伪代码算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解,4）算法的描述方法,1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;,欧几里德算法的伪代码描述,5）重要的问题类型,查找问题排序问题图问题组合问题几何问题,1.2算法分析（AlgorithmAnalysis）,1）算法评价的基本规则2）算法的复杂性分析对算法所需要的计算机资源-时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）,算法分析的目的：设计算法设计出复杂性尽可能低的算法选择算法在多种算法中选择其中复杂性最低者,算法分析的5条基本原则,正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，则称该算法是正确的。正确性证明的内容：方法的正确性证明算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序的正确性证明可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。,算法分析的5条基本原则,工作量时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。,关键：问题规模n：输入量的多少；基本语句：执行次数与整个算法的执行时间成正比的语句表示：T(n),for(i=1;i=n;i+)for(j=1;j=n;j+)x+;,问题规模：n基本语句：x+执行次数：n*n,时间复杂性分析,算法分析的5条基本原则,占用空间空间复杂性分析两种占用：存储程序和输入数据的空间存储中间结果或操作单元所占用空间额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据空间受输入规模约束空间复杂性考虑的是额外空间的大小,算法分析的5条基本原则,简单性含义：算法简单，程序结构简单。好处：容易验证正确性便于程序调试说明：简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。,算法分析的5条基本原则,最优性含义：指求解某类问题中效率最高的算法两种最优性最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。,31,算法分析的5条基本原则举例,例：在n个不同的数中找最大的数。基本运算：比较算法：FindMax输入：数组L，项数n输出：L中的最大项MAXMAXL(1);i2;whileindoifMAX0），则有T(n)=O(nm)且T(n)=(nm)，因此，有T(n)=(nm)。,2）最好、最坏和平均情况,例：在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）,intFind(intA,intn)for(i=0;in;i+)if(Ai=k)break;returni;,最好情况：出现概率较大时分析最坏情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布,结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。,3）非递归算法的分析,算法非递归算法、递归算法,例：求数组最小值算法intArrayMin(inta,intn)min=a0;for(i=1;in;i+)if(aimin)min=ai;returnmin;,非递归算法分析的一般步骤：,1.决定用哪个（或哪些）参数作为算法问题规模的度量2.找出算法中的基本语句3.检查基本语句的执行次数是否只依赖于问题规模4.建立基本语句执行次数的求和表达式5.用渐进符号表示这个求和表达式关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。,4）递归算法的分析,递归：函数直接或间接的调用自身叫函数的递归调用,4）递归算法的分析,A.猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。,关键：根据递归过程建立递推关系式，然后求解这个递推关系式。,二路归并排序算法,假定T(n)=n2。证明是成立的。假定T(n)=n，显然不成立则T(n)介于n与n2之间，证明T(n)=nlog2n,B.扩展递归技术,C.通用分治递推式,大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。,例1:,T(n)=4(T/2)+n-O(n2)T(n)=4(T/2)+n2-O(n2log2n)T(n)=4(T/2)+n3-O(n3)递归树法：T(n)=T(n/4)+T(n/2)+n2-O(n2),5）算法的后验分析,算法的后验分析（Posteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。,一般步骤：1.明确实验目的2.决定度量算法效率的方法，为实验准备算法的程序实现3.决定输入样本，生成实验数据4.对输入样本运行算法对应的程序，记录得到的实验数据5.分析得到的实验数