2第二章 算法效率分析基础

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,Analysis and Design of Computer Algorithms,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,算法分析与设计,Analysis and Design of Computer Algorithms,第二章,算法效率分析基础,1,算法效率分析基础,算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。,Time is Important,不是所有能计算的都有价值，不是所有有价值的都能被计算,阿尔伯特,.,爱因斯坦,2,School of Computer Science and Technology,SWUST,教学内容,算法效率分析框架,算法效率的表示符号,非递归算法的效率分析,递归算法的效率分析,算法的经验分析,要求,掌握算法中近似时间的表示、非递归、递归算法的效率分析方法，了解算法的经验分析,3,School of Computer Science and Technology,SWUST,分析框架,输入规模度量,输入规模度量,算法的时间效率和空间效率都用输入规模的函数进行度量。,对于所有的算法，对于规模更大的输入都需要运行更长的时间。,经常使用一个输入规模n为参数的函数来研究算法的效率。,选择输入规模的适宜量度，要受到所讨论算法的操作细节影响。,4,School of Computer Science and Technology,SWUST,分析框架,运行时间的度量单位,运行时间的度量单位,用算法的根本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。,根本操作通常是算法最内层循环中最费时的操作。,算法运行时间的估计：,T(n)c,op,C(n),n是该算法的输入规模,cop是特定计算机上一个算法根本操作的执行时间,C(n)是该算法需要执行的根本操作的次数,5,School of Computer Science and Technology,SWUST,分析框架,增长次数,增长次数,小规模输入在运行时间上的差异缺乏以将高效的算法和低效的算法区分开来。,一个需要指数级操作次数的算法只能用来解决规模非常小的问题,6,School of Computer Science and Technology,SWUST,分析框架,算法的最优、最差和平均效率,算法的最优、最差和平均效率,最差效率是指在输入规模为n时，算法在最坏情况下的效率。,最优效率是指在输入规模为n是，算法在最优情况下的效率。,平均效率是指在“典型或“随机输入的情况下，算法具有的行为（效率）。,摊销效率是指对于同样的数据结构执行屡次操作，然后分摊到每一次上。,7,School of Computer Science and Technology,SWUST,渐进符号,算法效率的主要指标是根本操作次数的增长次数。,为了对这些增长次数进行比较和归类，计算机科学家们使用了3种符号：,O（读“O）：上界,（读omega）：下界,（读theta）：近似,8,School of Computer Science and Technology,SWUST,符号,O,定义,1,对于足够大的,n,，,t(n),的上界由,g(n),的常数倍来确定，即：,记为,t(n),O(g(n),t(n)cg(n),，,c,为常数,n O(n,2,),100n+5 O(n,2,),n(n-1)/2 O(n,2,),9,School of Computer Science and Technology,SWUST,符号,定义,2,对于足够大的,n,，,t(n),的下界由,g(n),的常数倍来确定，即：,记为,t(n),(g(n),t(n),cg(n),，,c,为常数,n,3,(n,2,),n(n+1),(n,2,),4n,2,+5 (n,2,),10,School of Computer Science and Technology,SWUST,符号,定义,3,对于足够大的,n,，,t(n),的上界和下界由,g(n),的常数倍来确定，即：,记为,t(n),(g(n),c,2,g(n),t(n),c,1,g(n),，,c,1,c,2,为常数,n,2,+3n+2,(n,2,),n(n-1)/2,(n,2,),4n,2,+5 (n,2,),11,School of Computer Science and Technology,SWUST,渐进符号的有用特性,定理 如果t1(n)O(g1(n)并且t2(n)O(g2(n)，则,t1(n)+t2(n)O(max(g1(n),g2(n),对于符号和，该定理也成立。,该定理说明：当算法由两个连续执行局部组成时，该算法的整体效率由具有较大增长次数的那局部所决定。,12,School of Computer Science and Technology,SWUST,利用极限比较增长次数,前两种情况意味着,t(n)O(g(n),后两种情况意味着,t(n),(g(n),第二种情况意味着,t(n),(g(n),13,School of Computer Science and Technology,SWUST,根本的效率类型,常量,(1),、对数,(logn),、线性,(n),、,nlogn,、平方,(n,2,),、立方,(n,3,),、指数,(2,n,),、阶乘,(n!),14,School of Computer Science and Technology,SWUST,非递归算法的数学分析,Example 1,：讨论下面这个算法（从,n,个元素中查找最大元素问题）的效率。,算法,MaxElement(A0.n-1,/,求给定数组中的最大元素,/,输入：实数数组,A0.n-1,/,输出：,A,中的最大元素,maxval,A0,for i 1 to n-1 do,if Ai maxval,maxval Ai,return maxval,考虑：,循环中的操作有比较和赋值，取哪一个作为根本操作？,输入规模是多少？,基本操作为：比较运算,输入规模就是数组长度,n,算法的效率为：,15,School of Computer Science and Technology,SWUST,分析非递归算法效率的通用方案,决定用那些参数作为输入规模的度量。,找出算法的根本操作。,检查根本操作的执行次数是否只依赖输入规模。,建立一个算法根本操作执行次数的求和表达式。,利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。,16,School of Computer Science and Technology,SWUST,Example,考虑下面算法的效率,Example 2,元素唯一性问题,算法,UniqueElements(A0.n-1),/,验证给定数组的元素是否全部唯一,/,输入：实数数组,A0.n-1,/,输出：如果唯一，返回,True,，否则,False,for i,0,to n-2 do,for ji+1 to n-1 do,if,Ai,=,Aj,return False,return True,Example 3,两个,n,阶方阵乘法,算法,MatrixMuti(A0.n-1,0.n-1,B0.n-1,0.n-1),/,根据定义计算两个,n,阶矩阵的乘积,/,输入：两个,n,阶矩阵,/,输出：矩阵,C=AB,for i,0 to n-1 do,for j0 to n-1 do,Ci,j,0.0,for k 0 to n-1 do,Ci,j,=,Ci,j,+,Ai,k,*B,k,j,return C,17,School of Computer Science and Technology,SWUST,递归算法的数学分析,例：对于任意非负整数,n,，计算,F(n)=n!,的值。,F(n)=,n(n-1)!,n1,1 ,n=1,1 ,n=0,算法,F(n),/,递归计算,n!,/,输入：非负整数,n,/,输出：,n!,的值,if n=0 retuen 1,else return F(n-1)*n,M(n)=,M(n-1)+1 ,n1,0 ,n=0,M(n)=M(n-1)+1,=M(n-2)+1+1=M(n-2)+2,=M(n-3)+1+2=M(n-3)+3,=M(n-n)+1+n-1=n,18,School of Computer Science and Technology,SWUST,分析递归算法效率的通用方案,决定用哪个参数作为输入规模的度量,找出算法的根本操作,检查对相同规模的输入，根本操作的执行次数是否相同，如果不同，必须对最差、平均及最优效率单独研究,建立一个递推关系式及相应的初始条件,求解这个递归关系式，或者至少确定解的增长次数,19,School of Computer Science and Technology,SWUST,汉诺塔,M(n)=,2M(n-1)+1 ,n1,1 ,n=1,M(n)=2,n,-1,我们应该谨慎使用递归算法，因为他们的简洁可能会掩盖他们的低效率。,20,School of Computer Science and Technology,SWUST,斐波那契数列,F(n)=,F(n-1)+F(n-2),n1,1 ,n=1,0 ,n=0,0,1,1,2,3,5,8,13,21,34,21,School of Computer Science and Technology,SWUST,算法的经验分析,对算法效率做经验分析的通用方案,了解试验的目的,决定用来度量效率的量度,M,和度量单位（单位时间内的操作次数）,决定输入样本的特性,为实验准备算法的程序实现,生成输入样本,对输入样本进行计算，并记录观察到的实验数据,分析获得的实验数据,22,School of Computer Science and Technology,SWUST,23,School of Computer Science and Technology,SWUST,算法可视法,通过使用图形来传达关于算法的一些有用信息。,算法可视法的种类：,静态算法可视法,动态算法可视法,(,算法动画,Algorithm Animation),24,School of Computer Science and Technology,SWUST,静态算法可视法,25,School of Computer Science and Technology,SWUST,静态算法可视法,26,School of Computer Science and Technology,SWUST,动态算法可视法,27,School of Computer Science and Technology,SWUST,小结,算法效率包括时间效率和空间效率。,时间效率主要用它的输入规模的函数来度量，该函数计算算法根本操作的执行次数。,最差、最优与平均效率,增长次数,符号O，,非递归算法和递归算法的效率分析,递归算法简洁性可能会掩盖它的低效率,算法的经验分析是针对一个输入样本，运行算法的一个程序实现，然后分析观测到的数据。,28,School of Computer Science and Technology,SWUST,