单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/3/6,LingJie/GDUT,#,第,2,章,2024/11/17,LingJie/GDUT,1,第,2,章 算法效率分析基础,主要内容：,2.1,分析框架,2.2,渐进符号和基本效率类型,2.3,非递归算法的数学分析,2.4,递归算法的数学分析,2024/11/17,LingJie/GDUT,2,2.1,算法,分析的基本框架,一般而言，对于一个算法的分析主要是对算法效率的分析，包括了衡量其运行速度的时间效率以及衡量算法运行需要占用空间大小的空间效率。对于早期的计算机来说，时间与空间都是极其珍贵的资源。半个世纪以来，硬件技术的发展大大提高了计算机的存储容量，使得存储容量的局限性对于算法的影响大大降低了。但时间效率并没有得到相同程度的提高。因此，算法的时间效率是算法分析中的关键部分。,2024/11/17,LingJie/GDUT,3,2.1.1,输入规模的度量,一个显而易见的事实是：大部分算法的执行时间随着输入量的增加而增大。例如在对一个数组进行排序时，数组越大，排序需要的时间就越长。因此从逻辑上来说，算法的效率应该是输入量的函数。,选择哪个参数表示输入规模是有差异的。如计算两个,n,阶矩阵的乘积，选择矩阵阶数和矩阵元素个数作为输入规模求的的算法效率是有差别的。选择输入规模的合适度量受算法的操作细节影响，如拼写检查算法可以使用字符或词的数量作为输入规模。,如果算法是与数字特性相关的，其输入规模的度量应当引起注意。例如：检查给定的整数是否为质数，倾向于度量数字,n,的二进制表示中的比特数。,2024/11/17,LingJie/GDUT,4,2.1.2,运行时间的度量单位,算法时间包括了编译该算法的时间以及运行该算法的时间。因此衡量算法时间的单位很自然的会想到用,“,秒,”,、,“,毫秒,”,等实际的时间单位。这对于算法的测试者而言是很直观的，但是存在的问题是：编译算法的时间与编译程序的好坏有关，即使只考虑算法运行时间，得到的时间也受到了运行该算法的计算机速度的影响。因此一个算法在某一台计算机上实现得到的时间对于其他的计算机是没有参考意义的。,2024/11/17,LingJie/GDUT,5,统计算法每一步操作的执行次数,不可行。,统计算法中最重要的操作,基本操作,的执行次数。,排序的基本操作：比较,矩阵乘法的基本操作：乘法,多项式求值的基本操作：乘法,执行次数,C(n),是输入规模,n,的函数，算法运行时间,T(n),是执行次数,的函数：,2024/11/17,LingJie/GDUT,6,Basic operation:,the operation that contributes most towards the running time of the algorithm.,T,(,n,),c,op,C,(,n,),running time,execution time,for basic operation,Number of times basic operation is executed,input size,其中,:c,op,为特定计算机上一个基本操作的执行时间，是常量。,2024/11/17,LingJie/GDUT,7,2.1.3,增长次数,小规模的输入在运行时间上不能区分高效的算法与低效的算法，要考虑对于大规模输入时执行次数的增长次数。,n log,2,n nlog,2,n n,2,n,3,2,n,n!,10 3.3 3.310 10,2,10,3,10,3,3.610,6,10,2,6.6 6.610,2,10,4,10,6,1.310,30,3.610,157,10,3,10 1.010,4,10,6,10,9,10,5,17 1.710,6,10,10,10,15,2024/11/17,LingJie/GDUT,8,2.1.4,算法最优、最差和平均效率,算法最差效率：当输入规模为,n,时，算法在最坏情 况下的效率。,算法最优效率：当输入规模为,n,时，算法在最理想情况下的效率。,算法平均效率：在,“,随机,”,或,“,典型,”,输入时（规模仍为,n,），算法的效率。,平均效率的研究方法：一般将规模为,n,的实例分为几种类型，在假设各种输入的概率分布，推导出基本操作的平均次数。,2024/11/17,LingJie/GDUT,9,2.1.4,顺序查找的效率,最差效率：,最优效率：,平均效率：,2024/11/17,LingJie/GDUT,10,2.1,小结,:,算法分析框架的要点,算法的时间效率与空间效率都是算法输入量的函数。,时间效率的衡量通过算法基本操作执行次数的估计进行，而空间效率的衡量是通过算法运行所占用额外的存储器资源量进行的。,有些算法时空复杂度在相同输入量下可能由于具体输入值的不同而不同，因此需要考虑最好情况下、最坏情况下以及一般情况下的算法时间复杂度。,算法的分析框架关注的内容是当输入量很大，趋向无穷的时候，算法的时间复杂度是如何增长，即使用算法的时间复杂度的渐进表示法。,2024/11/17,LingJie/GDUT,11,2.2,渐进符号和基本效率类型,三个渐进符号：,常用函数符号：,t(n),：一个算法运行的时间,C(n),：基本操作次数,g(n),：,用来比较的函数,2024/11/17,LingJie/GDUT,12,1,、三个渐进符号的定义,O,的定义,：,存在常数,c0,和非负整数,n,0,，,使得对所有,n,n,0,，有,t(n),cg(n),则称函数,t(n),包含在,O(g(n),中，记为,t(n)O(g(n).,也,称函数,t(n),在,n,充分大时有上界,g(n),并称,t(n),的阶不高于,g(n),的阶,.,例如，4,nlogn+7 O(nlogn,)。,2024/11/17,LingJie/GDUT,13,2024/11/17,LingJie/GDUT,14,的定义,：,存在常数,c0,和非负整数,n,0,，,使得对所有,n,n,0,，有,t(n),cg(n),则称函数,t(n),包含在,(g(n),中，记为,t(n)(g(n),也称,t(n),的阶不低于,g(n),的阶,.,例如：,2n,2,+11n-10,(n,2,),，,n,3,(n,2,),2024/11/17,LingJie/GDUT,15,2024/11/17,LingJie/GDUT,16,存在大于,0,的常数,c,1,、,c,2,和非负整数,n,0,，,使得对所有,n,n,0,，有,c,1,g(n),t(n),c,2,g(n),，,则称函数,t(n),包含在,(g(n),中。记为,t(n)(g(n),。,例如：,3n,2,+16n+68,(n,2,),2024/11/17,LingJie/GDUT,17,2024/11/17,LingJie/GDUT,18,2,、渐进符号的有用特性,运算法则：,1.O(f)+O(g)=O(max(f,g),2.O(f)+O(g)=O(f+g),3.O(f)O(g)=O(fg),4.,如果,g(n)O(f(n),则,O(f)+O(g)=O(f),5.fO(f),6.O(cf(n)=O(f(n),（对符号,与,，有类似结论）,2024/11/17,LingJie/GDUT,19,法则,1,（定理,1,）：,如果,t,1,(n),O(g,1,(n),t,2,(n)O(g,2,(n),则,t,1,(n)+t,2,(n),O(maxg,1,(n),g,2,(n),证明：见,P45,。,2024/11/17,LingJie/GDUT,20,3,、渐进符号的证明,方法,1,：利用定义直接证明。,方法,2,：利用极限计算,2024/11/17,LingJie/GDUT,21,例如 估计如下二重循环算法在最坏情况下时间复杂性,T(n),的阶,.,for i:=1 to n do,for j:=1 to i do,s1,s2,s3,s4;,/s1,s2,s3,s4,为单一赋值语句,分析,:,内循环体只需,O,(1),时间,故,内循环共需,外循环共需,2024/11/17,LingJie/GDUT,22,O(2,n,),O(n!),O(n,n,),常见的指数阶,O(1),O(logn),O(n),O(nlogn),O(n,2,),O(n,3,),maxval,maxval=Ai,return maxval,2024/11/17,LingJie/GDUT,27,确定基本操作：是赋值运算还是比较运算,?,求基本操作的执行次数,记,C(n),为比较运算的执行次数，则,C(n)=,于是，,C(n)=n-1(n),2024/11/17,LingJie/GDUT,28,2.3.2,分析非递归算法效率的通用方案,分析的一般步骤：,1,、决定哪些参数作为输入规模的度量,2,、找出算法的基本操作,3,、检查基本操作的执行次数是否只依赖于输入规模,4,、求出基本操作的表达式,5,、确定基本操作执行次数的增长次数。,2024/11/17,LingJie/GDUT,29,2.3.3,计算两个,n,阶方阵乘积的例子,算法伪代码：,MaxtrixMultiplication(A0.n-1,0.n-1,B0.n-1,0.n-1),for i=0 to n-1 do,for j=0 to n-1 do,Ci,j=0.0,for k=0 to n-1 do,Ci,j=Ci,j+Ai,k*Bi,k,return C,2024/11/17,LingJie/GDUT,30,分析：,输入规模的度量：,n,基本操作：乘法,执行次数表达式,M(n)=,运行时间：,T(n)C,m,M(n),(n,3,),其中,C,m,为执行一次乘法在某计算机上所需要的时间,若考虑加法，则,T(n)C,m,M(n)+C,a,A(n)(n,3,),其中,C,a,为执行一次加法在某计算机上所需要的时间，,A(n),为加法的执行次数。,2024/11/17,LingJie/GDUT,31,2.3.4,求一个十进制正整数在二进制表示中 的二进制个数,算法伪代码：,Binary(n),/,输入：十进制正整数,n,/,输出：,n,在二进制表示中的二进制数字个数,基本操作为：,n1,；,执行次数为：,2024/11/17,LingJie/GDUT,32,2.4,递归算法的数学分析,例,1,、,n!,的递归算法,(n,为正整数,),。,一般的,方法：,n!=1*2*,*(n-1)*n,递归的方法,递归公式：,F(n)=F(n-1)n,，,0,！,:=1,算法伪代码：,F(n),/,输入：非负整数,n,/,输出：,n!,的值,if n=0 return 1,else return F(n-1)*n,2024/11/17,LingJie/GDUT,33,C,语言表示：,int factorial(int n),int x;,if(n=0),x=1;,else,x=factorial(n-1)*n;,return(x);,/,在该函数,factorial,(n),求解过程中,直接调用,factorial,(n-1),自身,所以,它是一个直接递归函数,2024/11/17,LingJie/GDUT,34,分析：,基本操作：乘法,记,M(n),为乘法执行次数，则递归关系表达式为,M(n)=M(n-i)+i,，,M(0)=0,于是，,M(n)=M(n-1)+1=M(n-n)+n=n,2024/11/17,LingJie/GDUT,35,分析递归算法效率的通用方案,分析的一般步骤：,1,、决定哪些参数作为输入规模的度量,2,、找出算法的基本操作,3,、检查对于相同规模的不同输入，基本操作的执 行次数是否不同,4,、求出基本操作的递归关系表达式及初始条件,5,、解递归关系，得基本操作执行次数的增长次数,2024/11/17,LingJie/GDUT,36,递