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

算法分析与设计AnalysisandDesignofComputerAlgorithms第二章算法效率分析基础杨春明西南科学技大学计算机学院AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST2算法效率分析基础算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。TimeisImportant不是所有能计算的都有价值，不是所有有价值的都能被计算——阿尔伯特.爱因斯坦AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST3教学内容算法效率分析框架算法效率的表示符号非递归算法的效率分析递归算法的效率分析算法的经验分析要求掌握算法中近似时间的表示、非递归、递归算法的效率分析方法，了解算法的经验分析AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST4分析框架——输入规模度量输入规模度量算法的时间效率和空间效率都用输入规模的函数进行度量。对于所有的算法，对于规模更大的输入都需要运行更长的时间。经常使用一个输入规模n为参数的函数来研究算法的效率。选择输入规模的合适量度，要受到所讨论算法的操作细节影响。AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST5分析框架——运行时间的度量单位运行时间的度量单位用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。基本操作通常是算法最内层循环中最费时的操作。算法运行时间的估计：T(n)≈copC(n)•n是该算法的输入规模•cop是特定计算机上一个算法基本操作的执行时间•C(n)是该算法需要执行的基本操作的次数AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST6分析框架——增长次数增长次数小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来。一个需要指数级操作次数的算法只能用来解决规模非常小的问题AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST7分析框架——算法的最优、最差和平均效率算法的最优、最差和平均效率最差效率是指在输入规模为n时，算法在最坏情况下的效率。最优效率是指在输入规模为n是，算法在最优情况下的效率。平均效率是指在“典型”或“随机”输入的情况下，算法具有的行为（效率）。摊销效率是指对于同样的数据结构执行多次操作，然后分摊到每一次上。AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST8渐进符号算法效率的主要指标是基本操作次数的增长次数。为了对这些增长次数进行比较和归类，计算机科学家们使用了3种符号：O（读“O”）：上界Ω（读”omega”）：下界Θ（读”theta”）：近似AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST9符号O定义1对于足够大的n，t(n)的上界由g(n)的常数倍来确定，即：记为t(n)∈O(g(n))t(n)≤cg(n)，c为常数n∈O(n2)100n+5∈O(n2)n(n-1)/2∈O(n2)AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST10符号Ω定义2对于足够大的n，t(n)的下界由g(n)的常数倍来确定，即：记为t(n)∈Ω(g(n))t(n)≥cg(n)，c为常数n3∈Ω(n2)n(n+1)∈Ω(n2)4n2+5∈Ω(n2)AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST11符号Θ定义3对于足够大的n，t(n)的上界和下界由g(n)的常数倍来确定，即：记为t(n)∈Θ(g(n))c2g(n)≤t(n)≤c1g(n)，c1,c2为常数n2+3n+2∈Θ(n2)n(n-1)/2∈Θ(n2)4n2+5∈Θ(n2)AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST12渐进符号的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，则t1(n)+t2(n)∈O(max{(g1(n),g2(n)})对于符号Ω和Θ，该定理也成立。该定理表明：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST13利用极限比较增长次数前两种情况意味着t(n)∈O(g(n))后两种情况意味着t(n)∈Ω(g(n))第二种情况意味着t(n)∈Θ(g(n))AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST14基本的效率类型常量(1)、对数(logn)、线性(n)、nlogn、平方(n2)、立方(n3)、指数(2n)、阶乘(n!)AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST15非递归算法的数学分析Example1：讨论下面这个算法（从n个元素中查找最大元素问题）的效率。算法MaxElement(A[0..n-1]//求给定数组中的最大元素//输入：实数数组A[0..n-1]//输出：A中的最大元素maxvalA[0]fori1ton-1doifA[i]maxvalmaxvalA[i]returnmaxval考虑：1.循环中的操作有比较和赋值，取哪一个作为基本操作？2.输入规模是多少？基本操作为：比较运算输入规模就是数组长度n算法的效率为：AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST16分析非递归算法效率的通用方案1.决定用那些参数作为输入规模的度量。2.找出算法的基本操作。3.检查基本操作的执行次数是否只依赖输入规模。4.建立一个算法基本操作执行次数的求和表达式。5.利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST17Example考虑下面算法的效率Example2元素唯一性问题算法UniqueElements(A[0..n-1])//验证给定数组的元素是否全部唯一//输入：实数数组A[0..n-1]//输出：如果唯一，返回True，否则Falsefori0ton-2doforji+1ton-1doifA[i]=A[j]returnFalsereturnTrueExample3两个n阶方阵乘法算法MatrixMuti(A[0..n-1,0..n-1],B[0..n-1,0..n-1])//根据定义计算两个n阶矩阵的乘积//输入：两个n阶矩阵//输出：矩阵C=ABfori0ton-1doforj0ton-1doC[i,j]0.0fork0ton-1doC[i,j]=C[i,j]+A[i,k]*B[k,j]returnCAnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST18递归算法的数学分析例：对于任意非负整数n，计算F(n)=n!的值。F(n)=n(n-1)!,n11,n=11,n=0算法F(n)//递归计算n!//输入：非负整数n//输出：n!的值ifn=0retuen1elsereturnF(n-1)*nM(n)=M(n-1)+1,n≥10,n=0M(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=nAnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST19分析递归算法效率的通用方案决定用哪个参数作为输入规模的度量找出算法的基本操作检查对相同规模的输入，基本操作的执行次数是否相同，如果不同，必须对最差、平均及最优效率单独研究建立一个递推关系式及相应的初始条件求解这个递归关系式，或者至少确定解的增长次数AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST20汉诺塔M(n)=2M(n-1)+1,n11,n=1M(n)=2n-1我们应该谨慎使用递归算法，因为他们的简洁可能会掩盖他们的低效率。AnalysisandDesignofComputerAlgorithms©SchoolofComputerScienceandTechnology,SWUST21斐波那契数列F(n)=F(n-1)+F(n-2),n11,n=10,n=00,1,1,2,3,5,8,13,21,34,……AnalysisandD