第2章算法分析

第2章算法分析基础学习要点:

理解算法分析的任务和目的掌握渐近标记法在算法分析中的应用掌握算法分析的方法能够分析算法的最好、最坏、平均时间复杂度

算法分析的任务：对设计出的每一个具体的算法，利用数学工具，讨论其复杂度。对算法的评价有两个大的方面：一是人对算法的维护的方便性。二是算法在实现运行时占有的机器资源的多少，即算法运行的时间和空间效率。

目的：设计和选择出复杂性尽可能低的算法来解决问题。★2.1.1时间复杂性算法运行所需要时间资源的量，T=T(n,I,A)。其中，n表示算法要解的问题的规模；

I表示算法的输入；

A表示算法本身。算法在一台抽象计算机上运行的时间。

T(n,I)=其中，ti是计算机所提供的元运算执行一次所需时间；ei是算法用到元运算Oi的次数。2.1

算法的复杂性三种情况下的时间复杂性最坏情况

Tmax(n)=max{T(I)|size(I)=n}最好情况

Tmin(n)=min{T(I)|size(I)=n}平均情况

Tavg(n)=其中，I是问题的规模为n的实例，p(I)是实例I出现的概率。2.1.2空间复杂性算法运行所需要空间资源的量，S=S(n,I,A)。其中，n表示算法要解的问题的规模；

I表示算法的输入；

A表示算法本身。算法在一台抽象计算机上运行时所占用的空间。分析起来比时间复杂性简单，本课程以时间复杂性为讨论主体。

2.1.3渐近复杂性对于T(n)，如果存在f(n)，使得当n→∞时有(T(n)-f(n))/T(n)→0，那么，就说f(n)是T(n)当n→∞时的渐近性态。又称算法A的渐近复杂性。在数学上，f(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。例如，T(n)＝3n2+4nlogn+7，则f(n)的一个答案是3n2，因为，此时有(T(n)-f(n))/T(n)=→0（当n→∞）渐近复杂性分析只关心f(n)的阶！2.2.1评价算法的准则算法正确性算法结构（健壮性）最佳性时间复杂性空间复杂性2.2算法分析的一般方法2.2.2评价算法时间复杂性的一般方法分析并确定：算法的哪些参数决定算法的“输入规模”？

原因：问题实例的输入规模较大的，算法得到输出需要更多的时间开销。明确：被分析算法的“关键操作”是什么？

关键操作：算法中重要的操作，或所关心的操作。“关键操作的数量”→“算法的时间复杂度”！

例：内排：(“比较类”)待排序元素之间的“比较”次数；待排序元素的“移动”次数。

查找：待查找值x与数据元素之间的“比较”次数。

矩阵乘法：矩阵元之间的乘法/加法运算次数。算法分析的目标：考察算法的“关键操作”数，随“问题规模”而变化的规律。提高计算速度对不同时间复杂性函数的影响对比T(n)微秒lognnnlognn2n3n52n3nn!n=103.310331001毫秒0.1秒1毫秒59毫秒3.6秒n=405.340213160064毫秒1.7分12.7天3855世纪103世纪n=605.9603543600216毫秒1.3分366世纪1.3×1013世纪1066世纪多项式函数指数函数时间复杂性函数用现在的计算机用快100倍的计算机用快1000倍的计算机nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.29算法时间复杂度的渐近表示

算法的时间开销随问题规模增大的变化趋势。例2-1：简单选择排序算法的“比较”次数

0123456…n-1a:(2,5,8,|12,9,20,15,…,66)

||↑↑

小大ij(K)voidSELECT_SORT(Typea[],intn){FOR(inti=0;i<=n-2;i++){intk=i;FOR(intj=i+1;j<=n-1;j++){IF(a[j]<a[k])k=j;};IF(k!=i)a[k]⇔a[i];};}

T(n)===n(n-1)/2

→t(n)注：n个元素存放在a[0]～a[n-1]之上！?多项式函数2.2.3算法渐近复杂性分析定义界函数设：f和g是两个函数，f,g:N→R+。若存在正整数c和n0，使得对于所有n≥n0,都有：f(n)≤cg(n)，则称g(n)是f(n)的上界，记为：

f(n)=O(g(n))理解：

ⅰ能够满足定义的g(n)，可以是一个函数集合

ⅱg(n)不小于f(n)，且g(n)是“简洁”的函数。例如，当n≥10时，有2n2+11n-10≤3n2，所以有2n2+11n-10=O(n2)O标记的运算规则：⑴

O(f(n))+O(g(n))=

O(max{f(n),g(n)})⑵O(f(n))+O(g(n))=

O(f(n)+g(n))⑶O(f(n))*O(g(n))=

O(f(n)*g(n))⑷O(cf(n))=

O(f(n))⑸g(n)=O(f(n))O(f(n))+O(g(n))=

O(f(n))若存在正整数c和n0，使得对于所有n≥n0，都有：f(n)≥cg(n)，则称g(n)是f(n)的下界，记为：

f(n)=Ω(g(n))若存在正整数c1、c2和n0，使得对于所有n≥n0，都有：c1g(n)≤f(n)≤c2g(n)，则称g(n)是f(n)的精确界，记为：

f(n)=Θ(g(n))如果对于任意c＞0，都存在非负整数n0，使得当n≥n0时，有f(n)＜

cg(n)，则称g(n)是f(n)的非紧上界，记为：

f(n)=o(g(n))如果对于任意c>0，都存在正数n0>0，使得当n≥n0时，有：f(n)＞

cg(n)，则称g(n)是f(n)的非紧下界，记为：

f(n)=

(g(n))定理1：

(g(n))=O(g(n))

(g(n))常用函数单调函数单调递增：m

n

f(m)f(n)单调递减：m

n

f(m)f(n)严格单调递增：m

<n

f(m)<f(n)严格单调递减：m

<n

f(m)>f(n)取整函数x：不大于x的最大整数

x：不小于x的最小整数多项式函数如果p(n)=a0+a1n+a2n2+…+adnd，ad>0；则

p(n)=(nd)

f(n)=O(nk)f(n)多项式有界；

f(n)=O(1)

f(n)

c;

kdp(n)=O(nk);kdp(n)=(nk);k>

dp(n)=o(nk);k<dp(n)=(nk)指数函数对于正整数m,n和实数a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1an为单调递增函数;a>1nb=o(an)ex

1+x|x|11+xex

1+x+x2

∴

当x0，有ex

=1+x+(x2)对数函数logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)kl;loglogn=log(logn);

如果a>0,b>0,c>0，则阶乘函数Stirling’sapproximation(斯特林逼近公式)：其中，例2-2：分析“计算n阶方阵A、B的乘积”算法。voidMatrixMulti(TypeA[],TypeB[],TypeC[],intn){FOR(inti=0;i<=n-1;i++){FOR(intj=0;j<=n-1;j++){C[i,j]=0;FOR(intk=0;k<=n-1;k++)C[i,j]=C[i,j]+A[i,k]*B[k,j];};};}

T(n)===

=n3=(n3)

算法的最坏情况下的复杂度设：I是问题规模为n的所有输入的集合，i∈I是问题的一个输入实例。ti(n)是输入i下，算法A的“关键操作”数。则，算法A的最坏情况复杂度：WA(n)=max{ti(n)}

i∈I例2-3：“顺序表查找”算法intSearch_line(Typea[],intn,Typex){a[n]=x;intj=0;WHILE(x!=a[j])j=j+1;IF(j==n)RETURN(0);失败

ELSERETURN(1);}

失败查找最坏特性：WAu(n)=n+1平均复杂度设：I是问题规模为n的所有输入的集合，i∈I是问题的一个输入实例。ti(n)是输入i下，算法A的“关键操作”数。Pi(n)是输入i出现在I中的概率。则，算法A的平均时间复杂度：AVA(n)=∑(Pi(n)ti(n))

i∈I例2-4：“顺序表查找”算法的平均复杂度：设：“失败”概率为q(0≤q≤1)。而且假设“成功”查找时，各种输入“等概率”，即：成功查找的输入概率为psi(n)=(1-q)/nAVA(n)=∑Pi(n)ti(n)=∑Psi(n)ti(n)+∑Pui(n)ti(n)=∑[(1-q)/n

·(j+1)]+q·(n+1)=(1-q)/n∑(j+1)+q(n+1)=(1+q)(1+n)/2i∈Isi∈I成功ui∈I失败n-1j=0n-1j=0课后作业P28：1.2.2.4算法分析实例非递归算法分析仅依赖于“问题规模”的时间复杂度例2-5：交换i和j的内容。

Temp=i;i=j;j=Temp;

以上三条基本语句的执行次数(语句频度)均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。结论：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。例2-6：变量计数之一。

(1)x=0；y=0；

(2)for(k=1;k<=n;k++)(3)x++；

(4)for(i=1;i<=n;i++)(5)for(j=1;j<=n;j++)(6)y++；该算法段的时间复杂度为T(n)=O(n2)。结论：当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。T(n)=

=n+n2n＞1时，有T(n)≤2n2=t(n)(n0=1，c=2)Tx(n)+Ty(n)=例2-7：变量计数之二。

(1)x=1;(2)for(i=1;i<=n;i++)(3)for(j=1;j<=i;j++)(4)for(k=1;k<=j;k++)(5)x++;

该算法段的基本语句是(5)，从内层循环向外层分析语句(5)的执行次数：

===则，该算法的时间复杂度为：T(n)=O(n3/6+低次项)=O(n3)算法的时间复杂度与输入实例的初始状态有关例2-8：一个简单k-选择算法(伪码)如下所示。算法思想：首先采用冒泡排序算法，按照从小到大次序，排出a数组的前k个元素，然后返回a数组的第k-1个元素。intK_SELECT(Typea[],intn,intk){p=1;//p控制“冒泡”的趟数

while(p<=k){j=n-1;while(j>=p)//进行“冒泡”，第p趟将第p小的元素交换到位

{if(a[j]<a[j-1])a[j]⇔a[j-1];j=j-1;};p=p+1;};RETURN(a[k-1]);}注：n个元素存放在a[0]～a[n-1]之上。问题规模：n，关键参数k解答以下问题：1.试分析算法的时间复杂度。即，求出数组a不同元素之间比较次数的关系表达式T(n,k)。解：显然，T(n,k)不仅与n有关，而且与k有关。

T(n,k)===k(2n–k–1)/22.问：在什么情况下，算法有最坏时间复杂度和最好时间复杂度？分别计算最好、最坏情况下的时间复杂度。

解：当k=n时，算法有最坏时间复杂度。此时，

T(n,k)=T(n,n)=n(n-1)/2

当k=1时，算法有最好时间复杂度。此时，

T(n,k)=T(n,1)=n–13.如果k在1至n之间取值等概率，请计算该算法的平均时间复杂度，并写出它的上界函数。解：∵对于一个确定的k值，算法具有时间复杂度：

T(n,k)=k(2n–k–1)/2∴算法的平均时间复杂度是对T(n,k)的“加”权平均值。故，算法的平均时间复杂度是：

A(n)=1/n

=(n2-1)/3=O(n2)→O(n2)→O(n)非递归算法分析的一般步骤：分析算法问题规模；明确关键操作；分析关键操作执行次数是否只依赖于问题规模？是，就直接建立关键操作执行次数的求和表达式，并求解；否则，分别对该算法的最好、最坏和平均情况的时间复杂度进行分析。用渐进符号表示。递归算法分析代入法（猜测法）先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。迭代法（扩展递归法）迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。通用分治递推式法这个方法针对形如“T(n)=aT(n/b)+f(n)”的递归方程。差分方程法可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。□□迭代法（扩展递归法）例2-9：求N!分析：构造算法中的两个步骤：

⑴

0!=1,1!=1⑵N!=N*(N-1)!递归算法如下：fact(intn){if(n=0orn=1)return(1);elsereturn(n*fact(n-1));}

递归方程为：T(n)=T(n-1)+O(1)，其中O(1)为一次乘法操作的执行时间。迭代求解过程如下：

T(n)=T(n-2)+O(1)+O(1)=T(n-3)+O(1)+O(1)+O(1)……=O(1)+……+O(1)+O(1)+O(1)=n*O(1)=O(n)例2-10：分析下面递推式的时间复杂度。设，n=2k∴îíì>+==15)2(217)(2nnnTnnT222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×´+++=+++=++=+=--L)(10310)212(57257)(22212102nOnnnnnnnnTkkii=£-=-+=øöçèæ+=--=å通用分治递推式法形如“T(n)=aT(n/b)+f(n)”的递归方程是分治法的时间复杂性所满足的递归关系。即一个规模为n的问题被分解为a个规模为n/b大小的子问题，分别求这a个子问题的复杂性，再合并各子问题(f(n)就是其工作量)îíì>+==1)(1)(ncnbnaTncnTkf(n)假定n=bm，则：T(n)=aT(n/b)+cnk=a(aT(n/b2)+c(n/b)k)+cnk=amT(1)+am-1c(n/bm-1)k+...+ac(n/b)k+cnk

===∵am=

=,∴有三种情况,r=：⑴r<1,<,由于am=

,所以T(n)=O()⑵r=1,=m+1=logbn+1,由于am==nk

,所以

T(n)=O(nklogbn)⑶r>1,==O(rm),所以T(n)=O(amrm)=O(bkm)=O(nk)例2-11：已知：x、y是n位二进制数（n=2r，r:非负正数），a、b、c、d与x、y的关系如下所示。试设计算法，计算p=xy，并分析算法关于二进制数运算（乘法、加法、移位）的时间复杂度。x:y:abcd算法一：p=xy=(a2n/2+b)(c2n/2+d)=ac2n+(ad+bc)2n/2+bd1)计算ac，并将结果“左移”n位；2)分别计算ad、bc，并求它们的和，再对和数“左移”n/2位；3)计算bd；4)对1)、2)、3)的结果求和。时间复杂性的递推式：其中，m为正数根据递推公式⑴可知，a=4,b=2,k=1所以有，a=4>bk=2，则上述递推式解为：

T(n)==O(n2)思考：该算法可否改进？îíì>+==1)(1)(nmn2n4TnmnTanOb)(log算法二：令：u=(a+b)(c+d),v=ac,w=bd有：p=xy=ac2n+(ad+bc)2n/2+bd=v2n+(u-v-w)2n/2+w建立递推关系式：求解递推关系式：T(n)=3T(n/2)+mn=3[3T(n/22)+m(n/2)]+mn=···=3r+1·m-2mn=3m–2mn≈3mn1.59–2mn=O(n1.59)îíì>+==1)(1)(nmn2n3TnmnTn32log2.2.5判定树模型：适用于“比较”算法判定树：是一棵满足以下条件的二叉树，每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树；每一个叶子结点表示问题的一个结果。要点:1)“内部结点”表示一次“比较”；

2)“分支”表示一次“比较”后,算法的“走向”

3)“外部结点”表示一种可能的输出。例2-6：用天平尽快找出27枚硬币中，质地较轻的一枚。a:bc1:c2c31:c32c33是“假币”a=bc1=