第2章算法效率分析基础.ppt.ppt

《第2章算法效率分析基础.ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章算法效率分析基础为什么需要对一个算法进行效率分析作比较对于同一问题，为什么一个解法比另一个解法好寻找解决一个问题的算法的极限解决一个问题的最快可以达到多快(度量)如解决排序问题的算法最快是多少?一个问题是否不存在更快的解法(NP问题)如在冯诺依曼机器上，解决旅行商问题的任何算法的时间费用都将是城市数量的指数级算法分析需解决的问题度量一个算法的时间效率(时间费用)度量一个算法的空间效率(空间费用)优化算法最小化一个算法的时间效率或空间效率途径理论分析经验分析理论分析时间效率识别一个算法的“基本操作”对该算法总运行时间贡献最大的操作被认为

2、是基本操作将“基本操作”的执行次数C(n)看成是“输入规模n”-的函数，并通过推导的方法找出C(n)然后估计算法的运行时间T(n)为cop是特定机器上一个算法的基本操作的执行时间，一般假定为常数输入规模与基本操作的例子问题输入规模基本操作从n个元素的列表中搜索特定的元素n比较两个实数矩阵的乘法矩阵的维度浮点乘计算ann浮点乘图问题结点和边的数量访问一个结点或穿越一条边时间效率的经验分析方法选定特定的输入样本使用物理时间单位（如秒）或对基本操作的执行次数进行计数分析实验结果最优、最差和平均效率大多数算法的效率C(n)不仅依赖于输入的规模而且依

3、赖于输入的其它细节：次序、各元素的差异等:最差情况:Cworst(n)即C(n)最大值最好情况:Cbest(n)即C(n)最小值平均情况:Cavg(n)即在一般的输入样本情况下C(n)的值严格地讲，Cavg(n)是假定输入规模为n的输入数据在所有可能的形式下，C(n)的数学期望例子：顺序搜索算法见书P.36输入:数组A[1..n],待找元素k基本操作：比较其中pi为在A[1..n]的第i位置找到k的概率,Ci为相应的比较次数Pn+1相当于没有找到的概率基本操作次数的公式类型精确公式如：C(n)=n(n-1)/2精确的常量乘数和增长次数(不精

4、确)如：C(n)≈0.5n2未知的常量乘数c如：C(n)≈cn2增长次数在忽略常数因子后的执行次数C(n)在n→∞时的度量称为增长次数如对于C(n)≈c×n(n-1),一般在下述场合下只需关心增长次数，即n2项如果算法在一台比现有机器快10倍的机器上运行，它运行有多快？10倍如果输入规模翻倍，该算法会运行多长时间？约4倍的时间常见增长次数(函数)渐进增长率作为一种比较两个函数的增长次数的方法考虑n→∞并忽略常数因子时，函数增长率的比较O,Θ,Ω符号的粗略含义O(g(n))表示增长率不超过g(n)的函数集合Θ(g(n))表示增长率与g(n)相

5、同的函数集合Ω(g(n))表示增长率大于或等于g(n)的函数集合O符号Ω符号Θ符号渐进符号的一个定理将上述命题中的O换成Ω或Θ同样成立利用极限比较增长次数t(n)g(n)关系10n2n2t(n)O(g(n))logbnlogcnt(n)(g(n))n(n+1)/2n2t(n)(g(n))基本的效率类型1常量logn对数n线性nlognnlognn2平方n3立方2n指数n!阶乘2.3非递归算法的数学分析步骤决定哪个(哪些)输入参数表示输入规模找出算法的基本操作一般位于算法的最内层循环中检查基本操作的执行次数是否仅依赖输入规模若否，则

6、需分别研究该算法的Cworst(n)、Cbest(n)、Cavg(n)建立一个基本操作执行次数的求和表达式或递推关系利用求和运算公式(附录A/B)，给出基本操作次数的闭合公式(closedform)或者至少确定增长次数例子：Matrixmultipliacation基本操作:乘法(位于最内层循环)输入规模:n例子：Selectionsort基本操作:比较操作<(位于最内层循环)输入规模:n例子：Insertionsort基本操作:A[j]>v中的键值比较操作(位于最内层循环)输入规模:n例子：Mysteryalgorithmfori:=1t

7、on-1domax:=i;forj:=i+1tondoif

8、A[j,i]

9、>

10、A[max,i]

11、thenmax:=j;fork:=iton+1doswapA[i,k]withA[max,k];forj:=i+1tondofork:=n+1downtoidoA[j,k]:=A[j,k]-A[i,k]*A[j,i]/A[i,i];由渐进符号定理知：只需计算最外层和最后两个嵌套循环的执行次数,基本操作为乘法或除法2.4递归算法的数学分析步骤决定哪个(哪些)输入参数表示输入规模找出算法的基本操作检查基本操作的执行次数是否仅依赖输入规模若否，则需分别

12、研究该算法的Cworst(n)、Cbest(n)、Cavg(n)建立一个基本操作执行次数的递推关系及初始条件解递推式(附录B)，给出基本操作次数的闭合公式(closedform)