算法效率分析基础.ppt

算法设计与分析计算机与信息学院,2,使用教材,使用教材,作者：（美）Anany Levitin 译者：潘彦出版社：清华大学丛书名：国外经典教材 计算机 科学与技术,第 2章 算法效率分析基础,算法效率分析框架 渐进符号和基本效率类型 非递归算法效率分析 递归算法效率分析,4,算法效率分析框架,算法效率分析框架本节将概要地描述一个分析算法效率的一般性框架。时间效率指出算法运行得有多快；空间效率关心算法需要的额外空间。目前，随着计算机硬件技术的飞速发展，空间效率已不是关心重点。因此，我们主要关心的是时间效率。输入规模的度量：（问题规模）一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行更长的时间（即算法耗费的时间随着输入规模的增大而增加）。例如：1.更大的数组排序需要花费更多的运行时间；2.更大的矩阵相乘需要花费更多的运算时间。因此，采用一个以算法输入规模 n 为参数的函数，来研究算法效率就是非常合乎逻辑的。输入规模的选择问题：在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度；对于 n 次多项式求值问题，这个参数是多项式次数或者系数个数。,5,输入规模的选择,当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个n 阶矩阵的乘积，有两种度量输入规模的方法：第一种方法：选择矩阵的阶 n；第二种方法：选择参与乘法运算的所有元素个数。第二种方法更具一般性，适用于非方阵。对于选择不同的输入规模，其算法效率在含义上有所差别。选择输入规模参数的合适量度，会受到算法操作细节的影响。例如：对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查，那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么选择单词数作为输入规模的度量。若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时，计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。,6,时间效率的度量,运行时间的度量：接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位（秒、毫秒等）来度量算法的运行时间呢？其理由如下：1.它依赖于特定计算机的运行速度；2.它依赖于实现算法的代码质量；（程序员编程的水平问题）3.它依赖于编译器的好坏；（编译成机器码的质量，即指令条数）4.它还依赖于一些其他问题如操作系统的调度策略等。鉴于此，希望找到一个不依赖于上述因素的时间度量。问：是否统计算法的每步操作执行次数来作为算法的时间效率度量呢？答：无此必要且较困难。一个算法中有许多操作，决定算法时间效率的是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法时间效率，这些最关键的操作步称为基本操作，它们对算法执行时间的占用最大（基本操作即算法中最费时的操作）。所以，用基本操作执行次数来作为时间效率的度量。,7,基本操作的选取,基本操作的选取例：大多数排序算法是通过比较排序元素（键）来进行工作，因此它的基本操作应选为键的比较操作，即算法中键的比较次数。矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器而言，乘法比加法更耗费时间，所以选取乘法为基本操作。在定义了算法的输入规模 n 和基本操作后，我们就可以建立起一个算法时间效率的分析框架：对规模为 n 的算法，通过统计其基本操作的执行次数来度量算法的时间效率。（时间耗费 T 为输入规模 n 的函数）分析框架的应用：设 t 为算法的一个基本操作在特定机器上的执行时间，C(n)为该算法需执行的基本操作数。用下式来估计该算法在该机器上的运行时间：,忽略了非基本操作执行时间,问：为什么用约等于符号？,8,分析框架的应用例,分析框架的应用例：根据上式，我们可以回答以下问题：1 若某算法运行在一台比现在机器快10倍的机器上，此算法运行多快？答：10倍。（t 增加10倍，C(n)不变）2 设，若输入规模翻倍，该算法运行时间如何变化？,（n 不是太小如 n=100）,不考虑每个操作步在机器上具体的执行时间 t，则时间耗费即为：,时间耗费即为基本操作数，为输入规模n的函数。,n的一次、二次函数分别称线性、二次增长率。2n 称指数增长率。,9,增长次数（增长率）,增长次数（增长率）基本操作数（时间耗费）是输入规模 n 的函数，记为T(n)。T(n)随着 n 次数的增加而增加。函数值T(n)增加快慢，决定于这个增长函数特性；也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快，指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了算法的时间耗费（效率）。若输入规模 n 很小，无论是高效的算法还是低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。,增长函数表：对于算法分析具有重要意义的函数值（近似值）,10,算法效率算例,算法的最优、最差、平均效率前述已知，我们用输入规模 n 的函数 T(n)来度量算法的效率。若T(n)随n 增长快，则算法效率较差；若T(n)随 n 增长较慢，则算法效率更好。这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模有关，且与特定的输入有关。下面以顺序查找算法为例：-【名称】顺序查找【要求】在列表中查找一次给定项（查找键），该列表有 n 个元素。【算法】从列表头开始，逐个比较列表中元素，直到发现匹配查找键的 元素或者到达列表尾为止（没找到）。【分析】1.很明显，该算法的执行效率与查找键在列表中的位置有密切关系。2.若查找键位于表头（第一个元素），该算法只比较一次。最优效率3.若查找键位于表尾（最末元素）或不存在，该算法将比较 n 次。最差4.若查找键位于表中间，该算法比较次数不固定。平均效率-通过上述例子，引入最佳、最差和平均效率的概念。,11,最优、最差效率,1 最差效率：（最为关注）当输入规模为 n 时，算法在最坏情况下的效率。此时，相对于其他规模为 n 的输入，该算法运行时间最长（最慢）。最差效率的确定：原理上讲，首先对算法作一个分析，看看在规模 n 的所有可能输入中，那种输入会导致基本操作数 C(n)达到最大值，计算这个最差值 Cworse(n)。后面讲到，通过确定算法运行时间的上界，分析最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模 n的实例来讲，它保证算法运行时间不会超过最坏输入情况下的运行时间 Cworse(n)。（最差效率分析的价值）顺序查找：Cworse(n)=n2 最优效率：当输入规模为 n 时，算法在最优情况下的效率。此时，相对于其他规模为 n 的输入，该算法运行时间最短（最快）。顺序查找：Cbest(n)=1最优效率分析的价值：远不如最差效率分析重要，因不能指望每次输入都是最优输入。但它对算法的的选择有指导意义，例如：某算法在有序列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近最优输入的效率，实际中可考虑选择该算法。重要的是，如果一个算法的最优效率都不能满足实际需要，可立即抛弃该算法。,12,平均效率,3 平均效率无论是最优还是最差效率，都不能提供这样一种必要信息：在随机输入情况下，该算法具有怎样的行为（时间耗费）。为此，引入平均效率。平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍。平均效率分析的价值：有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。所以如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们不能通过求最优和最差效率平均值的方法来求平均效率。平均效率分析的直接法：1 将输入分为几种类型（可能的话），目的是使得对于同种输入类型的 实例，具有相同的基本操作数。2 得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。但各类输入的概率模型往往又难以验证，虽然它可能很合理。,13,顺序查找算法的平均时间效率,顺序查找算法的平均时间效率：假设：(1)成功查找的概率是 p(0p1)，查找不成功的概率是 1-p；(2)对任意第 i 次查找，第一次成功匹配（查找成功）发生在列表第 i 个位置的概率相同，即查找键位于列表任一位置上的概率相同 1/n。基于假设，在列表任一位置上查找成功的概率为 p(1/n)（甚至可进一步假设p=0.5）。若查找成功的位置为 i，算法做的比较次数（基本操作）为i 次，考虑成功查找概率，比较次数为 p(i/n)；若查找不成功，算法做的比较次数为 n（列表全部查找一遍），考虑不成功查找概率，比较次数则为 n(1-p)。因此，算法平均效率：,统计平均,14,摊销效率,4 摊销效率它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。我们知道，在有些情况下单次运行的时间代价可能比较昂贵，但 n 次运行的总时间花费明显低于单次运行的最差效率乘以 n，因此我们把最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中把固定资产成本按其使用年限摊销到整个序列（各年）中的做法一致。通常，具备这种运行特性的算法是在一定程度上的具有“智能”的算法，通过“学习”获得“知识”累积，再运用知识库中的有关知识对算法下次如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率（学习积累过程），来动态调整这些字词下次出现的先后顺序，高频先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。-后续章节中，除非专门说明，都将最差情况下时间耗费的极限作为算法的时间耗费，称时间复杂性或时间效率。求解过程称为时间渐进分析。,15,渐进符号,渐进符号和基本效率类型上节指出，效率分析主要关心的是一个算法的基本操作数随问题规模的增长率（增长次数），即问题规模 n 变大情况下，该算法的基本操作数增长的快慢（它是规模 n 的函数增长函数）。为了对增长函数作出比较和归类，通常使用三种符号：O,(theta).下面就这些符号先作一个非正式介绍（便于理解）。T(n)和 g(n)：定义在自然数集合上的任意非负函数（n取自然数）；T(n)：算法的运行时间函数（常用基本操作数增长函数 C(n)表示）；g(n)：与增长函数作比较的函数。非正式介绍O(g(n)：增长次数小于等于g(n)（包括其常数倍，n 趋于无穷大）的 函数集合。即 g(n)是增长函数集的上界。例如：,16,上界符号,(g(n)：增长次数大于等于g(n)（包括其常数倍，n 趋于无穷大）的 函数集合。即 g(n)是增长函数集的下界。例如：(g(n)：增长次数等于g(n)（包括其常数倍，n 趋于无穷大）的函数 集合。即 g(n)与增长函数集同阶（相同的增长率）。例如：上界符号 O（最常用）定义：把函数T(n)包含在O(g(n)中，记为T(n)O(g(n)；它成立的条件是：对于足够大的 n，T(n)的上界由g(n)的常数倍决定。即存在正数c 和非负整数 n0，使得下式成立：,17,下界符号,证明：证一：据定义选取：证二：据定义选取：下届符号定义：把函数T(n)包含在(g(n)中，记为T(n)(g(n)；它成立的条件是：对于足够大的 n，T(n)的下界由g(n)的常数倍决定。即存在正数c 和非负整数 n0，使得下式成立：,规模,增长函数,n0 之前情况无关紧要,下界,最佳效率分析,18,同阶符号,同阶符号定义：把函数T(n)包含在(g(n)中，记为T(n)(g(n)；它成立的条件是：对于足够大的 n，T(n)的下界和上界均由g(n)的常数倍决定。即存在正数 c 和非负整数 n0，使得：例：证明 证：注意到上界情况：下界情况：,19,渐进符号的有用性质,渐进符号的有用性质（1、2、3 证明从略）性质1：性质2：性质3：性质4：性质4的价值：（证明见下页）某些算法是由两个（以上）执行部分组成，性质4指明：该算法的整体效率由具有较大增长率的部分决定，即它效率最差的部分。举例如下：数组中特定元素的查找算法：第一部分，用某种已知的排序算法对数组排序，得到有序数组；第二部分，对有序数组从头至尾扫描，比较是否与指定元素相等。若排序部分增长函数为0.5n(n-1)O(n2)；第二部分的增长函数为 nO(n)，那么，算法的整体效率为T(n)O(n2)。,20,渐进符号性质4的证明,性质4的证明：,21,利用极限比较增长率,利用极限比较增长率：此法常用来比较两个特定增长函数的增长率，简便。它根据极限定义，对两个函数的比值求极限，以判定哪个函数增长更快。,例1：比较0.5n(n-1)和n2的增长率。（或证明:0.5n(n-1)(n2)）,22,利用极限比较增长率例,例2：,例3：,23,渐进效率的基本类型,渐进效率的基本类型,24,非递归算法分析,非递归算法的效率分析（很常用）本节将系统地运用前节的通用框架来分析非递归算法的效率。先从一个简单的算法开始，示范这类算法分析的步骤。例1：从 n 个元素列表中查找最大值。（用数组简单实现列表）算法 MaxElement(A0.n-1)/求数组A中元素的最大值/输入：实数数组A。输出：A中最大元素的值 maxvalA0 for i1 to n-1 do if Ai maxval/每次循环时无条件执行（必执行）maxvalAi/每次循环时有条件执行（不一定执行）return maxval效率分析框架要求明确输入规模和基本操作。输入规模：数组元素的个数 n。基本操作：根据基本操作概念，它应该是算法中最费时的操作。因此，应该选择 for 循环内的比较操作。,本算法每个数组元素都要进行一次比较，故不区分最优、最差和平均效率。,25,非递归算法分析2,接下来，效率分析框架要求我们找到基本操作与输入规模的函数关系，即增长函数 T(n)或者 C(n)。这里，C(n)是比较运算的次数。不难看出，本算法每循环一次，基本操作就要执行一次。因此有：非递归算法效率分析的通用方案：1 确定输入规模；2 确定基本操作；（一般情况：它总是位于算法的最内层循环里）3 考虑基本操作的执行次数是否仅仅与输入规模有关。若还与其他因数 有关（比如顺序查找算法中基本操作执行次数还与查找键在列表中的 位置有关），则按需要对最差、最佳、平均效率作出分析。4 建立基本操作执行次数与输入规模 n 的求和表达式，即增长函数。5 利用运算公式（法则），确定该增长函数的增长率。,结论：本算法具有线性增长率,26,复习：几个常用求和公式,复习：几个常用求和公式,27,例2：元素唯一性问题,例2：【元素唯一性问题】检查给定数组的元素是否全部唯一算法：UniqueElement(A0.n-1)for i0 to n-2 do for ji+1 to n-1 do if A i=A j return falsereturn true输入规模：数组元素个数 n基本操作：最内层循环只有一个“比较”操作，选为基本操作。效率种类：从循环结束条件可知，若比较的两个元素相等，则提前结束循环，返回“假”说明数组元素不唯一。最佳的情况是，首次比较就结束循环，即数组开始两个元素就相同；最差的情况是，循环结束前的最后一次比较才发现相同的元素（最后两个），或者该数组没有相同元素，都要完成全部循环次数，即比较次数就是循环次数。这里，我们研究其最差效率 Cworst(n)。,i,j,28,例2：元素唯一性问题(续),外层 i 循环范围：0,n-2。内层 j 循环范围：i+1,n-1建立增长函数（基本操作执行次数与输入规模 n 的求和表达式）：,29,例3：【矩阵乘法】时间效率分析,例3：【矩阵乘法】时间效率分析给定两个方阵 A 和 B，根据矩阵乘法定义计算它们之乘积。算法：MatrixMultiplication(A0.n-10.n-1,B0.n-10.n-1)for i0 to n-1 do/行循环 for j0 to n-1 do/列循环 M i j 0.0/初始化 for k0 to n-1 do/用变量 k 表示变化的脚标 M i j M i j+A i k*B k j return M,列,行,如果是非方阵，只需改变行列循环变量的范围即可。本例均为n-1,30,例3：【矩阵乘法】时间效率分析（续）,输入规模：因是方阵，选择矩阵的阶 n。否则，选参与运算的元素数。基本操作：最内层循环有三种操作：乘法、加法、赋值。每次循环时，每种操作均被执行一次，所以任选一种作为基本操作均可，因为它们的执行次数都一样。但考虑操作的时间耗费，对大多数计算机来讲，乘法比加法更费时间，且算术运算比赋值操作更费时间。所以，本例选乘法作为基本操作。效率种类：因为本算例的基本操作数只与输入规模有关，所以不必分别研究最佳、最差和平均效率。就是一种时间效率。建立增长函数（基本操作数与输入规模 n 的求和表达式）：,31,例4：【二进制位数】一个十进制正整数的二进制位数,例4：【二进制位数】一个十进制正整数 n 的二进制位数 b。算法：Binary(n)count1 while n 1 do countcount+1 n return count输入规模：该正整数的大小 n；基本操作：选循环内的除法操作。效率种类：因基本操作执行次数只与规模 n 有关，无需分别研究最佳、最差和平均效率。增长函数：本例基本操作增长函数不是一个求和表达式，需要用其他的 方法来计算循环次数（基本操作执行次数），可建立递推式 来求解（后面两节介绍）。另外方法，本例循环次数为：,32,递归算法效率分析,递归算法效率分析 序列和递推关系定义：数字序列是数字的一个有序列表。例如：2,4,6,8,10,12,.（正偶数序列）0,1,1,2,3,5,8,.（裴波拉契数序列）序列的函数表示法：x(n)把序列表示为一个函数。自变量 n：表示一个元素在序列中的位置即序号；函数值 x(n)：表示该元素本身。如正偶数序列第2个元素：x(n)称为该序列的通项。序列的两种定义法：1.通项定义法：例如正偶数序列2.方程定义法：把序列的通项和其他项用方程定义，并规定序列的首项 或前几项的值，例如：,递推方程或递推关系，简称递推式,初始条件,33,解递推方程的概念,解递推方程的概念解递推方程，意味着找到序列通项，既满足递推式又满足初始条件。或证明这样一个序列不存在（递推方程无解）。如下递推式的解：验证递推方程：（代入法验证）验证初始条件：递推方程的通解：通常，有无穷多个序列（解）满足同一个递推方程，因此，通解一般包括若干任意常数。本例递推方程的特解：满足递推方程的一个特定的序列（解），通常是那个满足初始条件的特解。一个特定序列由初始条件（初值）确定。,不包括初始条件,34,递推方程求解：前向替换法,递推方程的求解方法不存在对每一个递推方程都有效的一种通用方法。这就象对简单的一元方程 f(x)=0 不能得到它的通解一样。前向替换法：递推方向：前后从序列首项（由初始条件给出）开始，使用递推式生成序列的前几项，希望通过对前几项的观察找到序列的通项，并进行验证。例子如下：递推式：根据初始条件和递推式，生成序列前几项：,通项,方法评价：有时候很难从序列前几项中找到通项！,汉诺(hanoi)塔游戏,35,递推方程求解：反向替换法,反向替换法：（很有效）递推方向：前后用递推式将 x(n)逐次表示为x(n-1),x(n-2),x(n-3),.,x(n-k),k=1,2,3,.然后通过运算化简，得序列通项（解）。例子：递推式：,根据初始条件(n=0)要求：n k=0,上式变为：,该法所得通项是直接由递推式推出来的，故无需验证。,36,递推方程求解：二阶常系数线性递推式,公式法：解二阶常系数线性递推方程问题提出：有一类重要递推式不能用前向和反向替换法求解。形如：概念解释：1.二阶：递推式中未知项 x(n)和 x(n-2)在序列中相差两个位置。2.常系数：递推式中未知项系数为常数。3.线性：递推式为未知项的线性组合。4.齐次：方程右端为0，即 f(n)=0。5.非齐次：方程右端不为0。6.特征方程：齐次递推方程的解，取决于和递推式具有相同系数的一个 二次方程即特征方程：定理1：设 q1,q2 是特征方程的两个根。第一种情况：有两个不相等实根,齐次递推方程通解为：,c1和c2为待定常数,37,递推方程求解：二阶常系数线性递推式例1,第二种情况：有两个相等实根,齐次递推方程通解为：第三种情况：特征方程在实数域无解。略。定理2：把非齐次方程的特解和相应的齐次方程通解相加，得到该非齐次 方程的通解。例1：求齐次递推方程通解和特解解：该递推方程的特征方程为：特征方程有两个相等的实根，根据定理1，该递推方程通解为：根据初始条件解出待定常数，得到一个特解：,c1和c2为待定常数,c1和c2为待定常数,38,递推方程求解：二阶常系数线性递推式例2,例2：求非齐次递推方程满足初始条件的特解解：根据例1，该非齐次方程对应的齐次方程的通解为：注意：此时不能代入初始条件解出非齐次方程的一个特解（为什么？）现在，求非齐次方程的一个特解：设特解为，由递推式解得根据定理2，得到非齐次递推方程的通解：(叠加)据初始条件解出特解中待定常数，得特解：,c1和c2为待定常数,c1和c2为待定常数,39,递推方程求解：k阶常系数线性递推式,公式法求解：k 阶常系数线性递推式（二阶的推广）它的齐次递推方程：方程右端项为0，即齐次方程的特征方程：（相同系数的一个 k 次方程，超越方程）,数值解法,40,递推方程求解：k阶常系数线性递推式（2）,求 k 阶齐次递推方程通解：定理1推广（1）特征方程有 k 个不相等实根 qk，齐次递推方程通解为：（2）特征方程有 r 个相等实根（重根），齐次递推方程通解为：说明：k 次特征方程有k个实根 q1,q2,.,qk,其中有r 个实根相同。这相同的 r 个实根为：,ck 为待定常数,41,递推方程求解：k阶常系数线性递推式（3）,求 k 阶非齐次递推方程特解：前面已求得其相应的齐次递推方程通解；据定理2，再求得非齐次方程的任意一个特解，则两者相加可得非齐次递推方程通解。最后，根据给定初始条件可得满足初始条件的非齐次递推方程特解。对一般的非齐次递推方程，不存在寻找特解的通用方法，只能用观察法去假定特解的形式，然后用待定系数法确定系数。1.当 f(n)是 n 的 t 次多项式时，可设特解也是n的多项式即特解形式:2.当 f(n)是n的指数函数,a,b为待定常数时，设特解形式：（1）b 不是相应齐次方程的特征根时（2）b 是相应齐次方程的 e 重特征根时,p 为待定系数,42,递推方程求解：k阶常系数线性递推式例,例：解递归方程解：1）求齐次递推方程的特征根：（特征方程的根）2）根据定理1，两个特征根不相等，齐次方程通解为：3）求非齐次方程的一个任意特解：因方程右端为n的指数形式，且b=4不是特征根，可设定特解形式：将特解代入非齐次递推方程：,43,递推方程求解：k阶常系数线性递推式例（续）,非齐次递推方程的一个特解为：4）非齐次递推方程的通解：（定理2）,5）求满足初始条件的非齐次递推方程的解（特解）：非齐次递推方程的通解中代入初始条件x(0)=0,x(1)=0,44,递推方程求解：生成函数法,生成函数法：(深入问题：选讲)前面已经讲了三种解递推方程的方法：前向替换法、反向替换法和公式解法。如果某个递推式包含了不只一个低次项，即序列的后一项需由其前面的多项来递推，那么用替换法求解较为不便和困难。公式法求解，可解常系数线性递推方程，齐次递推方程的特征方程为一元 k 次方程，求根算法一般为数值解法（近似解），特殊情况除外。对于非齐次递推方程，前面介绍了两种右端项情况：多项式型和指数型。许多递推方程至今没有找到精确解。本小节介绍生成函数法求解递推方程，该法可解替换法和公式法可解的递推方程，并且能解它们不能求解的递推方程。生成函数 A(x)：它是一个幂级数A(x)的系数是一个序列：现在已知该序列各元素满足某个递推关系，即该序列后续项可由前面项递推出来，但不知道该序列的通项（这正是我们要找的“解”）。为此，根据递推关系对生成函数作变换，求其解析表达式；然后，将其展开为x 的幂级数，其中xn 的系数就是序列的通项（递推式的解）。,45,生成函数法：例,例：用该例来说明生成函数法怎样解递推方程。,序列的下标表示法,序列的函数表示法,解：1）定义生成函数：2）利用递推式化简：其系数序列满足递推式,麦克劳林展开式,该函数展开式系数满足递推式,46,生成函数法：例（续）,4）对A(x)展开成幂级数：,将两项分别展开成幂级数，得：,当 i=n 时，xn 的系数项,分解为两个更简单的函数式,47,递推算法效率分析通用方案,递推算法效率分析通用方案（类似于非递归算法）1 确定输入规模；2 确定基本操作；（规律：它总是位于算法的最内层循环里）3 考虑基本操作的执行次数是否仅仅与输入规模有关。若还与其他因数 有关（比如顺序查找算法中基本操作执行次数还与查找键在列表中的 位置有关），则按需要对最差、最佳、平均效率作出分析。4 建立基本操作数与规模的函数关系，即递推关系和初始条件。5 解递推方程，确定增长函数的增长率。,