計算機算法基礎(chǔ) 第2版 課件全套 沈孝鈞 第1-15章 概述 -平攤分析和斐波那契堆

1第1章

概述什么是計算機算法?

2算法的偽碼表示

3算法復(fù)雜度的分析

6函數(shù)增長漸近性態(tài)的比較

11算法復(fù)雜度與問題復(fù)雜度的關(guān)系

19計算機算法研究的課題是：如何分析一個給定算法的時間復(fù)雜度。如何為一個計算問題設(shè)計有最小復(fù)雜度的算法。什么是(計算機)算法(algorithm)?

簡單地說，算法是為解決某計算問題而設(shè)計的一個過程，其每一步必須能在計算機上實現(xiàn)并在有限時間內(nèi)完成。為了理論分析的嚴格性和方便，要求算法所解決的問題有無窮多個可能的輸入規(guī)模，而且不斷增大的輸入規(guī)模要趨向無窮大。

21.什么是計算機算法？算法需要用某種語言去描述，但希望不依賴于某一語言。這個語言稱為偽語言，偽語言所表述的算法稱為偽碼

(Pseudocode)。偽碼不受繁瑣和嚴格的語法約束，簡化了對算法的表述。偽碼著重表達解題的思路和方法。不同的人可用不同的偽碼，只要讓讀者清楚地看懂即可。要求偽碼中每一步可在計算機上實現(xiàn)。32.算法的偽碼表示

一個例子:選擇排序輸入: A[1],A[2],…,A[n]輸出: 重排數(shù)組中數(shù)字，使得A[1]

A[2]

…

A[n]Selection-Sort(A[1..n])for(i

1,i

n-1,i++)

key

i

for(j

i,j

n,j++)

ifA[j]<A[key]

then

key

j

endif endfor

A[i]

A[key]endforEnd這個偽碼可以更簡潔地用下面?zhèn)未a表述。4選擇排序的另一種描述Selection-Sort(A[1..n])for

(i

1,i

n-1,i++) findjsuchthatA[j]=min{A[i],A[i+1],…,A[n]}

A[i]

A[j]endforEnd這個偽碼顯然更清楚地反映出這個排序算法的思路和方法。53.

算法復(fù)雜度的分析目的：找出運算所需時間和輸入規(guī)模之間的函數(shù)關(guān)系。

輸入規(guī)模的度量模型

通常用輸入數(shù)據(jù)中數(shù)字的個數(shù)，或輸入的集合中元素的個數(shù)，n，作為輸入規(guī)模大小的度量。有些情況下，用二進制表示輸入數(shù)據(jù)時的比特數(shù)。

運算時間的度量

用算法中一個主要的基本運算被執(zhí)行的次數(shù)作為時間復(fù)雜度。主要的基本運算是指它被執(zhí)行的次數(shù)是最多的。6為什么這樣做？大大簡化分析的工作。與實際復(fù)雜度之間最多差一個常數(shù)因子。這是因為: (1)任一算法只用常數(shù)個基本運算，例如加、減、乘、除等。 (2)不同基本運算所需時間最多相差一個常數(shù)倍因子。 (3)通常，一個基本運算所需時間不因數(shù)據(jù)大小而不同。復(fù)雜度好壞取決于輸入規(guī)模n

時，其增長的快慢。差常數(shù)倍因子的兩個復(fù)雜度函數(shù)認為是等階的。高階與低階的兩個復(fù)雜度在

n

時，它們之比一定無界。為了理論上正確和方便，要求算法必須允許

n

！7舉例：選擇排序的復(fù)雜度分析：

我們用輸入數(shù)據(jù)之間的比較作為主要的基本運算。分析如下：選出最小的數(shù)并放入A[1]需要(n-1)次比較;選出第二小的數(shù)并放入A[2]需要(n-2)次比較;…選出第i小的數(shù)并放入A[i]需要(n-i)次比較;…選出第n-1小的數(shù)，即第二大數(shù)，并放入A[n-1]需要1次比較;選出第n小的數(shù)，即最大數(shù)，并放入A[n]不需要比較。

所以，總共需要的比較次數(shù)，即復(fù)雜度是

T(n)=(n-1)+(n-2)+…+1=n(n-1)/2。89最好情況、最壞情況和平均情況的復(fù)雜度分析不同的輸入數(shù)據(jù)，既使有相同規(guī)模n，每次算法執(zhí)行的時間可能會大不相同。要分析三種情況的復(fù)雜度：最好情況復(fù)雜度：

在遇到最有利的一組輸入數(shù)據(jù)時，算法所需要的時間。(2) 最壞情況復(fù)雜度：

在遇到最不利的一組輸入數(shù)據(jù)時，算法所需要的時間。平均情況復(fù)雜度：

各種輸入情況下，算法所需要的時間的平均值。

往往假設(shè)各種輸入情況為均勻分布。舉例:線性搜索10Linear-search(x,A[1..n])輸入: 數(shù)組A[1..n]和要找的數(shù)x輸出: 如果A[i]=x,1≤i≤n，輸出i，否則輸出0。i

1while(i≤n

and

x≠A[i]) i

i+1endwhileifi≤n

thenreturn(i)

elsereturn(0)endifEnd最好:A[1]=x，算法只需一次比較最壞:

x不在數(shù)組中或者A[n]=x，算法需要n次比較。平均:(1+2+…+n)/n=(n+1)/2。4.函數(shù)增長漸近性態(tài)的比較11定義1.1

設(shè)f(n)和g(n)是兩個定義域為自然數(shù)的正函數(shù)。如果存在一個常數(shù)c>0和某個自然數(shù)n0使得對任一n

n0,都有關(guān)系f(n)≤cg(n)，我們則說f(n)的階不高于g(n)的階，并記作f(n)=O(g(n))。

例1.4 證明n3+2n+5=O(n3)證明：因為當(dāng)n≥1時,我們有n3

+2n+5

n3+2n3+5n3=8n3,所以n3

+2n+5=O(n3)。(取c=8,n0=1。) 12定義1.2

設(shè)f(n)和g(n)為兩個定義域為自然數(shù)的正函數(shù)。如果存在一個常數(shù)c>0和某個自然數(shù)n0使得對任一n

n0,都有關(guān)系f(n)

cg(n)，我們則說f(n)的階不低于g(n)的階，并記作f(n)=

(g(n))。

例1.5 證明

n2=

(nlgn)證明：因為當(dāng)n

1時,我們有n>lgn，從而有n2>nlgn。所以n2=

(nlgn)。(取c=1,n0=1。)13定義1.3

設(shè)f(n)和g(n)為兩個定義域為自然數(shù)的正函數(shù)。如果關(guān)系f(n)=O(g(n))和f(n)=

(g(n))同時成立，我們則說f(n)與g(n)同階，并記作f(n)=

(g(n))。例1.6

證明

n3+2n+5=

(n3) 證明：例1.4已證明了n3+2n+5=O(n3)，我們只須證明

n3

+2n+5=

(n3)。注意到當(dāng)n

1時，n3

+2n+5>n3，所以n3+2n+5=

(n3)，這樣也就證明了n3+2n+5=

(n3)。表示算法復(fù)雜度的常用函數(shù)從增長慢到快：O(1),lglgn,lgn,(lgn)2,…，（對數(shù)多項式）nlglgn,n(lgn),n2(lgn)2,…n2,n3,… （多項式）2n,n!,nn… （超多項式）

1415定理1.1

假設(shè)p(n)=aknk

+ak-1nk-1+ak-2nk-2

+…+a1n1

+a0是一個多項式，其中ak

>0，那么p(n)=

(nk)。證明

我們先證明p(n)=O(nk)。我們有以下演算：p(n)=aknk

+ak-1nk-1

+ak-2nk-2

+…+a1n1

+a0

aknk

+|ak-1|nk-1

+|ak-2|nk-2

+…+|a1|n1

+|a0|

aknk

+|ak-1|nk

+|ak-2|nk

+…+|a1|nk

+|a0|nk

(ak

+|ak-1|

+|ak-2|

+…+|a1|

+|a0|)nk

Cnk這里，常數(shù)C=(ak

+|ak-1|

+|ak-2|

+…+|a1|

+|a0|)

>0，所以

p(n)=O(nk)。下面證明p(n)=

(nk)。16

17

該例說明任何多項式函數(shù)比指數(shù)函數(shù)的階要小。18

該例說明任何對數(shù)函數(shù)比多項式函數(shù)的階要小。195.算法復(fù)雜度與問題復(fù)雜度的關(guān)系問題的復(fù)雜度任何解決該問題的算法所需要的最少的運算次數(shù)。例子用比較大小的辦法將n個數(shù)排序的任何算法需要至少

lgn!

次比較才行。這個結(jié)果將在第4章討論。

lgn!

就是(基于比較的)排序問題的復(fù)雜度。問題的復(fù)雜度是算法復(fù)雜度的下界例如，

lgn!

是基于比較的排序算法復(fù)雜度的下界。通常指的是在大omega意義下的下界，即任一比較排序算法的復(fù)雜度必定為

(lgn!)或

(nlgn)。20算法復(fù)雜度是問題復(fù)雜度的上界如果某一算法的復(fù)雜度是O(f(n)),那么它所解決的問題的復(fù)雜度不會超過O(f(n))。因此任一算法的復(fù)雜度也是其所解決的問題的復(fù)雜度的上界。算法工作者的任務(wù)就是努力尋找復(fù)雜度小的算法。同時，找出問題的復(fù)雜度，即找出其算法復(fù)雜度的下界，也是一重要的工作，因為它可以告訴我們是否還有改進當(dāng)前算法的余地而省去許多徒勞無功的努力。最佳算法如果某算法A的復(fù)雜度f(n)等于或不超過其問題的復(fù)雜度g(n)，f(n)=O(g(n))，那么稱為最優(yōu)算法。絕對相等很難，一般指漸近相等，漸近二字往往省略。21易處理問題和難處理問題如果某一問題的復(fù)雜度是超多項式的,則稱為難處理問題(intractable)。反之，則稱為易處理問題(tractable)。如果是難處理問題，那么我們只能依賴近似算法或啟發(fā)式算法來解決。NP完全問題判斷一個問題是易處理還是難處理是重要的?？墒牵邢喈?dāng)多的一類問題看似簡單，但這一判斷卻十分困難。NP完全問題指的是，目前人們還無法判斷難易的問題。22P≠NP的猜想現(xiàn)在人們知道的是，如果任何一個NP完全問題被證明有超多項式下界，那么所有這一類中的問題都有超多項式下界。反之，如果任何一個NP完全問題可以在多項式時間內(nèi)解決，則所有NP完全問題都可以有多項式算法去解。但是，到目前為止，沒有人能對任何一個NP完全問題給出多項式算法或證明它只能有超多項式算法，這就是著名的P=NP或P≠NP的猜想問題。1第2

章

分治法分治法原理

2遞推關(guān)系求解

6替換法 7序列求和法和遞歸樹法

10主方法求解 123 例題示范

141.分治法原理當(dāng)輸入規(guī)模很小時，問題都容易解。當(dāng)規(guī)模很大時，一個基本方法就是把大規(guī)模問題轉(zhuǎn)換為一組小規(guī)模問題去解。分治法是這種方法之一。分治算法要講明三件事：底：對足夠小的輸入規(guī)模，如何直接解出。

分：如何將規(guī)模為n的輸入分為一組規(guī)模小些的子問題。每個子問題又要遞歸地分解為更小的子問題，直到底為止。被分解的原問題或子問題，稱為那些由它分解得到的子問題的父問題。這里，父子關(guān)系就是分解和被分解的關(guān)系。

合：

如何從子問題的解中獲得它們的父問題的解。合是一個逐層向上的合并過程，直到最初的原問題得解為止。23一個例子：二元搜索Binary-Search(A,p,r,x)輸入：任一段子序列，A[p]≤A[p+1]≤…≤A[r]，和要找的數(shù)字x。輸出:i

如果序列中有A[i]=x，否則nil。

1 ifp>r

//表明數(shù)組為空集2

thenreturn(nil)3 endif4 mid

(p+r)/2

5 if

A[mid]=x6 thenreturn(mid)7

else if

x<A[mid]8

thenBinarySearch(A,p,mid-1,x)9

elseBinarySearch(A,mid+1,r,x)10

endif11 endif12 End4幾點解釋：算法先找出序列的中位數(shù)A[mid]，mid=

(p+r)/2

。如果A[mid]=x，問題解決。否則，原序列一分為二，前一半為A[p..mid-1]，后一半為A[mid+1..r]。如果x<A[mid]，則只需搜索前一半，否則搜索后一半。每遞歸一步，搜索范圍減半，偽碼要適用于不同規(guī)模的子問題。所以，輸入是A[p..r]，而不是A[1..n]。解原問題時，要設(shè)計一個主程序來調(diào)用這個分治算法。例如，算法Binary-Search設(shè)計好之后，主程序需要調(diào)用Binary-Search(A,1,n,x)。分治法只需說清楚如何把A[p..r]分解為A[p..mid-1]和A[mid+1..r]就可以了。把A[p..mid-1]分為更小的子問題由編譯軟件自動完成。軟件會動態(tài)地把r置為mid-1。這時，A[p..r]代表的是A[p..mid-1]。因此，算法只要說清楚如何分解A[p..r]就可以了，千萬不要畫蛇添足。5表示復(fù)雜度的遞推關(guān)系因為分治法含有遞歸調(diào)用，所以難以直接計算基本運算的次數(shù)。為得到復(fù)雜度，先建立一個表示復(fù)雜度的遞推關(guān)系，然后求解得到。以二元搜索為例，A[1..n]中的數(shù)和x之間的比較是主要的基本運算。假設(shè)在最壞情況下，二元搜索需要T(n)次比較，那么我們可以有以下的遞推關(guān)系：T(0)=0 （n=0時，不需比較）T(n)=T(

n/2

)+1 （與x比較一次，再加上子問題需要的比較次數(shù)）一般情況，把規(guī)模為

n的輸入分為規(guī)模為

n/b(b為正整數(shù))的一組子問題，然后解出其中

a個子問題并從而獲得原問題的解，通常有遞推關(guān)系：T(1)=c

（c0，常數(shù)，底的復(fù)雜度）T(n)=aT(n/b)+f(n) （

f(n)是分解及合并所需的時間）分治法的復(fù)雜度往往需要解以下的遞推關(guān)系： T(1)=c T(n)=aT(n/b)+f(n) 主要方法：替換法:先猜想一個復(fù)雜度，然后用歸納法證明其正確。序列求和法從原遞推關(guān)系逐步展開后得一序列，然后對該序列求和后得解。62.遞推關(guān)系求解7解：先證T(n)=O(nlgn)，即存在c>0，使得n

2

時，T(n)≤cnlgn。歸納基礎(chǔ):當(dāng)

n

=2,3,4時，T(n)=

(1)，故有c>0

使T(n)≤cnlgn。可假定c>1。歸納步驟:假設(shè)當(dāng)n=2,3,4,…,(k-1)時，T(n)≤cnlgn成立。當(dāng)n=k(k≥5)時因為

n/2

=

k/2

≤k

-1，由歸納假設(shè)得到

T(

n/2

)≤c(

n/2

)lg(

n/2

)≤c(n/2)lg(n/2)=(cn/2)(lgn-1)。從而，從遞推關(guān)系和c>1得到：T(n)=2T(

n/2

)+n

≤2(cn/2)(lgn-1)+n

=cnlgn

-cn

+n<cnlgn。

歸納成功，故有T(n)=O(nlgn)。

(接下頁)替換法

例2.2 用替換法決定以下遞推關(guān)系表示的算法復(fù)雜度

T(n)=

(1)，

當(dāng)1≤n≤4時，

T(n)=2T(

n/2

)+n

n>48例2.2(繼續(xù)1)再證:存在d>0使得n

2時，T(n)≥d(nlgn+n)=

(nlgn)。歸納基礎(chǔ):當(dāng)

n

=2,3,4時，因為12

(nlgn

+n)，而T(n)=

(1)，那么，存在足夠小的

d

>0使

T(n)>12d

d(nlgn

+n)。可假定

d

<1/4。歸納步驟:

假定當(dāng)n=2,3,4,…,(k-1)時，T(n)≥d(nlgn+n）成立。那么，當(dāng)n

=k時(k

5)時，因為

n/2

=

k/2

≤k-1，由歸納假設(shè)得到：T(

n/2

)≥d[(

n/2

)lg(

n/2

)+

n/2

]d(n/2-1)lg(n/4)+d(n/2–1)

=(dn/2-d)(lgn-2)+dn/2-d

=(dn/2)lgn+2d–dlgn–dn+dn/2–d

>(dn/2)lgn–dlgn–dn/2 >(dn/2)lgn–dn–dn/2 (因為lgn<n)=(dn/2)lgn–3dn/2

(接下頁)9例2.2(繼續(xù)2)

進而從遞推關(guān)系得到：T(n)=2T(

n/2

)+n>2[(dn/2)lgn–3dn/2]+n=dnlgn–3dn+n=dnlgn+dn–4dn+n>d(nlgn+n) (因為d<1/4，–4dn+n>0)歸納成功。這就證明了T(n)=

(nlgn+n)=

(nlgn)，從而有T(n)=

(nlgn)。用替換法解遞推關(guān)系需要猜測出正確的復(fù)雜度并且往往需要分別證明上界和下界。當(dāng)然，很多時候，我們只需對上界作出估計，則可簡化一些工作。另外，該方法需要一定的數(shù)學(xué)技巧。本書不常用這個方法。10序列求和法和遞歸樹法兩者的本質(zhì)相同，遞歸樹法用一棵樹把序列產(chǎn)生的過程顯示出來。例2.4

用序列求和法決定由以下遞推關(guān)系表示的算法復(fù)雜度

T(1)=O(1)

T(n)=2T(n/2)+nlgn解：置n=2k，得T(2k)=2T(2k-1)+k2k。定義W(k)=T(2k)后，得到：W(k)=2W(k-1)+k2k=2[2W(k-2)+(k-1)2k-1]+k2k

=22W(k-2)+(k-1)2k

+k2k=22

[2W(k-3)+(k-2)2k-2]+(k-1)2k

+k2k=23W(k-3)+(k-2)2k

+(k-1)2k

+k2k=……=2k-1W(1)+2×2k

+3×2k

+…+(k-1)2k

+k2k=2k-1W(1)+2k

[k(k+1)/2-1]=

(k22k)

=

(nlg2n)。11遞歸樹k2kW(k-1)W(k-1)一步遞歸的樹k2k(k-1)2k-1(k-1)2k-1W(k-2)W(k-2)W(k-2)W(k-2)(b) 兩步遞歸樹

(k-2)步遞歸(k-1)2k-1k2k(k-1)2k-1k2k(k-1)2k(k-2)2k-2(k-2)2k-2(k-2)2k-2(k-2)2k-2(k-2)2kW(1)W(1)W(1)W(1)2k-1W(1)(c) 遞歸停止后的完整的遞歸樹12主方法求解

主方法不是一個新的方法。它是用序列求和法時得到的一些結(jié)果的總結(jié)。主要有三條規(guī)則。檢查遞推關(guān)系滿足那條規(guī)則，如滿足，立馬就有答案。設(shè)遞推關(guān)系為T(n)=aT(n/b)+f(n)，a

1,b>1。

用規(guī)則前先計算k值，k=logba。規(guī)則一:如果存在正數(shù)

>0，使得f(n)=O(nk-

)，那么T(n)=

(nk)。例2.5

T(n)=9T(n/3)+nlgn解：

a=9，b=3，k=logba

=lg39=2。

用

=0.2，那么nk-

=n2-0.2

=n1.8。

因為f(n)=nlgn=O(n1.8)，所以T(n)=

(n2)。13

143.

例題示范例2.9給定序列A[1],A[2],…,A[n],請用分治法設(shè)計一個復(fù)雜度為O(nlgn)的算法來找出其中兩個序號i<j,使得A[i]

A[j],并使它們的和，A[i]+A[j]，最大。如果沒有這樣兩個數(shù)，則輸出-∞。解：考慮序列A[p..r]。

分為

A[p..mid]和A[mid+1..r]。設(shè) M1=A[i1]+A[j1]是子問題1的解，

M2=A[i2]+A[j2]是子問題2的解。如果

M1

>M2，那么第1個解好些，但不一定是全局最優(yōu)，因為

A[i1]和A[j1]只能取自

A[p..mid]。從

A[p..mid]中取A[i3]，從

A[mid+1..r]中取A[j3]，

M3=A[i3]+A[j3]也許更好。(接下頁)15例

2.9(繼續(xù)1)這樣的解不可能從子問題中得到。所以，在歸遞地解決兩個子問題后，我們還要做額外的工作來彌補缺失的部分。具體做法是：在A[mid+1..r]中找出最大的數(shù)A[j3]。在A[p..mid]中選出所有小于等于A[j3]的數(shù)，組成集合S。(3) S中找出最大的一個數(shù)A[i3]。(4) M3=A[i3]+A[j3]。全局的最優(yōu)解一定產(chǎn)生于M1，M2，M3

之中。這個額外的工作算在分治法的合并部分，不同的問題需要做不同的額外的工作。

16算法偽碼Max-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r thenM

-∞ //不存在解，是底的情況 elsemid

(p+r)/2

Max-Sum-Two-Numbers(A[p..mid],i1,j1,M1)

Max-Sum-Two-Numbers(A[mid+1..r],i2,j2,M2) findj3suchthatA[j3]=max{A[k]|mid+1≤k≤r}

S

{A[k]|p≤k≤mid,A[k]≤A[j3]}

if|S|=

then

M3

-∞10

else findi3suchthatA[i3]=max{A[k]|A[k]

S}11 M3

A[i3]+A[j3]12

endif

(接下頁)17算法偽碼(繼續(xù))

13 ifM3>M2and

M3>M114 then M

M3，i

i3，j

j315

else

ifM2>M116

thenM

M2，i

i2，j

j217

else M

M118

ifM≠-∞19

theni

i1，j

j220

endif21 endif22 endif

23 endif24 End

18算法復(fù)雜度分析例2.9的算法的主程序很簡單，只需調(diào)用Max-Sum-Two-Numbers(A[1..n],i,j,M)即可得到原問題的解。上面算法中第6行到第12行是找尋第3個解的部分，需要O(n)時間。所以算法復(fù)雜度可由遞推關(guān)系T(n)=2T(n/2)+O(n)決定。由主方法規(guī)則2得到T(n)=O(nlgn)。稍作修改，這個算法的復(fù)雜度可降為O(n)，我們把它留給讀者思考。第3

章

基于比較的排序算法1什么是基于比較的排序

2插入排序 3合并排序

7堆排序

15快排序

282什么是基于比較的排序排序是把輸入的n個數(shù)，A[1],A[2],…,A[n]，重排為一個遞增序列或遞減序列。因為對稱性，只考慮排序為遞增序列，A[1]

A[2]

…

A[n]。基于比較是指，用比較輸入數(shù)字之間大小的方法來決定它們的大小順序。不允許用數(shù)字的其它結(jié)構(gòu)性特征來幫助排序，例如數(shù)字A[i](1

i

n)有幾位，每一位的數(shù)值是多少，等等。32. 插入排序

這是一個簡單的用貪心法的算法。思路是：初始： 把一個數(shù)，A[1]，排好序，(不需操作)第1步： 把兩個數(shù)，

A[1]，

A[2]，排好序，第2步： 把三個數(shù)，A[1]，A[2]，A[3]，排好序，……例如: (方框是下一步要插入的數(shù))初始： 5 3 4 2 1第1步后:

3 5 4 1 2第2步后:

3 4 5 1 2第3步后: 1 3 4 5 2第4步后:

1 2 3 4 54插入排序偽碼Insertion-sort(A[1..n])ifn=1 thenexitendiffor

k←2to

n

x←A[k] j←k–1 while

j>0and

A[j]>x A[j+1]←A[j] //A[j]比x

大，向后挪一位 j←j-1 endwhile //如果j=0，則有x<A[1] A[j+1]←x //把x插入到A[j+1]。如j=0，也正確

endfor End5

6插入排序的優(yōu)缺點缺點：復(fù)雜度較高，后面會介紹

(nlgn)的算法。優(yōu)點：算法簡單，實現(xiàn)容易。是穩(wěn)定(stable)排序，即序列中任意兩個相等的數(shù)在排序后不改變它們的相對位置。是就地操作的算法，即只需要使用常數(shù)個除輸入數(shù)據(jù)所占空間以外的存儲單元。除數(shù)組A[1..n]以外，插入排序只需要指針k、指針j和臨時工作單元x。7用分治法把序列一分為二遞歸地將兩子序列排序用合并算法把排好序的兩個子序列合并為一個單一序列先討論合并算法，再討論排序算法。假設(shè)A[1..n1]和B[1..n2]分別為兩個遞增序列,即 A[1]

A[2]

A[3]

…

A[n1] B[1]

B[2]

B[3]

…

B[n2]合并算法把它們合并為一個排好序的單一序列。

合并后的序列存入數(shù)組C[1..n1+n2]，并有： C[1]

C[2]

C[3]

…

C[n1+n2](偽碼見下頁)3. 合并排序8Merge(A[1..n1],B[1..n2],C[1..n1+n2])i

←

j

←k←1while

i

n1

and

j

n25

ifA[i]

B[j]6

then

C[k]←A[i]，i

←i+18 else

C[k]←B[j]，j

←j+110

endif11

k

←k+112 endwhileifi>n1 //說明序列A里的數(shù)已全部放入序列C中

then

C[k..n1+n2]←B[j..n2] //B中剰余數(shù)放入C中15

elseC[k..n1+n2]←A[i..n1]

//否則，A中剰余數(shù)放入C中16 endifEnd合并算法復(fù)雜度(最壞情況)：

T(n)=n–1=n1+

n2

–1次比較。9合并排序：Mergesort(A[p..r]) //如果p=r，則是底的情況，不需任何操作1 if

p<r2

then

mid

←

(p+r)/2

3

Mergesort(A[p..mid])4

Mergesort(A[mid

+1..r])5

Merge(A[p..mid],A[mid+1..r],C[p..r])6

A[p..r]←C[p..r])7 endifEnd//調(diào)用

Mergesort(A[1..n])后可排序A[1..n]顯然，前面的合并算法Merge(A[1..n1],B[1..n2],C[1..n1+n2])需要稍加修改。主要是各數(shù)組兩端的序號必須是變量，不能總是從1開始。但這種修改極為容易，不在此贅述了。當(dāng)我們需要將數(shù)組A[1..n]排序時，只需調(diào)用Mergesort(A[1..n])即可。10二叉樹表示合并排序合并排序的遞歸過程可以用一棵二叉樹來表示。其劃分的順序是從根開始，自上而下，與樹的前向遍歷一致，而合并的順序是從葉子(底)開始，自下而上，與樹的后序遍歷順序一致。例子：A[1..8]A[1..4]A[5..8]A[1..2]A[3..4]A[5..6]A[7..8]9624153811合并排序復(fù)雜度最壞情況下，復(fù)雜度T(n)有遞推關(guān)系： T(1)=0 T(n)=T(

n/2

)+T(

n/2

)+(n-1)

（3.1）定理3.1設(shè)T(n)為，最壞情況下，合并排序數(shù)組A[1..n](n>0)需要的數(shù)字之間的比較次數(shù)，那么，T(n)滿足不等式

T(n)

n

lgn

–(n-1)。證明：我們用歸納法證明。歸納基礎(chǔ)：由(3.1)式，直接驗證n=1,2,3,4。T(1)=0

1

lg1

–(1-1)，T(2)=T(1)+T(1)+(2-1)=1

2

lg2

–(2-1)，T(3)=T(2)+T(1)+(3-1)=3

3

lg3

–(3-1)，T(4)=T(2)+T(2)+(4-1)=5

4

lg4

–(4-1)。

定理正確。歸納步驟:(接下頁)12定理3.1(證明繼續(xù)1)歸納步驟：假設(shè)當(dāng)

n

=1,2,3,…,k-1(k

5)時，有T(n)

n

lgn

–(n-1)。下面證明，當(dāng)n=k

時，仍然有T(n)

n

lgn

–(n-1)。我們注意到；

當(dāng)k是偶數(shù)時，

lg

k/2

=

lg(k/2)

=

lgk-1

=

lgk

-1。當(dāng)k是奇數(shù)時，

lg

k/2

=

lg((k+1)/2)

=

lg(k+1)-1

=

lg(k+1)

-1=

lgk

-1。 (因為k是奇數(shù))所以，由歸納假設(shè)，我們有：T(

k/2

)

k/2

lg

k/2

–(

k/2

-1)

k/2

(

lgk

-1)–

k/2

+1 (3.2)T(

k/2

)

k/2

lg

k/2

–(

k/2

-1)

k/2

(

lgk

-1)–

k/2

+1 (3.3)(接下頁)13定理3.1(證明繼續(xù)2)把(3.2)式和(3.3)式代入到(3.1)式，我們得到：T(n)=T(k)=T(

k/2

)+T(

k/2

)+(k-1)

(

k/2

(

lgk

-1)–

k/2

+1)+(

k/2

(

lgk

-1)–

k/2

+1)+(k-1)=k(

lgk

-1)–k+2+(k-1)=k

lgk

–k+1=k

lgk

–(k-1)。

歸納成功。

由定理3.1知，T(n)=O(nlgn)。因為合并部分的最好情況需要至少min(n1,n2)=

n/2

次比較，所以有

T(n)

T(

n/2

)+T(

n/2

)+

n/2

。由主方法知，

T(n)

2T(

n/2

)+

n/2

=

(nlgn)。因此，合并排序的最好情況，最壞情況，以及平均情況的復(fù)雜度都是T(n)=

(nlgn)。14合并排序的優(yōu)缺點優(yōu)點：復(fù)雜度是最好的。在第4章中，我們會證明這一點。合并排序是個穩(wěn)定排序。缺點：不是就地操作的算法，它需要使用

(n)個除數(shù)組A[1..n]外的存儲單元。當(dāng)n很大時，這是一個很大的開銷。把數(shù)組C中元素再復(fù)制回數(shù)組A要消耗時間，相當(dāng)于把基本操作的次數(shù)加倍。當(dāng)n很大時，遞歸所需要用的堆棧也會增加開銷。15堆(heap)的數(shù)據(jù)結(jié)構(gòu)n個數(shù)字的最大堆是有n個結(jié)點(包括葉子)的二叉樹并滿足：每一個結(jié)點，包括葉結(jié)點，存有一個數(shù)。所有葉結(jié)點只出現(xiàn)在最底下二層，可證堆的高為h=lgn

。倒數(shù)第二層的所有內(nèi)結(jié)點出現(xiàn)在所有葉結(jié)奌的左邊。除最后一個內(nèi)結(jié)點可有一個左兒子外，每個內(nèi)結(jié)點必須有2個兒子。滿足最大堆順序：任一內(nèi)結(jié)點v中的數(shù)大于等于其兒子結(jié)點中的數(shù)，從而也大于等于v為根的子樹中所有結(jié)點的數(shù)。顯然，可以類似定義最小堆，因?qū)ΨQ性，我們只討論最大堆。在最大堆中，根結(jié)點中的數(shù)最大。4. 堆排序堆的例子16堆可以用一數(shù)組實現(xiàn)，例如上面的堆可存放如下：如何找出A[i]的兒子和父親？A[i]的左兒子

=

A[2i] (如果2i

>

n,

A[i]沒有左兒子。)A[i]的右兒子

=A[2i+1] (如果2i+1>n,A[i]沒有右兒子。)A[i]的父親 =

A[

i/2

] (i>1,否則A[i]=A[1]是根。)17堆排序簡介設(shè)A[1..n]是一個堆，A[1]是最大數(shù)。把A[1]和A[n]中的數(shù)交換后，最大數(shù)就放在了A[n]，這正是排序后放最大數(shù)的地方。然后，我們把A[n]從堆中切除，即把n減1。這樣，剩下的n-1個數(shù)就在A[1..n-1]中了。A[1..n-1]不再是堆，但我們可以把它修復(fù)成一個堆。修復(fù)后，A[1]是下一個最大的數(shù)，把它與A[n-1]交換可把第二大數(shù)安排好。重復(fù)這樣的過程直至所有數(shù)都安排好。堆修復(fù)算法我們假設(shè)，在需要修復(fù)的堆中，有一處，也僅有一處違反了堆順序。也就是說，在某一個內(nèi)結(jié)點A[i]中的數(shù)小于其某個兒子結(jié)點中的數(shù)值，而其余的所有內(nèi)結(jié)點A[j](j

i)都保持著最大堆順序，即A[j]中的數(shù)大于等于以A[j]為根的子樹中所有結(jié)點含有的數(shù)字。18堆修復(fù)算法偽碼：Max-Heapify(A[1..heap-size],i)l

←2i，r←2i+1

//左兒子的序號l，和右兒子的序號rif

l

heap-size

and

A[l]>A[i]

then

largest←l

elselargest←i //與左兒子比較誰大endififr

heap-size

and

A[r]>A[largest]

thenlargest←r //與右兒子比較誰大endififlargest

i

//如果A[i]比A[largest]小

thenA[i]

A[largest] //A[i]與該兒子交換

Max-Heapify([1..heap-size],largest) //遞歸修復(fù)該兒子這一點endifEnd堆修復(fù)算法例子19堆修復(fù)算法復(fù)雜度是2h=O(lgn)，因為最多遞歸h

次，每次做2次比較。20為輸入數(shù)據(jù)建堆方法是先把數(shù)字任意放到數(shù)組

A[1..n]中，然后調(diào)整為一個堆。把A[i]為根的子樹調(diào)整為一個堆的遞歸算法如下。Build-Max-Heap(A[1..n],i)1 l

2i

//l是左兒子的序號2 r

2i+1

//r是右兒子的序號3 if

l≤n

4

thenBuild-Max-Heap(A[1..n],

l) //遞歸為左子樹建堆5 endif6 if

r≤n

7

then

Build-Max-Heap

(A[1..n],

r)

//遞歸為右子樹建堆8 endifMax-Heapify(A[1..n],i) End調(diào)用Build-Max-Heap(A[1..n],

1)后，即可將A[1..n]變?yōu)橐粋€堆。21輸入數(shù)據(jù)建堆的復(fù)雜度置n=2h+1-1。這樣A[1..n]所對應(yīng)的二叉樹是一棵高度為h的滿二叉樹(completebinarytree)，這里h=lg(n+1)–1。滿二叉樹的所有葉結(jié)點都在底層。例如：

22堆排序算法

將A[1..n]建堆后，堆排序算法如下：Heapsort(A[1..n])Build-Max-Heap(A[1..n],

1)2 Heap-size

n3 while

heap-size>14

A[1]

A[heap-size]5

heap-size

heap-size-16

Max-Heapify(A[1..heap-size]，1)7 endwhile8 End堆排序復(fù)雜度O(n)時間建堆。然后，循環(huán)(n-1)次，因為堆修復(fù)的時間是O(lgn),所以最壞情況復(fù)雜度是

T(n)=O(n)+(n-1)O(lgn)=O(nlgn)堆排序舉例2324堆排序的優(yōu)缺點優(yōu)點：堆排序是個就地操作的算法。它的復(fù)雜度T(n)=

(nlgn)是漸近最優(yōu)。缺點：堆排序的最大缺點是不穩(wěn)定。讀者可以很容易地找到不穩(wěn)定的例子。最壞情況下，可證明，它需要至少2n-lg(n+1)次比較先構(gòu)建一個堆。而且，它的排序部分還需要約2nlgn次比較。所以，最壞情況時，比合并排序的

n

lgn

-(n-1)比較次數(shù)(定理3.1)要多將近一倍以上。25堆用作優(yōu)先隊列堆還可用來動態(tài)地管理和修改數(shù)據(jù)，比如插入一個數(shù)，刪除一個數(shù)，減少(或增加)一個數(shù)，找到最大(或最小)的數(shù)等。提供這些操作的數(shù)據(jù)結(jié)構(gòu)都稱為優(yōu)先隊列(Priorityqueue)。1. 增加堆中A[i]的值為新值keyHeap-Increase-Key(A[1..n]，i，key)1 ifkey<A[i]2

thenerror //要增加的值比原來值還小，不合理3 endif4 A[i]

key，father(i)

i/2

while

i>1and

A[father(i)]<A[i]

A[i]

A[father(i)]，i

father(i) father(i)

i/2

8 endwhile9 End

這個算法復(fù)雜度為O(lgn)。262. 插入一個數(shù)keyMax-Heap-Insert(A[1..heap-size],key)1 heap-size

heap-size

+12 n

heap-size3 A[n]

-

4 Heap-Increase-Key(A[1..n],n,key)End

//這個算法復(fù)雜度為O(lgn)。3. 取走最大數(shù)并放入變量max當(dāng)中

Heap-Extract-Max(A[1..heap-size]，max)1 n

heap-size2 if

n<13

thenreturn“error,heapunderflow”4 endif(接下頁)273. 最大數(shù)放入變量max當(dāng)中

(繼續(xù))max

A[1]A[1]

A[n]heap-size[A]

n–18 Max-Heapify(A[1..heap-size]，1)9 return

max10 End //這個算法復(fù)雜度為O(lgn)將最大數(shù)復(fù)制到變量max當(dāng)中(不刪除最大數(shù))Heap-Maximum(A[1..heap-size],max)1 if

heap-size<12 thenreturnerror“heapunderflow” //堆是個空集3 endif4 max

A[1]5 returnmax6 End //這個算法復(fù)雜度為O(1)5.

快排序28快排序用分治法序列含1個數(shù)或沒有數(shù)時是底，此時不需任何操作。取序列A[p..r]中一個數(shù)，例如A[r]，作為中心點。文獻中有各種取法，都差不多，本書取A[r]作為中心點。

把序列中數(shù)，從A[p]到A[r-1]，逐個與中心點比較，小于等于A[r]的數(shù)放左邊，大于A[r]的數(shù)放右邊。最后，A[r]放中間。 左邊任何數(shù)≤A[r]<右邊任何數(shù)。遞歸地快排序左、右兩部分。劃分A[p..r]為二的算法指針j指向下一個要檢查的數(shù)，初始值為p，即指向A[p]。指針i指向當(dāng)前左邊部分中最后一個數(shù)，初始值為p-1。29劃分算法每步的具體操作：每次我們比較A[j]和A[r]時，有兩種結(jié)果，分述如下：

如果A[j]>A[r]，A[j]中數(shù)字屬于第二部分，只需指針j加1。如果

A[j]≤A[r]，A[j]中數(shù)字屬于第一部分。把A[j]和A[i+1]中數(shù)字交換后可把A[j]中的數(shù)字并入第一部分。這時需把指針i和j分別加1。當(dāng)A[1..r-1]中每個數(shù)都和A[r]比較后，交換A[i+1]和A[r]中數(shù)字。這樣就把A[r]中數(shù)放在了中心點位置上。顯然，中心點位置是q

=i+1。30劃分算法偽碼：Partition(A[p..r],q)1 x

A[r]2 i

p-13 for

j

ptor-1 //每次操作后，for循環(huán)會把j加14 ifA[j]

x//如A[j]>x，不需任何操作，i不變5 then

i

i+16

A[i]

A[j]7

endif

8 endfor9 A[i

+1]

A[r] 10 q

i+1 //中心點在A[i+1]11 returnq12 End

劃分算法需要n-1次比較，是就地操作。這里，n=r-p+1。31I=p-1J=pr初始狀態(tài)28713564ij一次比較后28713564ij2次比較后28713564ij3次比較后28713564ij4次比較后21783564ij5次比較后21387564ij6次比較后21387564ij7次比較后21387564把A[r]放到中21347568心點后q劃分算法舉例32快排序算法偽碼Quicksort(A[p..r]) 1 ifp<r //如果p

r，則見底2

then Partition(A[p..r],q)3

Quicksort(A[p..q-1])4

Quicksort(A[q+1..r])5 endif6 End

如果要把A[1..n]排序的話，只需調(diào)用Quicksort(A[1..n])?？炫判蜃顗那闆r復(fù)雜度定理3.2

給定序列A[p..r]，快排序Quicksort(A[p..r])需要最多n(n-1)/2次比較，這里n為數(shù)組中元素的個數(shù)，即n=p-r+1。(證明見下頁)33

34

35

36*快排序算法最好情況復(fù)雜度定理3.4

給定序列A[p..r]，快排序Quicksort(A[p..r])需要最少

(n+1)lg(n+1)

–2n次比較，這里n=p-r+1

為數(shù)組中元素的個數(shù)。證明：

對n進行歸納證明。歸納基礎(chǔ)：n

=0時，T(0)=0,

(0+1)lg(0+1)

–2

0=0，定理正確。n

=1時，T(1)=0,

(1+1)lg(1+1)

–2

1=0，定理正確。n

=2時，T(2)=1,

(2+1)lg(2+1)

–2

2=

3lg3

–4=

4.755

–4=1，定理正確。歸納步驟：假設(shè)當(dāng)n=0，1，2，…，(k-1)時(k≥3)定理正確。我們證明當(dāng)n=k

時，定理也正確。假定在第一次劃分后，左部分有a(≥0)個元素而右部分有b(≥0)個元素，a+b=k-1。這一劃分需要k-1次比較。(接下頁)37定理3.4證明(繼續(xù))由歸納假設(shè)，第一部分排序最少需要

(a+1)lg(a+1)

–2a次比較，第二部分需要

(b+1)lg(b+1)

–2b

次比較，因此整個排序需要最少f(a,b)=(k-1)+

(a+1)lg(a+1)

–2a+

(b+1)lg(b+1)

–2b次比較。下面我們來簡化這個式子。f(a,b)=(k-1)+

(a+1)lg(a+1)

–2a+

(b+1)lg(b+1)

–2b

=

(a+1)lg(a+1)

+

(b+1)lg(b+1)

–2(a+b)+(k-1) ≥(a+1)lg(a+1)+(b+1)lg(b+1)–(k-1) (因為a+b=k-1)因為(a+1)lg(a+1)+(b+1)lg(b+1)在a=b=(k-1)/2時有極小值，所以f(a,b)≥

2(a+1)lg(a+1)–(k–1)=(k+1)lg((k+1)/2)–(k–1)=(k+1)(lg(k+1)-1)–(k–1)

=(k+1)lg(k+1)–2k。因為比較次數(shù)f(a,b)必須是整數(shù)，所以有f(a,b)≥

(k+1)lg(k+1)

–2k。歸納成功。38快排序的優(yōu)缺點優(yōu)點：快排序是一個就地操作的算法。它的平均復(fù)雜度

(nlgn)是漸近最優(yōu)。它實際使用的比較次數(shù)平均為1.39nlgn，優(yōu)于堆排序所需次數(shù)。缺點：最壞情況時有復(fù)雜度

(n2)，高于堆排序。它不是穩(wěn)定排序。第4章

不基於比較的排序算法1序言

2比較排序的復(fù)雜度下界

3不基於比較的線性時間排序算法

19計數(shù)排序

19基數(shù)排序

27桶排序

3121.序言可以證明，任何比較排序在最壞情況時需要至少lg(n!)

nlgn

次比較。要想有更快的排序算法，必須考慮不基於比較的排序。不基於比較的排序往往有額外的條件限制。主要討論：

計數(shù)排序

基數(shù)排序

桶排序32.比較排序的復(fù)雜度下界

決策樹模型及最壞情況下界

很多問題的決策是對輸入數(shù)據(jù)作一系列某個操作決定的。每次操作會有若干個可能的結(jié)果，而下次操作如何進行是根據(jù)這一次操作的結(jié)果而定，直到得到答案。這可用一個決策樹來描述。任何基於比較的排序都是通過一系列數(shù)字間的比較來決定輸入數(shù)據(jù)之間大小關(guān)系的，因此可以用一棵決策樹來描述。證明排序問題的下界，我們只需考慮輸入的n個數(shù)都不相等的情況。這是因為針對一個特殊情況的下界也一定是包含所有情況的下界。我們將證明，即使需要排序的n個數(shù)都不相等，任何基於比較的排序算法，在最壞情況時，都必須做至少

lg(n!)

nlgn次比較。

4例（圖4.1）：一個把a1,a2,a3

排序的決策樹有n個不同數(shù)的序列中，最小的數(shù)稱為第1順序數(shù)，第2小的數(shù)稱為第2順序數(shù)，…，第n個小的數(shù)(即最大的數(shù))稱為第n順序數(shù)。排序就是確定在原序列中，那個是第1順序數(shù)，那個是第2順序數(shù)，…，那個是第n順序數(shù)。所以，排序的本質(zhì)是給出n個順序數(shù)在原序列中的一個排列。(接下頁)5決策樹模型及最壞情況下界(繼續(xù))每個葉結(jié)點代表了一個從輸入序列A[1]，A[2]，…，A[n]，到輸出序列

B[1]<B[2]

<…

<B[n]的映射。如果B[j]=A[i]，那么，A[i]就是第j順序數(shù)(1

i

n)。我們可以定義這個映射函數(shù)為：

(i)=j。比如，圖4-1中葉結(jié)點(1,3,2)表示A[1]<A[3]<A[2]。這個映射函數(shù)是：

(1)=1，

(2)=3，

(3)=2。因為輸入的n個數(shù)都不相等，它們只能有一個排序結(jié)果，所以一個葉結(jié)點只能代表一個映射。因為一個映射正好等于一個n個元素的全排列，所以有n!個不同的映射。因此，決策樹必