计算机算法设计与分析

第一章绪论计算机与软件学院（Schoolof

ComputerandSoftware）NanjingUniversityofInformationScience&Technology第一章绪论

1.1算法的概念及其特性

1.2衡量算法性能的标准1.3算法的时间和空间复杂度1.4算法分析1.5最优算法1.6高效算法的必要性“算法设计与分析”主要研究内容是：如何通过计算机将一个给定的输入高效地转化为所需要的输出。包括：

算法设计算法分析1.1算法的概念及其特性算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。一、算法的定义算法的形式化定义：算法是一个四元组(Q,I,Ω,F)其中：Q是包含子集I和Ω的集合,表示计算的状态.

I、Ω分别表示计算的输入、输出集合.

F表示计算的规则,它是一个由Q到它自身的函数,且具有自反性,即对于任何qQ,有F(q)=q.computer输入输出问题算法抽象二、算法的特性算法的5个特性：输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性(definiteness)：组成算法的每条指令清晰、无歧义。有穷性(finiteness)：算法中每条指令的执行次数有限，执行每条指令的时间也有限。可行性(effectiveness)：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。算法与程序的区别算法是解决问题的一种方法或一个过程。一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。主要区别在：有穷性、描述方法

程序可以是无穷的,例如OS;而算法是有穷的.{例}程序是用程序设计语言描述,在机器上可以执行;而算法还可以用框图、自然语言等多种方式描述.例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。描述算法可以有多种方式自然语言、流程图、伪语言等.三、算法的描述表达算法的抽象机制伪语言接近高级语言，易学、易掌握；使得设计出来的算法可读性好，可维护性强，可靠性高；伪语言算法易于转换为高级语言程序。算法书写注意点:1、算法说明：通常在算法头部之下以注释指明：算法功能、参数含义及输入输出属性；算法引用的全局变量或外部变量、其作用、初值及应满足的限制条件等。2、适当的注释；3、输入与输出：(1)scanf()、printf();(2)函数参数;(3)全局变量。4、错误处理：(1)函数返回状态；(2)内部出错处理。5、算法结构与语句选用：（1）分支、循环结构：if(switch)、while(for)（2）尽量避免用：

do{……do{……}while}while

或：

if

(…)if(…)if(…)

等结构。StatusListInsert_Sq(SqList&L,int

i,ElemTypee){/*功能:将元素e插入顺序表L中。参数:L—顺序表;i—元素插入位置;e—被插入表的元素。返回值:若操作成功，返回OK；否则返回ERROR*/if(i<=0||L.length)returnERROR;//i值不合法

if(L.length>=L.Listsize)//当前存储空间已满{//增加空间

newbase=(ElemType*)realloc(L.elem,(L.Listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);//存储分配失败

L.elem=newbase;//新基址

L.Listsize+=LISTINCREMENT;//新的表容量

q=&(L.elem[i-1]);//插入位置for(p=&(L.elem[L.Length-1]);p>=q;--p)*(p+1)=*p;//元素后移*q=e;//插入e

L.Length++;//表长增1

returnOK;}//ListInsert_Sq举例：顺序表插入操作算法描述:四、算法与数据结构算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。算法＋数据结构＝程序1.2衡量算法性能的标准(1)正确性(correctness)—执行结果应当满足功能要求。(2)可读性(readability)—为了人的阅读和交流。要求算法易于理解，便于分析。(3)健壮性(robustness)—输入非法数据也能适当地作出反应或进行处理。也称“鲁棒性”。(4)效率与低存储量－高效率、低存储我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。时间复杂度（TimeComplexity）算法的时间复杂度：在算法运行期间所花费的时间。通常用渐进形式表示例如，T(n)=O(n2)、

Ω(n2)、Θ(n2)

空间复杂度（SpaceComplexity）

算法的空间复杂度：在算法运行期间所需要的辅助内存空间（auxiliaryspace,orworkspace）。通常用渐进形式表示例如，S(n)=O(n2)、

Ω(n2)、Θ(n2)1.3算法的时间和空间复杂度1.4算法分析

算法分析：对于算法的时间和空间复杂度进行定量分析。一、分析时间复杂度的基本步骤Step1、计算出在算法运行期间基本运算执行的总频数.Step2、表示为渐近时间复杂度（asymptotictimecomplexity）二、渐近符号

1.定义(大“O”符号,增长阶上界)

：若存在两个正的常数c和n0,对于任意≥n0,都有T(n)≤c×f(n)，则称T(n)的增长阶不超过f(n)的增长阶,记为T(n)=O(f(n)).n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)例：(1)设f(n)=3n,g(n)=n.因对所有n≥1,有3n≤4n,(c=4,n0=1),所以有f(n)=O(g(n)).(2)设f(n)=n+10,g(n)=n.因对所有n≥1,有n+10≤11n,(c=11,n0=1),所以有f(n)=O(g(n)).(3)设f(n)=2n2+11n-10,g(n)=n2.因对所有n≥10,有2n2+11n-10≤3n2,(c=3,n0=10),所以有f(n)=O(g(n)).(4)设f(n)=n2,g(n)=n3.因对所有n≥1,有n2≤n3,(c=1,n0=1),所以有f(n)=O(g(n)).注意到,满足“O”符号定义的函数f(n)并不是唯一的。所以有以下约定：一个函数增长阶的上界是该函数的所有上界中的最小者(忽略常数因子和低次项).例:百鸡问题.“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”

a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程：

a+b+c=1005a+3b+c/3=100c%3=0

第一种解法：a、b、c的可能取值范围：0~100，对在此范围内的a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。第二种解法：公鸡只数：n/5;母鸡只数：n/3;小鸡只数：n-a-b。算法：改进的百鸡问题输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]1.chicken_problem(int

n,int&k,int

g[],int

m[],ints[])2.{int

k,i,j,a,b,c;3.k=0;4.i=n/5;5.j=n/3;6.for(a=0;a<=i;a++)7.for(b=0;b<=j;b++){8.c=n–a–b;9.if((5*a+3*b+c/3==n)&&(c%3==0)){10.g[k]=a;11.m[k]=b;12.s[k]=c;13.k++;14.}15.}16.}17.}

算法chicken_problem的时间花费：取n0=28，对，有：令：c=13，并令，有：所以,

含义：的增长最多象的增长那样快。称是的上界。运行时间的上界,“O”

2.大Ω符号(增长阶下界)

定义若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)的增长阶不小于f(n)的增长阶,记为T(n)=Ω(g(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n)例：设T(n)=3n2+2n,求其增长阶的下界.因对所有n>1,有|T(n)|=|3n2+2n|≥3n2,(c=3,n0=1),所以有T(n)=Ω(n2).注意到,满足“Ω”符号定义的函数f(n)并不是唯一的。所以有以下约定：一个函数增长阶的下界是该函数的所有下界中的最大者(忽略常数因子和低次项).例：百鸡问题chicken_problem算法第10、

11、12、13行，仅在条件成立时才执行,其执行次数未知.假定条件都不成立,这些语句一次也没有执行.所以该算法的执行时间至少为：当取=1时，，存在常数，和函数，使得：所以：T(n)=Ω(n2).

含义：的增长至少象的增长那样快。表示一个解决问题的算法的时间下界。

运行时间的下界,“Ω”

3.Θ符号(增长阶相同,“渐进的紧的界”)

定义若既有T(n)=O(f(n)),又有T(n)=Ω(g(n))

,则称函数T(n)的增长阶等于f(n)的增长阶,记为T(n)=Θ(f(n))

n0问题规模n执行次数n0之前的情况无关紧要T(n)c2×f(n)c1×f(n)例：T(n)＝5n2＋8n＋1当n≥1时，5n2＋8n＋1≤5n2＋8n＋n

＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2)∴当n≥1时，14n2≥5n2＋8n＋1≥5n2

则：5n2＋8n＋1＝Θ(n2)例，百鸡问题chicken_problem算法，运行时间的上界是，下界是；这表明无论输入规模如何变化，该算法的运行时间都介于和之间。表明该算法运行时间的准确界是。含义：的增长与的增长有同样的阶。表明算法的运行时间有一个较准确的界

。

运行时间的准确界,“Θ”

定理

设f,g是两个函数,,若r为>0的常数,则f(n)=

Θ(g(n)).证：设r=c为>0的常数.由极限的定义可知,取为c/2,则必存在某个n0,当n≥n0时,总在c/2~3c/2之间.于是,对所有n≥n0时,f(n)

≤,从而

f(n)=O(g(n)).并且对所有n≥n0,有f(n)≥,从而f(n)=Ω(g(n)).

渐近符号的性质(1)和函数(对、也成立)O(f(n))+O(g(n))=

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

O(f(n)+g(n))；(2)传递性(对、也成立)f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))(3)乘积(对、也成立)O(f(n))*O(g(n))=

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

O(f(n))两个函数f、g增长阶的比较定义了这两个函数之间的一个二元关系.具有的性质:性质O(f(n))+O(g(n))=

O(max{f(n),g(n)})的证明：对于任意f1(n)=

O(f(n))，存在正常数c1和自然数n1，使得对所有n

n1，有f1(n)

c1f(n)。类似地，对于任意g1(n)=

O(g(n))，存在正常数c2和自然数n2，使得对所有n

n2，有g1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。则对所有的n

n3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).(4)自反性f(n)=

(f(n))f(n)=O(f(n))f(n)=

(f(n))(5)对称性f(n)=

(g(n))

g(n)=

(f(n))(6)反对称性f(n)=O(g(n))

g(n)=

(f(n))增长阶的极限形式判别法定理设f,g是两个函数,,则(1)c≠0,f(n)与g(n)同阶,f(n)=

(g(n))(2)c=0,f(n)比g(n)低阶,f(n)=O(g(n))(3)c=∞,f(n)与g(n)高阶,f(n)=Ω(g(n))三、算法时间复杂度的有关概念最好时间复杂度：指算法对所有可能输入集的最小执行时间

最坏时间复杂度：指算法对所有可能输入集的最大执行时间

平均时间复杂度：指算法对所有可能输入集的执行时间的平均值

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

[例]顺序查找算法以元素的比较作为基本操作。考虑成功检索的情况。

最好情况下的时间复杂度：

(1)

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

(n)

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

(n)int

search(inta[],int

n,intkey){for(i=0;i<n;i++)if(a[i]==key)returni;return-1;}四、算法分析中常见的复杂度函数FunctionNamecConstantlognlogarithmicnlinernlognn-log-nn2Quadraticn3Cubic2nExponential各种数量级的f(n)五、算法渐近分析的步骤统计基本操作次数简化、得到统计结果基本概念：渐近复杂度：O,

,

平均时间复杂度,最坏时间复杂度,最好时间复杂度基本技术：常用求和公式递归方程求解基本技术：根据循环统计基本操作次数用递归关系统计基本操作次数

统计基本操作次数的常用方法

根据循环统计基本操作的次数利用递归关系求基本操作的次数例：选择排序voidsele_sort(intA[],intn){for(i=0;i<n-1;i++){index=i;for(j=i+1;j<n;j++)if(A[j]<A[index])index=j;if(index!=i){temp=A[index];

A[index]=A[i];

A[i]=temp;}}}T(n)=n*(1+(n+1)/2+1)=(n2+

5)

/2T1(n)=nT2(n)=1T3(n)=(n+1)/2T4(n)=1[例2]利用递归关系来基本操作的次数.求Fibonacci数列的第n项。该数列的定义为：F0=F1=1,Fi=Fi-1+Fi-2，i>=2。由这一数学定义自然地导出一个递归算法。int

F(intn){if(n==0||n==1)return1;elseif(n>=2)returnF(n-1)+F(n-2);}该算法的计算时间T(n)满足递归方程：

T(n)=T(n-1)+T(n-2)+1,n>1；初始条件T(0)=T(1)=0。六、常用求和公式(1)算术级数(2)多项式级数平方和级数k方和级数(3)几何级数(4)算术-几何级数也称递推方程（recurrenceequation）是自然数n上一个函数T(n)，它使用一个或多个小于n时的值的等式或不等式来描述。递推方程也称为递推关系或递推式。

递推方程必须有一个初始条件（也称边界条件）。七、解递归方程

[例]

逆序输出正整数的各位数.voidPrintDigit(unsigned

intn){ printf(n%10); //输出最后一位数dk

if(n>=10)PrintDigit(n/10); //以逆序输出前k-1位数}时间分析设n=d1d2

dk是k位数，当k=1时，只执行printf语句和if判定语句；当n至少是2位数（k＞1）时，除了执行这两个操作外，还需执行递归函数调用PrintDigit(n/10)，

n/10

是k

1位数。T(k)=2k+2=

(k)

迭代法(展开法)将递归方程的的右端项通过迭代展开成级数,然后估计级数和的渐进阶.

生成函数(母函数)法替换法

先估计递归方程的显式解,再用数学归纳法证明.主方法

若递归方程形如:T(n)=aT(n/b)+f(n),可根据f(n)的不同情况使用主定理.常用方法：1、展开法(Recursivelyexpand)

将递归方程展开直到方程右边不再含有未知函数T，而代之以一个级数，对这个级数求和即可得到方程的解。

例：T(n)=2T(n/2)+5n2,(设n=2k);T(1)=7解：由原方程可得T(n/2)=2T(n/4)+5(n/2)2T（n/4）=2T(n/8)+5(n/4)2...T（n/2k-1）=2T(n/2k)+5(n/2k-1)2

代入原方程，得：

=…=10n2-3n[例]

使用迭代法分析程序。算法——汉诺塔算法1voidHanoi(intn,charA,charB,charC)

2{3if(n==1)

Move(A,C);//Move是一个抽象操作，表示将碟子从A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}[分析]

函数Hanoi中两次调用自身，函数调用使用的实在参数均为n

1，函数Move所需时间具有常数界

(1)，可将其视为一个程序步，于是有：扩展并计算此递推式：T(n)=2T(n

1)+1=2(2T(n

2)+1)+1=22T(n

2)+2+1=23T(n

3)+22+2+1

=2n

1T(1)+…+22+2+1=2n

1+…+22+2+1=2n

1使用递归树（recursiontree）可以形象地看到递推式的迭代过程。

[例]T(n)=2T(n/2)+n的递归树2、用生成函数(母函数)解递归函数

1)生成函数的定义定义:令是一个数列,构造如下的函数：

该函数称为数列a0,a1,a2,…

的生成函数.例：函数是序列的生成函数。2)生成函数的性质

(1)加法

设是序列的生成函数，

是序列的生成函数.则

是序列的生成函数。(2)移位

设是序列的生成函数，则

是序列的生成函数。(3)乘法

设是序列的生成函数，是序列的生成函数，则

是序列的生成函数，其中，

(4)z变换设是序列的生成函数，则 是序列的生成函数。当时，有：(式1)

则是序列1,1,1,…的生成函数。特别地，有：

所以，是序列的生成函数。若取数列为算法的时间复杂度函数{T(n)},则其生成函数为:

f(x)=T(0)+T(1)x+…+

T(n)xn…如果能由T(n)的递归方程求出T(n)的生成函数,则其展开式第n项系数即为T(n).3)用生成函数法求解递归方程例汉诺塔(Hanoi)问题。递归关系式：(式2)

用作为系数，构造一个生成函数：令：(根据式2,h(n)-2h(n-1)=1)

由式1，得：所以：令：有：解得：所以：有：，它是式中第项的系数。替换方法要求首先猜测递推式的解，然后用归纳法证明。[例]使用替换方法分析程序Hanoi问题的时间。可以先对以下这些小的示例进行计算：T(3)=7=23

1；T(4)=15=24

1；T(5)=31=25

1；T(6)=63=26

1总结规律，猜测：T(n)=2n

1，n≥1。3、替换法证明：（归纳法证明）(1)当n=1时，h(1)=1，结论成立。(2)归纳法假设：当k＜n时，有h(k)=2k

1.(3)那么，当k=n时，h(n)=2h(n

1)+1=2(2n

1

1)+1=2n

1。因此，对所有n≥1，h(n)=2n

1=

(2n)。4、主方法主方法在递归算法分析中，常需求解如下形式的递推式：T(n)=aT(n/c)+f(n)

式中，

a≥1和c＞1是常数，f(n)是一个渐近正函数，n/c指

n/c

或

n/c

。求解这类递推式的方法称为主方法。

[定理]

设a,b,c为非负常数,

其中n是c的幂，则其解是：(主定理)[例]T(n)=16T(n/4)+nT(1)=1对照公式:a=16,c=4,b=1,符合情况（3），[例]T(n)=2T(n/2)+n对照公式:a=2,c=2,b=1,符合情况（2），[例]T(n)=3T(n/4)+n对照公式:a=3,c=4,b=1,符合情况（1）,1.5最优算法(optimalalgorithm)一、问题的下界定义

一个问题的下界是解决该问题的任意算法所需要的最小时间复杂度。注:

定义中的时间复杂度指最坏时间复杂度.首先对已知的解决该问题的算法进行分析,找出同类算法中共有的基本操作的最大集合.再证明这些基本操作(或其中的一些基本操作构成的子集)在最坏情况下对于该问题的解决是必不可少的.问题下界的确定?例，在一个无序数组中查找最大元的算法.输入：数组E[],数组大小n.输出：最大元素max.int

findMax(int[]E,intn){intmax;max=E[0];//Assumemax.for(index=1;index<n;index++)if(max<E[index])max=E[index]returnmax;}

算法findMax的最好、最坏和平均时间复杂度都一样，为

(n).

查找无序数组最大元的所有算法的时间复杂度的下界是否是

(n)?分析：

不失一般性,只考虑数组中各元素互不相同的情形.因此n元数组中最大元只有一个.对其余n-1个元素,要判定它不是最大元,至少要找到一个比它大的元素,因此需要至少一次比较.所以,为了找出最大元,任何算法至少需要n-1次比较.由此可确定查找最大元问题的算法复杂度下界为

(n).定义如果一个算法的时间复杂度等于这个问题的下界，那么该算法是最优的。二、最优算法例，算法findMax即为最优算法.例如，排序问题的计算时间下界为

(nlogn)，时间复杂度为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。1.6高效算法的必要性例：设算法A在输入规模为n时的计算时间为T(n)=3×2n.在计算机C1上执行该算法的算法是t秒.现有另一台计算机C2,其运行速度是C1的64倍,则在C2上用算法A在t秒内能解输入规模为多大的问题?若算法的计算时间改进为T(n)=n2,其余条件不变,则在C2上用t秒内能解输入规模为多大的问题?解：设C2用算法A在t秒内能解n1规模的问题.则有

,得n1=n+6.设C2用改进算法在t秒内能解n2规模的问题.则有

,得n2=8n.不同时间复杂度下不同输入规模的算法运行时间,这里假定每一个操作时间是1ns.

nlognnnlognn2n32n83n8n24n64n512n256n164n16n64n256n4.096μ65.536μ325n32n160n1.024μ32.768μ4294.967ms646n64n384n4.096μ262.144μ5.85c1287n128n896n16.384μ1997.152μ1020c2568n256n2.048μ65.536μ16.777ms1058c5129n512n4.608μ262.144μ134.218ms10135c102410n1.024μ10.24μ1048.576μ1073.742ms10289c204811n2.048μ22.528μ4194.304μ8589.935ms10589c409612n4.096μ49.152μ16.777ms68.719s101214c819213n8.196μ106.548μ67.174ms549.752s102447c1638414n16.384μ229.376μ268.435ms1.222h104913c3276815n32.768μ491.52μ1073.742ms9.773h109845c6553616n65.536μ1048.576μ4294.967ms78.187h1019709cn：纳秒µ：微秒ms：毫秒s：秒h：小时d：天y：年c：世纪

算法A1A2A3A4A5A6时间复杂度nnlognn2n32nn!n2和n1的关系10n18.38n13.16n12.15n1n1+3.3n1计算机速度提高10倍后,不同算法复杂度求解规模的扩大情况

FasterComputerorFasterAlgorithm?附录:基本数据结构复习线性结构线性表栈队列串非线性结构树，二叉树图（a1,a2,…ai-1，ai,ai＋1

，…,an）(一)线性表有关的概念：数据元素表头ai的直接前驱ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长表尾n=0时称为空表在数据元素的非空有限集中：（1）存在唯一的一个被称为“第一个”的数据元素（开始结点）；（2）存在唯一的一个被称为“最后一个”的数据元素（终端结点）；（3）除第一个之外，每个数据元素均只有一个前驱；（4）除最后一个之外，每个数据元素均只有一个后继

.线性表的特点：逻辑地址数据元素存储地址数据元素1a1Loc(a1)a12a2Loc(a1)+La2…………iaiLoc(a1)+(i-1)*Lai……nanLoc(k0)+(n-1)*Lan线性表的顺序存储结构

Locate(ai+1)=Locate(ai)+sizeof(ElemType)

Locate(ai)=Locate(a1)+sizeof(ElemType)*(i-1)单链表a4a3a1a2

0101010241014101010121014101610181020102210241026

用一组任意的存储单元存储线性表的各个数据元素。数据元素之间的关系通过保存直接后继元素的存储位置来表示。a