算法分析與設(shè)計(jì)課件

計(jì)算機(jī)算法分析與設(shè)計(jì)任課教師：袁寧ise_yuann@濟(jì)南大學(xué)信息學(xué)院計(jì)算機(jī)軟件教研中心西南科技大學(xué)計(jì)算機(jī)學(xué)院軟件教研室學(xué)習(xí)目標(biāo)2掌握算法分析與設(shè)計(jì)的基本理論掌握進(jìn)行算法分析與設(shè)計(jì)的基本方法（時(shí)間、空間復(fù)雜度分析，算法正確性的證明）掌握計(jì)算機(jī)領(lǐng)域中常用的非數(shù)值計(jì)算方法，并學(xué)會用這些算法解決實(shí)際問題課程要求3教學(xué)方式：理論(34學(xué)時(shí))，實(shí)踐(14學(xué)時(shí))考核方式：考試(70%)+考勤和平時(shí)作業(yè)(10%)+上機(jī)實(shí)驗(yàn)(20%)課程學(xué)分：3先修課程：《離散數(shù)學(xué)》《數(shù)據(jù)結(jié)構(gòu)》《數(shù)值分析》《C語言程序設(shè)計(jì)》授課教材4機(jī)械工業(yè)出版社選用教材：《算法設(shè)計(jì)方法》吳哲輝等參考書目：《計(jì)算機(jī)算法基礎(chǔ)》（第二版）

余祥宣等

華中科技大學(xué)出版社《算法引論》

張益新，沈雁 國防科技大學(xué)出版社第一章 導(dǎo)引5---計(jì)算機(jī)算法分析與設(shè)計(jì)是面向設(shè)計(jì)的、處于核心地位的教育課程---計(jì)算機(jī)算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心。算法的定義和特征算法的描述算法分析遞歸算法1.1

算法(Algorithm)的定義和特征算法是指解決問題的一種方法或一個(gè)過程例:從濟(jì)南大學(xué)去動物園的乘車方法①濟(jì)南大學(xué)102電車動物園經(jīng)七緯二

4,35路汽車②濟(jì)南大學(xué)9路汽車動物園4,35路汽車③濟(jì)南大學(xué)k92汽車大觀園大觀園/天橋/…長途車站動物園4,35路汽車6一個(gè)算法是求解某一類特定問題的一組有窮規(guī)則的集合。7首先，一個(gè)算法是一組規(guī)則，通常稱之為算法步驟，這組規(guī)則是有窮的，即能用有限的形式表示出來。其次，一個(gè)算法是針對一類問題而設(shè)計(jì)的。1.2

算法的描述8算法主要包含兩個(gè)方面的內(nèi)容：算法設(shè)計(jì)：主要研究怎樣針對某一特定類型的問題設(shè)計(jì)出求解步驟。算法分析：討論所設(shè)計(jì)出來的算法步驟的正確性和復(fù)雜性。對于設(shè)計(jì)出來的一類問題的求解步驟，需要一種表達(dá)方式，即算法描述。算法的基本思想：輕者（小的元素）像氣泡那樣從水底往上浮。在排序過程中，每次把相鄰的兩個(gè)元素作比較，當(dāng)前面的元素大于后面的元素時(shí)，就交換它們的位置。這樣，所有相鄰的元素比較一遍以后最大的元素就被交換到了最后面。依此類推，直到把最后兩個(gè)元素排好序。9例1.1冒泡排序算法用冒泡排序法對6個(gè)數(shù)進(jìn)行排序(從小到大)972541a[0]a[1]a[2]a[3]a[4]a[5]7541727754152415794121214579124579冒泡排序方法:

依次比較相鄰的兩個(gè)數(shù),將小數(shù)放前面,大數(shù)放后面.

n個(gè)數(shù)排序需要進(jìn)行n-1輪比較, 從第1輪到第n-1輪, 各輪的比較次數(shù)依次為:n-1次、n-2次

…

1次109721999594725419第3輪初始狀態(tài) 第1輪 第2輪 第4輪 第5輪254179例1.1

冒泡排序算法算法1.1冒泡排序輸入：待排序數(shù)組A，其中有n個(gè)元素；輸出：排好序的數(shù)組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；輸出：交換后的結(jié)果仍存于x和y中。swap

(float

*x,

float

*y){float

u

=

*x;*x=

*y;*y

=

u;}12例1.2

求兩個(gè)正整數(shù)m,n的最大公約數(shù)13求最大公約數(shù)的輾轉(zhuǎn)相除算法基本思想：用小的數(shù)作除數(shù)，大的數(shù)作為被除數(shù)，做除法求余，如果余數(shù)等于零，那么小的數(shù)就是兩個(gè)數(shù)的最大公約數(shù)。否則用小的數(shù)做被除數(shù)，余數(shù)作為除數(shù)，再做除法求余，如此輾轉(zhuǎn)相除下去，直到余數(shù)等于零。那時(shí)的除數(shù)就是要求的原本兩個(gè)數(shù)的最大公約數(shù)。例1.2

求兩個(gè)正整數(shù)m,n的最大公約數(shù)Beginr

m%nr=0？Swap(m.n,r)EndNY14歐幾里得算法描述：輸入：正整數(shù)m和n輸出：m和n的最大公因子第一步：求余數(shù)。r

m%n第二步：判斷r=0?，若是，終止(n為答案)，否則，轉(zhuǎn)第三步。第三步：互換,m

n,n

r,返回第一步。求兩個(gè)正整數(shù)最大公因子的一個(gè)實(shí)例假設(shè)m=21

和n=45，求21和45的最大公因子第一步：r=m%n=21%45=21；第二步：r不等于0，轉(zhuǎn)入第三步；第三步：互換，m=n=45,

n=r=21，返回第一步。第一步：r=m%n=45%21=3；第二步：r不等于0，轉(zhuǎn)入第三步；第三步：互換，m=n=21,

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

等于0，算法結(jié)束，3即為21和45的最大公因子。15算法1.3

求最大公約數(shù)的輾轉(zhuǎn)相除法輸入：兩整數(shù)m和n；輸出：m和n的最大公約數(shù)。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

求最大公約數(shù)的遞歸算法輸入：兩整數(shù)m和n；輸出：m和n的最大公約數(shù)。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根據(jù)等式設(shè)計(jì)出一個(gè)高效算法。例1.3

多項(xiàng)式求值的Horner算法18輸入：多項(xiàng)式的系數(shù)和初值；輸出：多項(xiàng)式的值。步驟：（僅主體部分）19P(x0)=a0;for

(i=1;

i<=n;

i++)P(x0)

=

P(x0)*x0

+

ai;算法1.5

多項(xiàng)式求值的Horner算法首先，我們給出兩個(gè)更為基本的集合運(yùn)算算法。一個(gè)用Member(b,A)表示，其功能是考查b是不是集合A的一個(gè)元素。另一個(gè)記為Insert(b,A)，它的功能是在集合A中增加一個(gè)元素b，這個(gè)運(yùn)算以b原本不是A的元素為前提。實(shí)現(xiàn)Member(b,A)的實(shí)質(zhì)性工作是查找。把A的元素逐個(gè)同b進(jìn)行比較，若找到一個(gè)元素等于b，就輸出1并停止運(yùn)算；當(dāng)查找完集合A的全部元素都沒有找出同b相等的元素時(shí)，就輸出0。20例1.4

集合的并運(yùn)算和交運(yùn)算輸入：集合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

集合的并運(yùn)算算法輸入：集合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

集合的交運(yùn)算算法算法的五個(gè)重要特性25確定性每一種運(yùn)算必須要有確切的定義，無二義性可行性運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成輸入有0個(gè)或多個(gè)輸入輸出一個(gè)或多個(gè)輸出有窮性在執(zhí)行了有窮步運(yùn)算后終止算法的特性26凡是算法，都必須滿足以上五條特性。只滿足前四條特性的一組規(guī)則不能稱之為算法，只能叫做計(jì)算過程。操作系統(tǒng)就是計(jì)算過程的一個(gè)典型例子。設(shè)計(jì)操作系統(tǒng)的目的是為了控制作業(yè)的

運(yùn)行，當(dāng)沒有作業(yè)時(shí)，這一計(jì)算過程并

不終止，而是處于等待狀態(tài)，一直等到

一個(gè)新的作業(yè)的進(jìn)入。1.3

算法分析27算法分析工作可歸結(jié)為兩部分：正確性證明：主要包括算法的可終止性（即對

任意輸入，算法的執(zhí)行都可以在有限步內(nèi)終止）和算法的執(zhí)行結(jié)果（輸出）與問題（問題類）的求解要求相符兩方面的證明。復(fù)雜性分析：指算法的執(zhí)行所需要的時(shí)間量和

空間量的分析，其中對時(shí)間量的分析尤為重要。頻率計(jì)數(shù)例子頻率計(jì)數(shù)(frequency

count)：即語句執(zhí)行的次數(shù)。考慮語句x

x+y在下面三個(gè)程序段中的頻率計(jì)數(shù)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計(jì)算時(shí)間的漸進(jìn)估計(jì)表示29定義1.1

設(shè)f(n)和g(n)為定義在自然數(shù)集上的兩個(gè)函數(shù)。如果存在兩個(gè)正常數(shù)c和n0，對于所有的n≥n0，有|f(n)|≤c|g(n)|

則記作：f(n)=O(g(n))因此，當(dāng)說一個(gè)算法具有O(g(n))的計(jì)算時(shí)間時(shí)，指的就是如果此算法用n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)，f(n)的數(shù)量級就是g(n)時(shí)間的漸進(jìn)估計(jì)表示30定理1.1若A(n)=amnm+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。證明：取n0=1，當(dāng)n≥n0時(shí)利用A(n)的定義和一個(gè)簡單的不等式，有|A(n)|

≤

|am|nm+…+|a1

|

n+|a0

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

…+|a0

|/nm

)

nm≤

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

|)

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

|，定理得證。時(shí)間的漸進(jìn)估計(jì)表示31定理表明，變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階。因此，一個(gè)計(jì)算時(shí)間為m階多項(xiàng)式的算法，其時(shí)間都可以用O(nm)來表示。例如，一個(gè)算法的數(shù)量級為

c1nm1,c2nm2,…cknmk的k個(gè)語句，則算法的數(shù)量級及計(jì)算時(shí)間就是

c1nm1+c2nm2+…+cknmk=O(nm)其中m=max{mi|1≤i≤k}算法的分類32從計(jì)算時(shí)間上可把算法分為兩類多項(xiàng)式時(shí)間算法(polynomial

timealgorithm):可用多項(xiàng)式來對其計(jì)算時(shí)間限界的算法。以下六種計(jì)算時(shí)間的多項(xiàng)式時(shí)間算法是最為常見的O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時(shí)間算法(exponential

time

algorithm):計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法O(2n)<O(n!)<O(nn)對于問題輸入長度n取不同值，各種不同的時(shí)間復(fù)雜性函數(shù)的算法，在機(jī)器上的運(yùn)行所需時(shí)間如下所示：nlognnlognn2n32n100112212484428166416832464512256164642564096655363251601024327684294967296

33假設(shè)： 機(jī)器運(yùn)算速度甲

105/s乙

108/s34設(shè)計(jì)算法時(shí)間 算法時(shí)間復(fù)雜度5天

O(n3)2小時(shí)

O(2n)甲：當(dāng)輸入量n=50時(shí)，共需要503=125000次基本運(yùn)算，在其機(jī)器上運(yùn)行1.25s就能完成。乙：當(dāng)輸入量n=50時(shí)，共需要250次基本運(yùn)算，由于250

>1015，乙的機(jī)器一年完成的基本運(yùn)算次數(shù)是：365*24*3600*108=2.7*

1014乙完成算法需要運(yùn)行3年多才能完成對問題的計(jì)算。時(shí)間的漸進(jìn)估計(jì)表示定義1.2

如果存在兩個(gè)正常數(shù)c和n0，對于所有的n≥n0，有|f(n)|≥

c|g(n)|則記作：f(n)=Ω(g(n))，則g(n)是計(jì)算時(shí)間f(n)的一個(gè)下界函數(shù)。定義1.3

如果存在兩個(gè)正常數(shù)c1,c2和n0，對于所有的n≥n0，有c1

|g(n)|≤

|f(n)|≤

c2

|g(n)|則記作：f(n)=Θ(g(n))這就意味著該算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常因子范圍內(nèi)而言是相同的。35常用的整數(shù)求和公式36冒泡排序算法的時(shí)間復(fù)雜性分析。冒泡排序算法主要包含兩種基本運(yùn)算：比較和交換。比較和交換運(yùn)算都出現(xiàn)在雙重嵌套循環(huán)語句的循環(huán)體中，比較運(yùn)算是作為交換運(yùn)算的條件而出現(xiàn)的。從這個(gè)雙重嵌套的循環(huán)語句結(jié)構(gòu)容易知道，比較運(yùn)算共需進(jìn)行次。算法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當(dāng)待排序數(shù)組的元素之間滿足關(guān)系時(shí)，一次交換運(yùn)算都不需要執(zhí)行。反之，如果待排序數(shù)組的元素滿足關(guān)系那么每一次比較后都需要把相鄰兩個(gè)元素進(jìn)行交換。38平均情況下的時(shí)間復(fù)雜性分析需要先引入逆序的概念。在一個(gè)序列，使得i<j但中，若存在，則說A[i]和A[j]構(gòu)成一個(gè)逆序。顯然，用算法1.1對這個(gè)序列進(jìn)行排序，交換運(yùn)算的次數(shù)就等于這個(gè)序列中逆序的個(gè)數(shù)。由于n個(gè)數(shù)的不同排列共有n!種，而在各種排列中，逆序個(gè)數(shù)的最小值為0，最大值為n(n-1)/2。因此各種分布的平均逆序個(gè)數(shù)為上式值等于n(n-1)/4?？梢娖骄粨Q運(yùn)算次數(shù)和最壞情況下的交換運(yùn)算次數(shù)都是輸入量n的二次函數(shù)，即391.4

遞歸方程求解40所謂遞歸算法，就是把一個(gè)輸入規(guī)模較大的問題轉(zhuǎn)化為一個(gè)輸入規(guī)模較小的同類問題，并反復(fù)進(jìn)行這種轉(zhuǎn)化，直到輸入規(guī)模小到可以直接求解為止。對遞歸算法的時(shí)間復(fù)雜性分析，涉及到遞歸方程的求解。因此，本節(jié)專門討論遞歸方程的求解方法。下面先給出一個(gè)產(chǎn)生遞歸方程的例子。一個(gè)黃銅板上，插著三根寶石針，其中一根針上從下到上放了由大到小的64塊金片，這就是Hanoi塔。Hanoi塔問題：就是如何將64塊金片按照梵天不渝法則，由一根寶石針全部移動到另一根寶石針上去。41Hanoi問題Hanoi問題

問題描述：設(shè)A,B,C是3個(gè)塔座。在塔座A上有n個(gè)圓盤,這些圓盤自下而上,由大到小的疊放。要求將A上的圓盤移到C上,并仍按同樣順序疊放。移動圓盤應(yīng)遵守以下規(guī)則：規(guī)則1：每次只能移動1個(gè)圓盤規(guī)則2：任何時(shí)刻都不允許將大圓盤壓在小圓盤之上規(guī)則3：在滿足規(guī)則1和2的前提下, 可將圓盤移至任一塔座上42C43

3個(gè)圓盤的移動過程演示A

BA→CA→BHanoi問題C44

3個(gè)圓盤的移動過程演示A

BC→BHanoi問題C

3個(gè)圓盤的移動過程演示A

B45A→CHanoi問題C46

3個(gè)圓盤的移動過程演示A

BB→AB→CHanoi問題C

3個(gè)圓盤的移動過程演示A

B47A→C3個(gè)圓盤一共需要7次移動：

A→C，A→B，C→B，A→C，B→A，B→C，A→CHanoi問題移動步驟：①(n-1)個(gè)圓盤A

B②第n個(gè)圓盤A

C③(n-1)個(gè)圓盤B

CACB

n個(gè)圓盤的移動方法：n個(gè)圓盤分為2部分上面(n-1)個(gè)圓盤最下面的第n號圓盤(n-1)個(gè)圓盤怎么移動？48遞歸何時(shí)結(jié)束？Hanoi問題如果只有一塊金片，則只需作一次移動就可以了。如果有兩塊金片，則先將上面小的金片從第一根針移到第三根針上，再將下面大的金片從第一根針移到第二根針上，最后將第三根針上的小的金片從第三根針移到第二根針上?？偣沧?次移動動作。如果有n個(gè)金片呢？假設(shè)對n-1塊金片怎樣移動我們已經(jīng)掌握，那么就可以把金片分成兩部分：上面n-1塊作為一部分，最底下的一塊作為另一部分。這樣，就可以把上面的n-1塊金片整體移動到第三根針上，然后把最底下的一塊金片移到第二根針上，最后再把第三根針上的塊金片整體移到第二根針上，放在最底下那塊金片的上面。49可以看到，實(shí)現(xiàn)這個(gè)移動，是通過塊金片的整體移動兩次和一塊金片移動一次組成的。如果把n塊金片的梵塔從一根針移動到另一根針需要做單塊金片的移動的次數(shù)記為f(n)，那么就可以得到上面就是遞歸公式或遞歸方程。501.4

遞歸方程求解——遞歸公式的展開Hanoi問題：由此可以看出，當(dāng)n=64時(shí)，如果移動一塊金片需要1秒，要將近58萬億年才能完成。51第n個(gè)圓盤A

C

n=1(n-1)個(gè)圓盤A

B第n個(gè)圓盤A

C(n-1)個(gè)圓盤B

Cn>1{

if

(n==1) Move(n,

A,

C);elseMove(n,

A,

C);}{

Han(n-1,

A,C,B);

//將n-1個(gè)盤子從A移到B,借助于CHan(n-1,

B,A,C);

//將n-1個(gè)盤子從B