算法设计技巧与分析 算法分析的基本方法

2024/3/21Algorithms:

DesignTechniquesandAnalysis

算法设计技巧与分析1课程信息

学习目标熟悉算法分析的常用方法掌握算法设计的基本方法——分治法、贪心法、动态规划法、回溯法等熟悉计算机科学中经常出现的某些问题的精巧求解算法

——例如，快速排序算法、求最小生成树的prim算法等等初步具有能针对所给实际问题来设计和实现算法，以及评价算法的能力。逐步养成对于所要解决的问题，总是努力去设计出尽可能好的算法的良好习惯2课程信息教学方式课堂讲授（50学时）上机实验（6学时）考核方法期末闭卷考试70%实验作业30%3课程信息教材与教学参考资源教材：《算法设计技巧与分析》，电子工业出版社，2004.(Algorithms:DesignTechniquesandAnalysis,M.H.Alsuwaiyel)4课程信息教材与教学参考资源参考教材：[1]

算法导论（第二版影印版）高等教育出版社

,2007(IntroductiontoAlgorithms(SecondEdition),theMITPress,2001)

[2]计算机算法设计与分析，王晓东，电子工业出版社，2001。5课程主要学习内容1.算法分析的基本方法2.算法设计的基本方法

分治法动态规划法贪心法回溯法分枝限界法3.算法设计的其它方法6

1.

算法分析的基本方法1.1.算法及其特性1.2.衡量一个算法性能的好坏的标准1.3.算法的时间和空间复杂度1.4.算法分析(AlgorithmAnalysis)1.4.1.分析算法时间复杂度的基本步骤1.4.2.算法时间复杂度的有关概念1.4.3.几种典型算法举例1.4.4.分析、求解算法复杂度的方法1.5.最优算法(optimalalgorithm)7

1.1.算法及其特性算法（algorithm）：算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。算法的五个特性：确定性：组成算法的每条指令是清晰的，无歧义的。能行性：算法中的任何计算步都可以在有限时间内完成。有穷性：算法必须能在执行有限个步骤之后终止。输入：有0个或多个由外部提供的量作为输入。输出：算法产生至少一个量作为输出。8

1.2.

衡量算法性能的标准衡量算法性能一般有下面几个标准正确性：算法能够正确地完成所要解决的问题。易读性：算法清晰易懂。健壮性：算法除了能对合法的输入数据得到正确的结果外, 还应对非法的输入数据做出正确合理的处理。

算法的时间和空间性能：高效率和低存储空间我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。9

1.3.算法的时间和空间复杂度时间复杂度（TimeComplexity）算法的时间复杂度：在算法运行期间所花费的时间。通常用渐进形式表示比如，T(n)=

(n2)、

(n2)或

(n2)空间复杂度（SpaceComplexity）

算法的空间复杂度：在算法运行期间所需要的内存空间。一般是指，除开容纳输入数据之外的附加空间（auxiliaryspace,orworkspace）。通常用渐进形式表示比如，S(n)=

(n2)、

(n2)或

(n2)10

1.4.算法分析(AlgorithmAnalysis)算法分析：对于算法的时间和空间复杂度进行定量分析。分析算法时间复杂度的基本步骤算法时间复杂度的有关概念分析、求解算法复杂度的基本方法111.4.1.分析时间复杂度的基本步骤一、选取一种运算作为基本运算

二、表示出在算法运行期间基本运算执行的总频数三、渐近时间复杂度（asymptotictimecomplexity）12渐近表示的记号—O-记号设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c>0和一个自然数n0，使得对于任意的n

n0

，均有

f(n)

cg(n),

则f(n)=O(g(n))13渐近表示的记号—

-记号设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c>0和一个自然数n0，使得对于任意的n

n0

，均有

f(n)

cg(n),

则f(n)=

(g(n))14渐近表示的记号—

-记号设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在一个自然数n0和两个正常数c1，c2，使得对于任意的n

n0

，均有

c1g(n)

f(n)

c2

g(n),

则f(n)=

(g(n))15[例1]

设f(n)=10n2+20n。则有f(n)=O(n2)f(n)=

(n2)f(n)=

(n2)[例2]

设f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak>0)。则有f(n)=O(nk)f(n)=

(nk)：f(n)=

(nk)

由此可见，复杂度的渐近表示可以简洁地表示出复杂度的数量级别。渐近表示—Examples16渐近表示—Examples17渐近表示—Examples18渐近表示—Examples191.4.2.算法时间复杂度的有关概念

对于算法的时间复杂度，通常分平均、最坏、最好几种情形来衡量，尤其是前两种。算法的平均复杂性

算法的最坏复杂性算法的最好复杂性

201.4.2.算法时间复杂度的有关概念[例1]

检索问题的顺序查找算法以元素的比较作为基本操作。考虑成功检索的情况。最好情况下的时间复杂度：

(1)最坏情况下的时间复杂度：

(n)在等概率前提下，平均情况下的时间复杂度：

(n)[例2]

直接插入排序算法以元素的比较作为基本操作。最好情况下的时间复杂度：

(n)最坏情况下的时间复杂度：

(n2)在等概率前提下，平均情况下的时间复杂度：

(n2)211.4.3.几种典型算法举例二分搜索合并两个已排序的表选择排序插入排序自底向上合并排序22二分搜索问题：设A[1..n]为n个元素的数组，判定给定元素x是 否在A中。 即：寻找索引j，1≤j≤n，如果x在A中，有x=A[j]，否则j=0。算法1：扫描A中的所有项目，将每个项目与x比较，如果在j次比较后搜索成功，即x=A[j]，则返回j的值，否则返回0。这种方法称为顺序搜索或线性搜索。算法如下：23二分搜索如果A中的元素按升序排列，则有：24二分搜索25二分搜索算法分析算法分析 假定每个三向比较(if-then-else)记为一次比较，显然最小的比较次数是1，即被搜索的元素x在序列的中间位置。 对于最大的比较次数，可以假定x大于等于将要搜索的序列中的所有元素。因此，第二次迭代A[mid+1…n]中元素恰好是。类似地，第三次迭代时，要搜索的剩余元素的数目是。依次类推，经过j次循环后的剩余元素是。此时，或者找到x，或者要搜索的子序列的长度为1。故搜索x的最大循环数就是满足条件=1时的j值。26二分搜索算法分析

根据底函数的定义，有 即 有:

因为j是整数，可得：

27二分搜索算法分析定理1.1

对于一个大小为n的排序数组，算法BINARYSEARCH执行比较的最大次数为 。28合并两个已排序的表问题： 假定有一个数组A[1..m]，p,q,r为它的三个索引，并有1≤p≤q<r≤m，两个子数组A[p…q]和A[q+1…r]各自按升序排列，要求重新安排A中元素的位置，使得子数组A[p…r]也按升序排列。29合并两个已排序的表思路：

这其实就是合并A[p…q]和A[q+1…r]的过程。使用两个指针s和t，初始化时各自指向A[p]和A[q+1]，再用一个空数组B[p…r]做临时变量。每一次比较元素A[s]和A[t]，将小的元素添加到辅助数组B，如果相同就把A[s]添加进行。然后更新指针，如果A[s]A[t]，则s加1，否则t加1，当条件s=q+1或t=r+1成立时过程结束。在第一种情况下，我们把数组A[t…r]中剩余的元素添加到B，而在另一种情况下，把数组A[s…q]中剩余的元素添加到B。最后，把数组B[p…r]复制回A[p….r]。30合并两个已排序的表31合并两个已排序的表32合并两个已排序的表33选择排序思路

设A[1…n]为一个有n个元素的数组，选择排序的思路如下：首先找到最小元素，将其存放在A[1]中，然后找到剩下的n-1个元素中的最小元素，将其存放在A[2]中，重复此过程直至找到第二大的元素，并将其存放在A[n-1]中。34选择排序35选择排序36插入排序思路

插入排序方法如下：从大小为1的子数组A[1]开始，它自然是排好序的，接下来将A[2]插入到A[1]的前面或后面，则取决于A[2]比A[1]小还是大。对于第i次执行，依次扫描序号从i-1到1的元素，每次都将A[i]和当前位置的元素比较。这样，或者找到一个小于等于A[i]的元素，或者前面已排序数组的元素都已扫描过。此时，A[i]已被插入到合适的位置。37插入排序38插入排序39插入排序40自低向上合并排序例：假定要对如下8个数字的数组排序

可以按下面的方法进行：41自低向上合并排序思路42自低向上合并排序43自低向上合并排序分析44自低向上合并排序分析45自低向上合并排序分析461.4.4.分析、求解算法复杂度的方法数学基础典型的求和公式积分近似求和递归关系47典型的求和公式

0i

n

f(i)

1i

n

i=n(n+1)/2=

(n2)

1i

n

(a+bi)=na+bn(n+1)/2=

(n2)

1i

n

i2=n(n+1)(2n+1)/6=

(n3)

1i

n

ik=

(nk+1)

0i

n

ai=(1–an+1)/(1–a)=

(an)(a

1)

特别地，

0i

∞

ai=1/(1–a)(|a|<1)

0i

n

ai=

(1)(|a|<1)

0i

n

iai=

(nan)(a

1)48

积分近似求和如果连续函数f(n)是单调递减的，则有

mn+1

f(x)

m

j

n

f(j)

m-1n

f(x)如果连续函数f(n)是单调递增的，则有

m-1n

f(x)

m

j

n

f(j)

mn+1

f(x)49

积分近似求和[例1]

1

j

njk(k>1)50

积分近似求和51

积分近似求和[例2]

1

j

n

1/j=

(logn)52

积分近似求和53

积分近似求和[例3]

1

j

n

logj=

(nlogn)54

递归关系(I)线性齐次递归方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k),(n

k)(II)线性非齐次递归方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k)+f(n),(n

k)(III)分而治之型递归方程

T(n)=a1T(n/c1)+a2T(n/c2)+…+apT(n/cp)+f(n),(n>n0)55

递归关系

常用方法差分方程法展开法换元法数学归纳法56(I)线性齐次递归方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k),n

k

初始条件（略）。

主要解法：差分方程法

递归关系57[例1]

f(n)=3f(n1)+4f(n2),n>1；初始条件：f(0)=1，f(1)=4

递归关系tn是递归方程的解(忽略初始条件)

t是对应特征方程的根Step1Step2Step3Step4

特征方程为：t2

3t

4=0。解得t1=4,t2=

1。于是，f(n)=c1·4n+c2·(

1)n（n

0），其中c1,c2待定。所以，f(n)=4n

（n

0）解：

由f(0)=1,f(1)=4有：c1+c2=14c1

c2=4由此得c1=1,c2=0。58

递归关系[例2]

f(n)=4f(n

1)

4f(n

2),n>1；初始条件：f(0)=6,f(1)=8。解：

特征方程为：t2

4t+4=0。解得t1=t2=2。于是，f(n)=c1·2n+c2·n·2n

（n

0），其中c1，c2待定。由f(0)=6，f(1)=8有：c1=6，

2c1+2c2=8。由此得c1=6,c2=

2。所以，f(n)=3·2n+1

n·2n+1（n

0）59

递归关系(II)线性非齐次递归方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k)+f(n),(n

k)

初始条件（略）。主要解法：差分方程法60

递归关系[例3]

T(n)=T(n-1)+T(n-2)+b,n>1，初始条件：T(1)=T(0)=a,这里a，b均为非负常数。tn是递归方程齐次部分的解

(忽略初始条件)

t是对应特征方程的根解：

特征方程为：t2

t

1=0，解得t1=(1+51/2)/2,t2=(1

51/2)/2。显然，T(n)=

b是方程的一个特解。于是，T(n)=c1·t1n+c2·t2n

b(n

0)

，其中c1，c2待定。由T(0)=a，T(1)=a有：c1+c2

b=a

c1·t1+c2·t2

b=a

由此得c1=？c2=？所以，T(n)=c1·t1n+c2·t2n

b

（n

0）其渐近表示为：T(n)=(((1+51/2)/2)n)Step1Step2Step3Step4Step561说明：与上例相关的一个算法例子是，Fibonacci数列的第n+1项该数列的定义为：

F0=F1=1,Fi=Fi-1+

Fi-2，i2。由这一数学定义自然地导出一个递归算法。

intF(intn){ if(n==0||n==1)return1;elseif(n>=2)returnF(n

1)+F(n

2);}

该算法计算时间T(n)满足的递归方程呈上例形式。

递归关系62

[例4]河内塔问题的递归求解算法如下(C++描述)：voidHanoi(intn,chara,charb,charc){if(n>0){ Hanoi(n

1,a,c,b);cout<<“MoveDiskNo.”<<n<<“fromPile”<<a<<“to”<<c<<endl;Hanoi(n

1,b,a,c);}}

递归关系63递归关系

使用输出语句为基本操作。若用T(n)表示该算法的计算时间，则有

T(n)=2T(n

1)+1,n>1T(1)=1。

使用展开法、差分法或数学归纳法可得：

T(n)=2n

1,

即T(n)=(2n)。64(III)分而治之型递归方程

e.g.

f(n)=af(n/b)+g(n),n>1，初始条件：f(1)=c,这里的a,b,c均是正常数。说明：考虑这样的递归过程：它把大小为n的问题分成了a个大小为n/b的子问题去解。设大小为1的问题需要c个单位时间，把a个子问题的解合并成原问题的解需要g(n)个单位时间。用f(n)表示大小为n的问题的计算时间，则得上述递归方程。

递归关系65[例5]

解递归方程

f(n)=2f(n/2)+bnlogn,n>1;

初始条件：f(1)=d

。其中b和d都是非负实数，n=2k。解法1：（展开法）令g(n)=bnlogn，则f(n)=f(2k)=2f(2k-1)+g(2k)=22f(2k-2)+2g(2k-1)+g(2k)……=2kf(20)+∑i=0k-12ig(2k-i)=2kd+∑i=0k-12i·b·2k-i·log2k–i=n·d+b·2k∑i=0k-1(k-i)

=n·d+b·n∑i=1ki

=n·d+b·n·k(k+1)/2

=n·d+b·n·logn·(logn+1)/2（注意：由n=2k

有k=logn）所以，

f