第2章算法效率分析基础

1第2章算法效率分析基础一个问题往往有多个算法，应当分析算法的品性–怎样评价一个算法？–涉及的概念：问题的规模（大小）、基本操作、计算复杂度、复杂度的量级、上下界–掌握循坏算法与递归算法的复杂度分析方法2•正确性•工作量•空间用量•简单性•最优型34顺序查找：•SequentialSearch(A[0..n-1],x)//输入：数组A[0..n-1],和查找关键字x//输出：返回第一个匹配x的元素下标//如果没有匹配的，返回-1•i=0;•whileinandA[i]≠xdoi=i+1;•Ifinthenreturnielsereturn-1;什么是基本运算什么是最坏情况什么是最好情况在表A中查找关键字x56782.1分析框架如何评价时间效率？2.1.1输入规模的度量一个事实：问题规模越大，算法运行时间越长。将算法输入规模n为时间效率的参数。选择哪个（些）参数作为输入规模？9•一个算法好不好体现在运行该算法所需要的计算机资源的多少上–所需资源越少，该算法越好；•计算机最重要的资源是–时间和空间•算法分析对算法利用这两种资源的效率做研究•时间效率：指出正在讨论的算法运行得有多快；•空间效率：关心算法需要的额外空间。•研究实验告诉我们，对于大多数问题来说，我们在速度上能够取得的进展要远大于在空间上的进展，•所以我们把主要精力集中在时间效率上。102.1.2运行时间的度量单位可以采用秒，分，小时吗？可以统计算法每一步的操作次数吗？一般的做法：把基本操作（最重要的操作）次数作为算法运行时间的度量单位。思考下面算法的重要操作：排序矩阵乘法11•建立一个算法时间效率的分析框架•对于输入规模为n的算法•统计基本操作执行次数C(n)，来对其效率进行度量。•在某个特定计算机上的某个算法程序的运行时间•T(n)≈copC(n)基本操作的执行时间基本操作次数12•对下面的三个时间效率函数表达式,哪一个效率高?•C1(n)=n•C2(n)=n3•C3(n)=10n•n=1•1110•n=2•28100•n=3•3271000•n=非常大结论：1随n的递增，不同函数增幅不同2某些函数在大规模时增幅显著，函数可以表示增幅的特点3我们希望选择大规模时，时间效率增幅小的算法13•2.1.3增长次数（增长幅度）•特别考虑大规模的输入要强调执行次数的增长次数呢？这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。14•图1－2各种函数的曲线152.1.4算法的最优、最差和平均效率一个算法的最差效率是指当输入规模为n时，算法的最坏情况下的效率。这时，相对于其他规模为n的输入，该算法的运行时间最长。为什么要考虑最坏效率？提供了对任何规模为n的实例，算法运行的上界Cworst(n)16一个算法的最优效率是指当输入规模为n时，算法在最优情况下的效率。这时，与其它规模为n的输入相比，该算法运行得最快。然而，无论是最差效率分析还是最优效率分析都不能提供一种必要的信息：在“典型”或者“随机”输入的情况下，一个算法会具有什么样的行为。这正是平均效率试图提供给我们信息。17算法计算复杂度的定义182.1.5分析框架概要•算法的时间效率和空间效率都用输入规模的函数进行度量。•我们用算法基本操作的执行次数来度量算时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。•在输入规模相同的情况下，有些算法的效率会的显著差异。对于这样的算法，我们需要区分最差效率，平均效率和最优效率。•本框架主要关心，当算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）函数的增长次数。19复杂度函数的阶2.2渐进符号和基本效率类型2021例题2223注意•上面3个符号O，θ，Ω称为渐进符号•在问题的求解规模充分大的时候才成立。–如，N32N,只有在Nc的时候才成立，其中c是方程N3＝2N的解。当Nc时，前者反而有效。242.2.5渐进符号的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，则t1(n)+t2(n)∈O(max{g1(n),g2(n)})(对于Ω和Θ符号，类似的断言也为真)对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分.252.2.6利用极限比较增长次数虽然符号O，Ω和Θ的正式定义对于证明它们的抽象性质是不可缺少的，但我们很少直接用它们来比较两个特定函数的增长次数。有一种较为简便的比较方法，它是基于对所计论的两个函数的比率求极限。有3种极限情况会发生：大的增长次数比表明相同的增长次数和表明小的增长次数比表明)()()()()()(0)()(limngntngntcngntngntn262.2.7基本的效率类型O(2n)O(n!)O(nn)常见的指数阶O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)1constantlognlogarithmicnlinearnlognnlognn2quadraticn3cubic2nexponentialn!factorial27关于渐进时间效率：当比较两个算法的效率时,若两个算法是同阶的,必须进一步考察阶的常数因子才能辨别优劣。282.3非递归算法的复杂度分析如何用前面介绍的知识分析一个算法的效率29算法分析例题30例1考虑从n个元素的列表中查找元素最大值的问题.假设列表是用数组实现的。MaxElement(A[0..n-1])//求给定数组中最大元素的值//输入：实数数组A[0..n-1]//输出:A中最大元素的值maxval←A[0];fori←1ton-1doifA[i]maxvalmaxval←A[i];returnmaxval;第一步：决定用哪个(哪些)参数作为输入规模的度量：数组元素的个数n31•MaxElement(A[0..n-1])//求给定数组中最大元素的值//输入：实数数组A[0..n-1]//输出:A中最大元素的值•maxval←A[0]；•fori←1ton-1doifA[i]maxvalmaxval←A[i]；•returnmaxval第二步：找出算法基本操作：比较？赋值？32第三步：检查基本操作的执行次数是否只依赖输入规模：比较次数相同•MaxElement(A[0..n-1])•//求给定数组中最大元素的值•//输入：实数数组A[0..n-1]•//输出:A中最大元素的值•maxval←A[0]；•fori←1ton-1do•ifA[i]maxval•maxval←A[i]；•returnmaxval33第四步：建立一个算法基本操作执行次数的求和表达式：•MaxElement(A[0..n-1])•//求给定数组中最大元素的值•//输入：实数数组A[0..n-1]•//输出:A中最大元素的值•maxval←A[0]；•fori←1ton-1do•ifA[i]maxval•maxval←A[i]；•returnmaxval34把C(n)记作比较运算的执行次数,由于该算法每执行一次循环就会做一次比较，并且对于循环变量i在1和n-1(包含在内)中的每个值都会做一次循环，所以，我们得到C(n)的下列求和表达式：111)(ninC)(11)(11nnnCni35算法最优性36分析非递归算法效率的通用方案1.决定用哪个(哪些)参数作为输入规模的度量2.找出算法的基本操作（作为一规律，它总是位于算法的最内层循环中）。3.检查基本操作的执行次数是否只依赖输入规模。如果它还依赖一些其他的特性，则最差效率、平均效率以及最优效率（如果必要）需要分别研究。4.建立一个算法基本操作执行次数的求和表达式。5.利用求和运算的标公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。37例2元素唯一性问题：验证给定数组中的元素是否全部唯一（互不相等）。UniqueElements(A[0..n-1])//输入：数组A[0..n-1]//输出：如果A中的元素全部唯一，返回“true”//否则，返回“false”.fori←0ton-2doforj←i+1ton-1doifA[i]=A[j]returnfalseReturntrue第一步：决定用哪个(哪些)参数作为输入规模的度量：数组元素的个数n38•UniqueElements(A[0..n-1])•fori←0ton-2do•forj←i+1ton-1do•ifA[i]=A[j]returnfalse•Returntrue第二步：找出算法基本操作：比较39•UniqueElements(A[0..n-1])•fori←0ton-2do•forj←i+1ton-1do•ifA[i]=A[j]returnfalse•Returntrue第三步：检查基本操作的执行次数是否只依赖输入规模：比较的次数取决于：n？相同元素？及其位置？40•最差效率：•某个数组Cworst(n)所做的比较数比其它数组都多。•有哪两种类型？–不包括相同元素–最后两个元素是唯一一对相同元素41•UniqueElements(A[0..n-1])•fori←1ton-2do•forj←i+1ton-1do•ifA[i]=A[j]returnfalse•Returntrue第四步：建立一个算法基本操作执行次数的求和表达式：42)(212)1(2)1)(2()1(2)1)(2(1)1()1()1(]1)1()1[(1)(22220202020202011nnnnnnnnnninininnCnininininininijworst这个结果是完全可以预测的：在最坏的情况下，对于n个元素的所有n(n-1)/2对两两组合，该算法都要比较一遍。总共有0到n-2个元素需要考察内循环的一次操作对于给定的i内循环从i+1到n-1进行比较43•例3给定n阶方阵A和B计算乘积C=A·BAlgorithmMatrixMul(A[0..n-1,0..n-1],B[0..n-1,0..n-1])Fori=0ton-1doforj=0ton-1doC[i,j]=0.0;fork=0ton-1doC[i,j]=C[i,j]+A[i,k]*B[k,j]；endofforendofforendofforReturnC44•前面3道例题，似乎很简单•但在某些时候会有困难：•循环变量无规律变化，过于复杂而无法求解的求和表达式，分析平均情况的难度等。45•例4设计算法求一个十进制正整数在二进制表示中的二进制数字个数，并分析算法的计算复杂度算法思想•Binary(n)•//输入十进制正整数n•count:=1•Whilen1do•count:=count+1•n:=•Returncount2/n给定f(x)的值，求n462.4递归算法的复杂度分析例1对于任意非负整数n,计算阶乘函数F(n)=n!的值。当n≥1时，F(n)=F(n-1)·n且0!=1算法F(n)//输入：非负整数nifn=0return1elsereturnF(n-1)*n用n本身来指出算法的输入规模该算法的基本操作是乘法，它的执行次数记作M(n)，思考应该如何构造表达式?47用到的乘法数量M(n)需要满足这个等式：当n0时，M(n)=M(n-1)+1ifn=0return1elsereturnF(n-1)*n规模为n的阶乘的乘法数量做一次乘法F(n-1)*n做完一次乘法后，阶乘规模变为n-148M(n)=M(n-1)+1=M(n-2)+1+1=M(n-3)+1+1+1…=M(n-i)+i…=M(n-n)+n=M(0)+n=n初始条件M(0)=0ifn=0return1elsereturnF(n-1)*n49分析递归算法效率的通用方案1.决定用哪个（哪些）参数作为输入规模的度量。2.找出算法的基本操作。3.检查一下，对于相同规模的不同输入，基