算法分析与设计课件

计算机算法分析与设计任课教师：袁宁ise_yuann@济南大学信息学院计算机软件教研中心西南科技大学计算机学院软件教研室学习目标2掌握算法分析与设计的基本理论掌握进行算法分析与设计的基本方法（时间、空间复杂度分析，算法正确性的证明）掌握计算机领域中常用的非数值计算方法，并学会用这些算法解决实际问题课程要求3教学方式：理论(34学时)，实践(14学时)考核方式：考试(70%)+考勤和平时作业(10%)+上机实验(20%)课程学分：3先修课程：《离散数学》《数据结构》《数值分析》《C语言程序设计》授课教材4机械工业出版社选用教材：《算法设计方法》吴哲辉等参考书目：《计算机算法基础》（第二版）

余祥宣等

华中科技大学出版社《算法引论》

张益新，沈雁 国防科技大学出版社第一章 导引5---计算机算法分析与设计是面向设计的、处于核心地位的教育课程---计算机算法是计算机科学和计算机应用的核心。算法的定义和特征算法的描述算法分析递归算法1.1

算法(Algorithm)的定义和特征算法是指解决问题的一种方法或一个过程例:从济南大学去动物园的乘车方法①济南大学102电车动物园经七纬二

4,35路汽车②济南大学9路汽车动物园4,35路汽车③济南大学k92汽车大观园大观园/天桥/…长途车站动物园4,35路汽车6一个算法是求解某一类特定问题的一组有穷规则的集合。7首先，一个算法是一组规则，通常称之为算法步骤，这组规则是有穷的，即能用有限的形式表示出来。其次，一个算法是针对一类问题而设计的。1.2

算法的描述8算法主要包含两个方面的内容：算法设计：主要研究怎样针对某一特定类型的问题设计出求解步骤。算法分析：讨论所设计出来的算法步骤的正确性和复杂性。对于设计出来的一类问题的求解步骤，需要一种表达方式，即算法描述。算法的基本思想：轻者（小的元素）像气泡那样从水底往上浮。在排序过程中，每次把相邻的两个元素作比较，当前面的元素大于后面的元素时，就交换它们的位置。这样，所有相邻的元素比较一遍以后最大的元素就被交换到了最后面。依此类推，直到把最后两个元素排好序。9例1.1冒泡排序算法用冒泡排序法对6个数进行排序(从小到大)972541a[0]a[1]a[2]a[3]a[4]a[5]7541727754152415794121214579124579冒泡排序方法:

依次比较相邻的两个数,将小数放前面,大数放后面.

n个数排序需要进行n-1轮比较, 从第1轮到第n-1轮, 各轮的比较次数依次为:n-1次、n-2次

…

1次109721999594725419第3轮初始状态 第1轮 第2轮 第4轮 第5轮254179例1.1

冒泡排序算法算法1.1冒泡排序输入：待排序数组A，其中有n个元素；输出：排好序的数组A。bubblesort(float

A[],int

n){

int

i

,j;for

(i=0;i<n-1;

i++)for

(j=0;j<n-1-i;

j++)if

(A[j]>A[j+1])swap(A+j,

A+j+1);}11算法1.2元素交换输入：待交换元素的位置x和y；输出：交换后的结果仍存于x和y中。swap

(float

*x,

float

*y){float

u

=

*x;*x=

*y;*y

=

u;}12例1.2

求两个正整数m,n的最大公约数13求最大公约数的辗转相除算法基本思想：用小的数作除数，大的数作为被除数，做除法求余，如果余数等于零，那么小的数就是两个数的最大公约数。否则用小的数做被除数，余数作为除数，再做除法求余，如此辗转相除下去，直到余数等于零。那时的除数就是要求的原本两个数的最大公约数。例1.2

求两个正整数m,n的最大公约数Beginr

m%nr=0？Swap(m.n,r)EndNY14欧几里得算法描述：输入：正整数m和n输出：m和n的最大公因子第一步：求余数。r

m%n第二步：判断r=0?，若是，终止(n为答案)，否则，转第三步。第三步：互换,m

n,n

r,返回第一步。求两个正整数最大公因子的一个实例假设m=21

和n=45，求21和45的最大公因子第一步：r=m%n=21%45=21；第二步：r不等于0，转入第三步；第三步：互换，m=n=45,

n=r=21，返回第一步。第一步：r=m%n=45%21=3；第二步：r不等于0，转入第三步；第三步：互换，m=n=21,

n=r=3，返回第一步。第一步：r=m%n=21%3=0；第二步：r

等于0，算法结束，3即为21和45的最大公因子。15算法1.3

求最大公约数的辗转相除法输入：两整数m和n；输出：m和n的最大公约数。16int

gcd(int

m,

int

n){

int

a=max{m,n};int

b=min{m,n};intc;while

(b!=0){

c=a

mod

b;a=b;b=c;}return

(a);}算法1.4

求最大公约数的递归算法输入：两整数m和n；输出：m和n的最大公约数。int

gcd(int

m,

int

n){

inta=max{m,n};int

b=min{m,n};intc;if

(b

==

0)

return

(a);else

{c=a

mod

b;return(

gcd(b

,

c)

);}}17Horner根据等式设计出一个高效算法。例1.3

多项式求值的Horner算法18输入：多项式的系数和初值；输出：多项式的值。步骤：（仅主体部分）19P(x0)=a0;for

(i=1;

i<=n;

i++)P(x0)

=

P(x0)*x0

+

ai;算法1.5

多项式求值的Horner算法首先，我们给出两个更为基本的集合运算算法。一个用Member(b,A)表示，其功能是考查b是不是集合A的一个元素。另一个记为Insert(b,A)，它的功能是在集合A中增加一个元素b，这个运算以b原本不是A的元素为前提。实现Member(b,A)的实质性工作是查找。把A的元素逐个同b进行比较，若找到一个元素等于b，就输出1并停止运算；当查找完集合A的全部元素都没有找出同b相等的元素时，就输出0。20例1.4

集合的并运算和交运算输入：集合A和待查找的元素b，其中|A|=m；输出：b在集合A中则返回1，否则返回0。int

Member(float

b,

float

A[

],

int

m){ int

i;for

(i=0;

i<m;

i++)if

(A[i]

==

b) return

(1);return

(0);}21算法1.6

集合元素查找算法输入：集合A和待插入的元素b

，其中|A|=m;输出：集合S，其中|S|=m+1.22Insert(float

b,float

A[

],float

S[

],int

m){ inti;for

(i=0;

i<m;

i++)S[i]

=

A[i];S[m]

=

b;}算法1.7

向集合中插入元素算法输入：集合A和集合B；输出：集合S，其中并且满足。23Union(float

A[],

int

m,

float

B[],

int

n,

float

S[]){ int

i,

j;S=A;for

(i=0;

i<n;

i++)if

(Member(B[i],

A,

j)

==

0)Insert(B[i],

S,

S,j++);}算法1.8

集合的并运算算法输入：集合A和集合B，其中，；输出：集合S，其中并且满足。24Intersection(float

A[],

int

m,

float

B[],

int

n,

float

S[])

{int

i,

j

=

1;S=NULL

;for

(i=0;

i<n;

i++)if

(Member(B[i],

A,

m)

==

1)Insert(B[i],

S,

S,j++);}算法1.9

集合的交运算算法算法的五个重要特性25确定性每一种运算必须要有确切的定义，无二义性可行性运算都是基本运算，原理上能在有限时间内完成输入有0个或多个输入输出一个或多个输出有穷性在执行了有穷步运算后终止算法的特性26凡是算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称之为算法，只能叫做计算过程。操作系统就是计算过程的一个典型例子。设计操作系统的目的是为了控制作业的

运行，当没有作业时，这一计算过程并

不终止，而是处于等待状态，一直等到

一个新的作业的进入。1.3

算法分析27算法分析工作可归结为两部分：正确性证明：主要包括算法的可终止性（即对

任意输入，算法的执行都可以在有限步内终止）和算法的执行结果（输出）与问题（问题类）的求解要求相符两方面的证明。复杂性分析：指算法的执行所需要的时间量和

空间量的分析，其中对时间量的分析尤为重要。频率计数例子频率计数(frequency

count)：即语句执行的次数。考虑语句x

x+y在下面三个程序段中的频率计数FCbeginx

x+yendbeginfor

i

1

to

n

dox

x+yrepeatendFC:128FC:nbeginfor

i

1

to

n

dofor

j

1

to

n

dox

x+yrepeatrepeatendFC:n2计算时间的渐进估计表示29定义1.1

设f(n)和g(n)为定义在自然数集上的两个函数。如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≤c|g(n)|

则记作：f(n)=O(g(n))因此，当说一个算法具有O(g(n))的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)时间的渐进估计表示30定理1.1若A(n)=amnm+…+a1n+a0是一个m次多项式，则A(n)=O(nm)。证明：取n0=1，当n≥n0时利用A(n)的定义和一个简单的不等式，有|A(n)|

≤

|am|nm+…+|a1

|

n+|a0

|=(|am|+|am-1|/n

…+|a0

|/nm

)

nm≤

(|am|+|am-1|…+|a0

|)

nm取c=|am|+|am-1|…+|a0

|，定理得证。时间的渐进估计表示31定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶。因此，一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。例如，一个算法的数量级为

c1nm1,c2nm2,…cknmk的k个语句，则算法的数量级及计算时间就是

c1nm1+c2nm2+…+cknmk=O(nm)其中m=max{mi|1≤i≤k}算法的分类32从计算时间上可把算法分为两类多项式时间算法(polynomial

timealgorithm):可用多项式来对其计算时间限界的算法。以下六种计算时间的多项式时间算法是最为常见的O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间算法(exponential

time

algorithm):计算时间用指数函数限界的算法O(2n)<O(n!)<O(nn)对于问题输入长度n取不同值，各种不同的时间复杂性函数的算法，在机器上的运行所需时间如下所示：nlognnlognn2n32n100112212484428166416832464512256164642564096655363251601024327684294967296

33假设： 机器运算速度甲

105/s乙

108/s34设计算法时间 算法时间复杂度5天

O(n3)2小时

O(2n)甲：当输入量n=50时，共需要503=125000次基本运算，在其机器上运行1.25s就能完成。乙：当输入量n=50时，共需要250次基本运算，由于250

>1015，乙的机器一年完成的基本运算次数是：365*24*3600*108=2.7*

1014乙完成算法需要运行3年多才能完成对问题的计算。时间的渐进估计表示定义1.2

如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≥

c|g(n)|则记作：f(n)=Ω(g(n))，则g(n)是计算时间f(n)的一个下界函数。定义1.3

如果存在两个正常数c1,c2和n0，对于所有的n≥n0，有c1

|g(n)|≤

|f(n)|≤

c2

|g(n)|则记作：f(n)=Θ(g(n))这就意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。35常用的整数求和公式36冒泡排序算法的时间复杂性分析。冒泡排序算法主要包含两种基本运算：比较和交换。比较和交换运算都出现在双重嵌套循环语句的循环体中，比较运算是作为交换运算的条件而出现的。从这个双重嵌套的循环语句结构容易知道，比较运算共需进行次。算法1.1冒泡排序bubblesort(float

A[

],

intn){

int

i

,j;for

(i=0;i<n-1;i++)for

(j=0;

j<n-1-i;

j++)if

(A[j]>A[j+1])swap(A+j,

A+j+1);}37当待排序数组的元素之间满足关系时，一次交换运算都不需要执行。反之，如果待排序数组的元素满足关系那么每一次比较后都需要把相邻两个元素进行交换。38平均情况下的时间复杂性分析需要先引入逆序的概念。在一个序列，使得i<j但中，若存在，则说A[i]和A[j]构成一个逆序。显然，用算法1.1对这个序列进行排序，交换运算的次数就等于这个序列中逆序的个数。由于n个数的不同排列共有n!种，而在各种排列中，逆序个数的最小值为0，最大值为n(n-1)/2。因此各种分布的平均逆序个数为上式值等于n(n-1)/4。可见平均交换运算次数和最坏情况下的交换运算次数都是输入量n的二次函数，即391.4

递归方程求解40所谓递归算法，就是把一个输入规模较大的问题转化为一个输入规模较小的同类问题，并反复进行这种转化，直到输入规模小到可以直接求解为止。对递归算法的时间复杂性分析，涉及到递归方程的求解。因此，本节专门讨论递归方程的求解方法。下面先给出一个产生递归方程的例子。一个黄铜板上，插着三根宝石针，其中一根针上从下到上放了由大到小的64块金片，这就是Hanoi塔。Hanoi塔问题：就是如何将64块金片按照梵天不渝法则，由一根宝石针全部移动到另一根宝石针上去。41Hanoi问题Hanoi问题

问题描述：设A,B,C是3个塔座。在塔座A上有n个圆盘,这些圆盘自下而上,由大到小的叠放。要求将A上的圆盘移到C上,并仍按同样顺序叠放。移动圆盘应遵守以下规则：规则1：每次只能移动1个圆盘规则2：任何时刻都不允许将大圆盘压在小圆盘之上规则3：在满足规则1和2的前提下, 可将圆盘移至任一塔座上42C43

3个圆盘的移动过程演示A

BA→CA→BHanoi问题C44

3个圆盘的移动过程演示A

BC→BHanoi问题C

3个圆盘的移动过程演示A

B45A→CHanoi问题C46

3个圆盘的移动过程演示A

BB→AB→CHanoi问题C

3个圆盘的移动过程演示A

B47A→C3个圆盘一共需要7次移动：

A→C，A→B，C→B，A→C，B→A，B→C，A→CHanoi问题移动步骤：①(n-1)个圆盘A

B②第n个圆盘A

C③(n-1)个圆盘B

CACB

n个圆盘的移动方法：n个圆盘分为2部分上面(n-1)个圆盘最下面的第n号圆盘(n-1)个圆盘怎么移动？48递归何时结束？Hanoi问题如果只有一块金片，则只需作一次移动就可以了。如果有两块金片，则先将上面小的金片从第一根针移到第三根针上，再将下面大的金片从第一根针移到第二根针上，最后将第三根针上的小的金片从第三根针移到第二根针上。总共作3次移动动作。如果有n个金片呢？假设对n-1块金片怎样移动我们已经掌握，那么就可以把金片分成两部分：上面n-1块作为一部分，最底下的一块作为另一部分。这样，就可以把上面的n-1块金片整体移动到第三根针上，然后把最底下的一块金片移到第二根针上，最后再把第三根针上的块金片整体移到第二根针上，放在最底下那块金片的上面。49可以看到，实现这个移动，是通过块金片的整体移动两次和一块金片移动一次组成的。如果把n块金片的梵塔从一根针移动到另一根针需要做单块金片的移动的次数记为f(n)，那么就可以得到上面就是递归公式或递归方程。501.4

递归方程求解——递归公式的展开Hanoi问题：由此可以看出，当n=64时，如果移动一块金片需要1秒，要将近58万亿年才能完成。51第n个圆盘A

C

n=1(n-1)个圆盘A

B第n个圆盘A

C(n-1)个圆盘B

Cn>1{

if

(n==1) Move(n,

A,

C);elseMove(n,

A,

C);}{

Han(n-1,

A,C,B);

//将n-1个盘子从A移到B,借助于CHan(n-1,

B,A,C);

//将n-1个盘子从B