算法设计与分析基础第2版算法分析第2章-课件

第2章算法效率分析基础我常常说，当你对所讲的内容能够进行度量并且能够用数字来表达时，证明你对这些内容是有所了解的；如果你不能用数字来表达，那么你的认识是不完整的，也是无法令人满意的.-------LordKelvin(1824-1907)

第2章算法效率分析基础我常常说，当你对所讲的内12.1分析框架在本节中,我们将概要地描述一个分析算法效率的一般性框架.首先必须指出,有两种算法效率:时间效率和空间效率。时间效率指出正在讨论的算法运行得有多快；空间效率关心算法需要的额外空间。研究实验告诉我们，对于大多数问题来说，我们在速度上能够取得的进展要远大于在空间上的进展，所以我们把主要精力集中在时间效率上。2.1分析框架在本节中,我们将概要地描述一个分析算法效率的22.1.1输入规模的度量几乎所有的算法，对于规模更大的输入都需要动行更长的时间。例如，需要更多时间来对更长的数组排序，更大的矩阵相乘也需要花费更多时间，等等。所以，使用一个以算法输入规模式n为参数的函数，来研究算法效率是非常合乎逻辑的。2.1.1输入规模的度量32.1.2运行时间的度量单位

我们把基本操作作为算法运行时间的度量单位。所谓基本操作，就是算法中最重要的操作。它们对总运行时间的贡献最大。我们的下一步工作就是计算它们的运行次数。掌握了这样一种规律，我们就不难发现一个算法中的基本操作：它通常是算法最内层循环中最费时的操作。例如，大多数排序算法是通过比较列表中的待排序元素（键）来进行工作的；对于这种算法来说，基本操作就是对键的比较。

2.1.2运行时间的度量单位42.1.3增长次数

为什么对于大规模的输入要强调执行次数的增长次数呢？这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。

2.1.3增长次数

为什么对于大规模的输入要强调执5算法设计与分析基础第2版算法分析第2章-课件62.1.4算法的最优、最差和平均效率一个算法的最差效率是指当输入规模为n时，算法的最坏情况下的效率。这时，相对于其他规模为n的输入，该算法的运行时间最长。一个算法的最优效率是指当输入规模为n时，算法在最优情况下的效率。这时，与其它规模为n的输入相比，该算法运行得最快。然而，无论是最差效率分析还是最优效率分析都不能提供一种必要的信息：在“典型”或者“随机”输入的情况下，一个算法会具有什么样的行为。这正是平均效率试图提供给我们信息。还有一种类型的效率称为摊销效率。它并不适用于算法的单次运行，而是应用于算法对同样数据结构所执行的一系列操作。2.1.4算法的最优、最差和平均效率72.1.5分析框架概要算法的时间效率和空间效率都用输入规模的函数进行度量。我们用算法基本操作的执行次数来度量算时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。在输入规模相同的情况下，有些算法的效率会的显著差异。对于这样的算法，我们需要区分最差效率，平均效率和最优效率。本框架主要关心，当算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）函数的增长次数。2.1.5分析框架概要82.2渐进符号和基本效率类型2.2.1非正式的介绍非正式来说，O(g(n))是增长次数小于等于是g(n)(以及其常数倍，n趋向于无穷大)的函数集合。n∈O(n2),100n+5∈O(n2),1/2(n(n-1))∈O(n2),n3∈/O(n2),第二个符号Ω(g(n))，代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。

n3∈Ω(n2)，1/2(n(n-1))∈Ω(n2)，但是100n+5∈/Ω(n2)最后，Θ(g(n))是增长次数等于g(n))(以及其常数倍,n趋向于无穷大)的函数集合。因些，每一个二次方程an2+bn+c在a>0的情况下都包含在Θ(n2)中，除了无数类似于n2+sinn和n2+logn的函数（你能解释原因吗？）。2.2渐进符号和基本效率类型2.2.1非正式的介绍92.2.2符号О

定义1我们把函数t(n)属于O(g(n))，记作t(n)∈

O(g(n));它的成立条件是：对于所有足够大的n，t(n)的上界由g(n)的常数倍数所确定，也就是说，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥n0来说，t(n)≤cg(n)n0之前的情况无关重要cg(n)t(n)n符号O：t(n)∈O(g(n))n02.2.2符号Оn0之前的情况无关重要cg(n)t(n)n102.2.3符号Ω定义2我们把函数t(n)属于Ω(g(n))，记作t(n)∈Ω(g(n))，它的成立条件是：对于所有足够大的n，t(n)的下界由g(n)的常数倍所确定，也就是说，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥n0来说，t(n)≥cg(n)n0之前的情况无关重要cg(n)t(n)n符号Ω：t(n)∈Ω(g(n))n02.2.3符号Ωn0之前的情况无关重要cg(n)t(n)n112.2.4符号Θ定义3我们把函数t(n)属于Θ(g(n))，记作t(n)∈Θ(g(n));它的成立条件是：对于所有足够大的n，t(n)的上界和下界都由g(n)的常数倍数所确定，也就是说，存在大于0的常数c1，c2和和非负的整数n0，使得：对于所有的n≥n0来说，c2g(n)≤t(n)≤c1g(n)n0之前的情况无关重要c1g(n)t(n)n符号Θ：t(n)∈Θ(g(n))n0c2g(n)2.2.4符号Θn0之前的情况无关重要c1g(n)t(n122.2.5渐进符号的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，则t1(n)+t2(n)∈O(max{g1(n),g2(n)})(对于Ω和Θ符号，类似的断言也为真)对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分.2.2.5渐进符号的有用特性132.2.6利用极限比较增长次数虽然符号O，Ω和Θ的正式定义对于证明它们的抽象性质是不可缺少的，但我们很小直接用它们来比较两个特定函数的增长次数。有一种较为简便的比较方法，它是基于对所计论的两个函数的比率求极限。有3种极限情况会发生：2.2.6利用极限比较增长次数142.2.7基本的效率类型

1constantlognlogarithmicnlinearnlognnlognn2quadraticn3cubic2nexponentialn!factorial2.2.7基本的效率类型1constantlognloga15练习Problem2,4.b,5,and6.aP48练习Problem2,4.b,5,and6.a162.3非递归算法的数学分析例1考虑一下从n个元素的列表中查找元素最大值的问题.简单起见,我们假设列表是用数组实现的。下面给出一个解决问题的标准算法的伪代码。算法MaxElement(A[0..n-1])

//求给定数组中最大元素的值//输入：实数数组A[0..n-1]//输出：A中最大元素的值maxval←A[0]fori←1ton-1doifA[i]>maxvalmaxval←A[i]returnmaxval2.3非递归算法的数学分析例1考虑一下从n个元素的列表中查17如何确定基本操作呢？由于做每一次循环都会进行一次比较，所以把比较作为基本操作如何确定基本操作呢？18我们把C(n)记作比较运算的执行次数,并试图寻找一个公式将它表达为规模n的函数。由于该算法每执行一次循环就会做一次比较，并且对于循环变量i在1和n-1(包含在内)中的每个值都会做一次循环，所以，我们得到C(n)的下列求和表达式：

我们把C(n)记作比较运算的执行次数,并试图寻找一个19分析非递归算法效率的通用方案1.决定用哪个(哪些)参数作为输入规模的度量2.找出算法的基本操作（作为一规律，它总是位于算法的最内层循环中）。检查基本操作的执行次数是否只依赖输入规模。如果它还依赖一些其他的特性，则最差效率、平均效率以及最优效率（如果必要）需要分别研究。建立一个算法基本操作执行次数的求和表达式。利用求和运算的标公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。分析非递归算法效率的通用方案1.决定用哪个(哪些)参20例2考虑一下元素惟一性问题：验证给定数组中的元素是否全部惟一。下面这个简单直接的算法可以解决该问题。算法UniqueElements(A[0..n-1])//验证给定数组中的无素是否全部惟一//输入：数组A[0..n-1]//输出：如果A中的元素全部惟一，返回“true”//否则，返回“false”.fori←1ton-2doforj←i+1ton-1doifA[i]=A[j]returnfalseReturntrue例2考虑一下元素惟一性问题：验证给定数组中的元素是否全部惟21基本操作：比较除了和n有关外，还取决于数组中是否有相同的元素，以及它们在数组中的位置必须研究其最优，平均和最差效率基本操作：比较22这个结果是完全可以预测的：在最坏的情况下，对于n个元素的所有n(n-1)/2对两两组合，该算法都要比较一遍。这个结果是完全可以预测的：在最坏的情况下，对于n个元素的所有23矩阵乘法Algorithm

MatrixMultiplication(A[0..n-1,0..n-1],B[0..n-1,0..n-1])//Multipliestwosquarematricesofordernbythedefinition-basedalgorithm//Input:twon-by-nmatricesAandB//Output:MatrixC=ABfori0ton-1do forj0ton–1do C[i,j]0.0 fork0ton–1do C[i,j]C[i,j]+A[i,k]*B[k,j]returnC矩阵乘法AlgorithmMatrixMultiplica24乘法次数乘法次数252.4递归算法的数学分析例1对于任意非负整数n,计算阶乘函数F(n)=n!的值。因为当n≥1时，n!=1·…·(n-1)·n=(n-1)!·n并且根据定义，0!=1，我们可以使用下面的递归算法计算F(n)=F(n-1)·n2.4递归算法的数学分析例1对于任意非负整数n,计算阶乘26算法F(n)

//递归计算n!//输入：非负整数n//输出：n!的值ifn=0return1elsereturnF(n-1)*n我们用n本身来指出算法的输入规模（而不是它的二进制表示的比特数）。该算法的基本操作是乘法，我们把它的执行次数记作M(n)。算法设计与分析基础第2版算法分析第2章-课件27因为函数F(n)的计算是根据下面公式：当n>0时，F(n)=F(n-1)*n所以，计算这个公式时，用到的乘法数量M(n)需要满足这个等式：当n>0时，M(n)=M(n-1)+1的确，计算F(n-1)需要用M(n-1)次乘法，还有一次乘法用来把该结果乘法n。为了确定一个惟一解，我们还需要一初始条件来告诉我们该序列的起始值。因为函数F(n)的计算是根据下面公式：28为了得到这个起始值，我们可以观察该算法停止递归调归调用时的条件：ifn=0return1所以，我们所遵循的初始条件是：M(0)=0这样，我们成功地建立了关于该算法的乘法次数M(n)的递推关系和初始条件：当n>0时，M(n)=M(n-1)+1M(0)=0最终结果为M(n)=M(n-1)+1=…=M(n-i)+i=…=M(n-n)+n=n为了得到这个起始值，我们可以观察该算法停止递归调归调用时的条29分析递归算法效率的通用方案决定用哪个（哪些）参数作为输入规模的度量。找出算法的基本操作。检查一下，对于相同规模的不同输入，基本操作的执行次数是否不同。如果不同，则必须对最差效率、平均效率以及最优效率作单独研究。对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。解这个递推式，或者至少确定它有解的增长次数。分析递归算法效率的通用方案决定用哪个（哪些）参数作为输入规模30练习Exercise2.3,P54Problem6Exercise2.4,P61-62Problem1,partb.,c.,e.Problem7练习Exercise2.3,P54312.5例题：斐波那契数列斐波那契数列—0,1,1,2,3,5,8,13,21,34,…这个数列可以用一个简单的递推式和两个初始条件来定义：当n>1时，F(n)=F(n-1)+F(n-2)F(0)=0,F(1)=1算法F(n)//根据定义，递归计算第n个斐波那契数//输入：一个非负整数n//输出：第n个斐波那契数ifn≤returnnelsereturnF(n-1)+F(n-2)2.5例题：斐波那契数列32该算法的基本操作很明显是加法，我们把A(n)定义为这个算法在计算F(n)的过程中所做的加法次数。因而，计算F(n-1)和F(n-2)所需要的加法次数分别是A(n-1)和A(n-2)，而该算法还需要做一次加法来计算它们的和。因此，对于A(n)我们有下面的递推式：当n>1时，A(n)=A(n-1)+A(n-2)+1从递推式中，我们可以预计到该算法的效率不高。的确，它包含两个递归调用，而这两个调用的规模仅比n略小一点。通过观察该算法的递归调用树，我们也能发现该算法效率低下的原因。相同的函数值被一遍一遍地重复计算，这很明显是一种效率低下的做法。该算法的基本操作很明显是加法，我们把A(n)定义为这33F(4)F(5)F(3)F(3)F(2)F(2)F(1)F(1)F(2)F(1)F(0)F(1)F(0)F(1)F(0)n=5时，计算斐波那契数的递归调用树F(4)F(5)F(3)F(3)F(2)F(2)F(1)F(34通过简单地对斐波那契数列的连续元素进行迭代计算，我们得到了一个快得多的算法，就像下面的这个算一样：算法Fib(n)//根据定义，迭代计算第n个斐波那契数//输入：一个非负整数n//输出：第n个斐波那契数F[0]←0;F[1]←1fori←2tondoF[i]←F[i-1]+F[i-2]returnF(n)很明显，这个算法要做n-1次加法运算。所以，它和n一样都是线性函数，“仅在”作为n的二进制位数的函数时，才表现为指出级函数。注意，没有必要特意使用一个数组在存储斐波那契数列的前面元素：为了完成该任务，只需要存储两个元素就足够了。通过简单地对斐波那契数列的连续元素进行迭代计算，我们35第2章算法效率分析基础我常常说，当你对所讲的内容能够进行度量并且能够用数字来表达时，证明你对这些内容是有所了解的；如果你不能用数字来表达，那么你的认识是不完整的，也是无法令人满意的.-------LordKelvin(1824-1907)

第2章算法效率分析基础我常常说，当你对所讲的内362.1分析框架在本节中,我们将概要地描述一个分析算法效率的一般性框架.首先必须指出,有两种算法效率:时间效率和空间效率。时间效率指出正在讨论的算法运行得有多快；空间效率关心算法需要的额外空间。研究实验告诉我们，对于大多数问题来说，我们在速度上能够取得的进展要远大于在空间上的进展，所以我们把主要精力集中在时间效率上。2.1分析框架在本节中,我们将概要地描述一个分析算法效率的372.1.1输入规模的度量几乎所有的算法，对于规模更大的输入都需要动行更长的时间。例如，需要更多时间来对更长的数组排序，更大的矩阵相乘也需要花费更多时间，等等。所以，使用一个以算法输入规模式n为参数的函数，来研究算法效率是非常合乎逻辑的。2.1.1输入规模的度量382.1.2运行时间的度量单位

我们把基本操作作为算法运行时间的度量单位。所谓基本操作，就是算法中最重要的操作。它们对总运行时间的贡献最大。我们的下一步工作就是计算它们的运行次数。掌握了这样一种规律，我们就不难发现一个算法中的基本操作：它通常是算法最内层循环中最费时的操作。例如，大多数排序算法是通过比较列表中的待排序元素（键）来进行工作的；对于这种算法来说，基本操作就是对键的比较。

2.1.2运行时间的度量单位392.1.3增长次数

为什么对于大规模的输入要强调执行次数的增长次数呢？这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。

2.1.3增长次数

为什么对于大规模的输入要强调执40算法设计与分析基础第2版算法分析第2章-课件412.1.4算法的最优、最差和平均效率一个算法的最差效率是指当输入规模为n时，算法的最坏情况下的效率。这时，相对于其他规模为n的输入，该算法的运行时间最长。一个算法的最优效率是指当输入规模为n时，算法在最优情况下的效率。这时，与其它规模为n的输入相比，该算法运行得最快。然而，无论是最差效率分析还是最优效率分析都不能提供一种必要的信息：在“典型”或者“随机”输入的情况下，一个算法会具有什么样的行为。这正是平均效率试图提供给我们信息。还有一种类型的效率称为摊销效率。它并不适用于算法的单次运行，而是应用于算法对同样数据结构所执行的一系列操作。2.1.4算法的最优、最差和平均效率422.1.5分析框架概要算法的时间效率和空间效率都用输入规模的函数进行度量。我们用算法基本操作的执行次数来度量算时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。在输入规模相同的情况下，有些算法的效率会的显著差异。对于这样的算法，我们需要区分最差效率，平均效率和最优效率。本框架主要关心，当算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）函数的增长次数。2.1.5分析框架概要432.2渐进符号和基本效率类型2.2.1非正式的介绍非正式来说，O(g(n))是增长次数小于等于是g(n)(以及其常数倍，n趋向于无穷大)的函数集合。n∈O(n2),100n+5∈O(n2),1/2(n(n-1))∈O(n2),n3∈/O(n2),第二个符号Ω(g(n))，代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。

n3∈Ω(n2)，1/2(n(n-1))∈Ω(n2)，但是100n+5∈/Ω(n2)最后，Θ(g(n))是增长次数等于g(n))(以及其常数倍,n趋向于无穷大)的函数集合。因些，每一个二次方程an2+bn+c在a>0的情况下都包含在Θ(n2)中，除了无数类似于n2+sinn和n2+logn的函数（你能解释原因吗？）。2.2渐进符号和基本效率类型2.2.1非正式的介绍442.2.2符号О

定义1我们把函数t(n)属于O(g(n))，记作t(n)∈

O(g(n));它的成立条件是：对于所有足够大的n，t(n)的上界由g(n)的常数倍数所确定，也就是说，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥n0来说，t(n)≤cg(n)n0之前的情况无关重要cg(n)t(n)n符号O：t(n)∈O(g(n))n02.2.2符号Оn0之前的情况无关重要cg(n)t(n)n452.2.3符号Ω定义2我们把函数t(n)属于Ω(g(n))，记作t(n)∈Ω(g(n))，它的成立条件是：对于所有足够大的n，t(n)的下界由g(n)的常数倍所确定，也就是说，存在大于0的常数c和非负的整数n0，使得：对于所有的n≥n0来说，t(n)≥cg(n)n0之前的情况无关重要cg(n)t(n)n符号Ω：t(n)∈Ω(g(n))n02.2.3符号Ωn0之前的情况无关重要cg(n)t(n)n462.2.4符号Θ定义3我们把函数t(n)属于Θ(g(n))，记作t(n)∈Θ(g(n));它的成立条件是：对于所有足够大的n，t(n)的上界和下界都由g(n)的常数倍数所确定，也就是说，存在大于0的常数c1，c2和和非负的整数n0，使得：对于所有的n≥n0来说，c2g(n)≤t(n)≤c1g(n)n0之前的情况无关重要c1g(n)t(n)n符号Θ：t(n)∈Θ(g(n))n0c2g(n)2.2.4符号Θn0之前的情况无关重要c1g(n)t(n472.2.5渐进符号的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，则t1(n)+t2(n)∈O(max{g1(n),g2(n)})(对于Ω和Θ符号，类似的断言也为真)对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分.2.2.5渐进符号的有用特性482.2.6利用极限比较增长次数虽然符号O，Ω和Θ的正式定义对于证明它们的抽象性质是不可缺少的，但我们很小直接用它们来比较两个特定函数的增长次数。有一种较为简便的比较方法，它是基于对所计论的两个函数的比率求极限。有3种极限情况会发生：2.2.6利用极限比较增长次数492.2.7基本的效率类型

1constantlognlogarithmicnlinearnlognnlognn2quadraticn3cubic2nexponentialn!factorial2.2.7基本的效率类型1constantlognloga50练习Problem2,4.b,5,and6.aP48练习Problem2,4.b,5,and6.a512.3非递归算法的数学分析例1考虑一下从n个元素的列表中查找元素最大值的问题.简单起见,我们假设列表是用数组实现的。下面给出一个解决问题的标准算法的伪代码。算法MaxElement(A[0..n-1])

//求给定数组中最大元素的值//输入：实数数组A[0..n-1]//输出：A中最大元素的值maxval←A[0]fori←1ton-1doifA[i]>maxvalmaxval←A[i]returnmaxval2.3非递归算法的数学分析例1考虑一下从n个元素的列表中查52如何确定基本操作呢？由于做每一次循环都会进行一次比较，所以把比较作为基本操作如何确定基本操作呢？53我们把C(n)记作比较运算的执行次数,并试图寻找一个公式将它表达为规模n的函数。由于该算法每执行一次循环就会做一次比较，并且对于循环变量i在1和n-1(包含在内)中的每个值都会做一次循环，所以，我们得到C(n)的下列求和表达式：

我们把C(n)记作比较运算的执行次数,并试图寻找一个54分析非递归算法效率的通用方案1.决定用哪个(哪些)参数作为输入规模的度量2.找出算法的基本操作（作为一规律，它总是位于算法的最内层循环中）。检查基本操作的执行次数是否只依赖输入规模。如果它还依赖一些其他的特性，则最差效率、平均效率以及最优效率（如果必要）需要分别研究。建立一个算法基本操作执行次数的求和表达式。利用求和运算的标公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。分析非递归算法效率的通用方案1.决定用哪个(哪些)参55例2考虑一下元素惟一性问题：验证给定数组中的元素是否全部惟一。下面这个简单直接的算法可以解决该问题。算法UniqueElements(A[0..n-1])//验证给定数组中的无素是否全部惟一//输入：数组A[0..n-1]//输出：如果A中的元素全部惟一，返回“true”//否则，返回“false”.fori←1ton-2doforj←i+1ton-1doifA[i]=A[j]returnfalseReturntrue例2考虑一下元素惟一性问题：验证给定数组中的元素是否全部惟56基本操作：比较除了和n有关外，还取决于数组中是否有相同的元素，以及它们在数组中的位置必须研究其最优，平均和最差效率基本操作：比较57这个结果是完全可以预测的：在最坏的情况下，对于n个元素的所有n(n-1)/2对两两组合，该算法都要比较一遍。这个结果是完全可以预测的：在最坏的情况下，对于n个元素的所有58矩阵乘法Algorithm

MatrixMultiplication(A[0..n-1,0..n-1],B[0..n-1,0..n-1])//Multipliestwosquarematricesofordernbythedefinition-basedalgorithm//Input:twon-by-nmatricesAandB//Output:MatrixC=ABfori0ton-1do forj0ton–1do C[i,j]0.0 fork0ton–1do C[i,j]C[i,j]+A[i,k]*B[k,j]returnC矩阵乘法AlgorithmMatrixMultiplica59乘法次数乘法次数602.4递归算法的数学分析例1对于任意非负整数n,计算阶乘函数F(n)=n!的值。因为当n≥1时，n!=1·…·(n-1)·n=(n-1)!·n并且根据定义，0!=1，我们可以使用下面的递归算法计算F(n)=F(n-1)·n2.4递归算法的数学分析例1对于任意非负整数n,计算阶乘61算法F(n)

//递归计算n!//输入：非负整数n//输出：n!的值ifn=0return1elsereturnF(n-1)*n我们用n本身来指出算法的输入规模（而不是它的二进制表示的比特数）。该算法的基本操作是乘法，我们把它的执行次数记作M(n)。算法设计与分析基础第2版算法分析第2章-课件62因为函数F(n)的计算是根据下面公式：当n>0时，F(n)=F(n-1)*n所以，计算这个公式时，用到的乘法数量M(n)需要满足这个等式：当n>0时，M(n)=M(n-1)+1的确，计算F(n-1)需要用M(n-1)次乘法，还有一次乘法用来把该结果乘法n。为了确定一个惟一解，我们还需要一初始条件来告诉我们该序列的起始值。因为函数F(n)的计算是根据下面公式：63为了得到这个起始值，我们可以观察该算法停止递归调归调用时的条件：ifn=0return1所以，我们所遵循的初始条件是：M(0)=0这样，我们成功地建立了关于该算法的乘法次数M(n)的递推关系和初始条件：当n>0时，M(n)=M(n-1)+1M(0)=0最终结果为M(n)=M(n-1)+1=…=M(n-i)+i=…=M(n-n)+n=n