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

1第1章

概述什么是計(jì)算機(jī)算法?

2算法的偽碼表示

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

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

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

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

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

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

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

一個(gè)例子:選擇排序輸入: 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這個(gè)偽碼可以更簡(jiǎn)潔地用下面?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這個(gè)偽碼顯然更清楚地反映出這個(gè)排序算法的思路和方法。53.

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

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

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

運(yùn)算時(shí)間的度量

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

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

n

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

n

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

我們用輸入數(shù)據(jù)之間的比較作為主要的基本運(yùn)算。分析如下：選出最小的數(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í)行的時(shí)間可能會(huì)大不相同。要分析三種情況的復(fù)雜度：最好情況復(fù)雜度：

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

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

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

往往假設(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ù)增長(zhǎng)漸近性態(tài)的比較11定義1.1

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

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

例1.4 證明n3+2n+5=O(n3)證明：因?yàn)楫?dāng)n≥1時(shí),我們有n3

+2n+5

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

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

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

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

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

(g(n))。

例1.5 證明

n2=

(nlgn)證明：因?yàn)楫?dāng)n

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

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

設(shè)f(n)和g(n)為兩個(gè)定義域?yàn)樽匀粩?shù)的正函數(shù)。如果關(guān)系f(n)=O(g(n))和f(n)=

(g(n))同時(shí)成立，我們則說(shuō)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時(shí)，n3

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

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

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

1415定理1.1

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

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

+…+a1n1

+a0是一個(gè)多項(xiàng)式，其中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

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

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

lgn!

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

lgn!

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

lgn!

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

(lgn!)或

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

章

分治法分治法原理

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

6替換法 7序列求和法和遞歸樹(shù)法

10主方法求解 123 例題示范

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

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

合：

如何從子問(wèn)題的解中獲得它們的父問(wèn)題的解。合是一個(gè)逐層向上的合并過(guò)程，直到最初的原問(wèn)題得解為止。23一個(gè)例子：二元搜索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幾點(diǎn)解釋：算法先找出序列的中位數(shù)A[mid]，mid=

(p+r)/2

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

n/2

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

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

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

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

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

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

2

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

n

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

(1)，故有c>0

使T(n)≤cnlgn?？杉俣╟>1。歸納步驟:假設(shè)當(dāng)n=2,3,4,…,(k-1)時(shí)，T(n)≤cnlgn成立。當(dāng)n=k(k≥5)時(shí)因?yàn)?/p>

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)。

(接下頁(yè))替換法

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

T(n)=

(1)，

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

T(n)=2T(

n/2

)+n

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

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

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

n

=2,3,4時(shí)，因?yàn)?2

(nlgn

+n)，而T(n)=

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

d

>0使

T(n)>12d

d(nlgn

+n)?？杉俣?/p>

d

<1/4。歸納步驟:

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

=k時(shí)(k

5)時(shí)，因?yàn)?/p>

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 (因?yàn)閘gn<n)=(dn/2)lgn–3dn/2

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

進(jìn)而從遞推關(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) (因?yàn)閐<1/4，–4dn+n>0)歸納成功。這就證明了T(n)=

(nlgn+n)=

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

(nlgn)。用替換法解遞推關(guān)系需要猜測(cè)出正確的復(fù)雜度并且往往需要分別證明上界和下界。當(dāng)然，很多時(shí)候，我們只需對(duì)上界作出估計(jì)，則可簡(jiǎn)化一些工作。另外，該方法需要一定的數(shù)學(xué)技巧。本書(shū)不常用這個(gè)方法。10序列求和法和遞歸樹(shù)法兩者的本質(zhì)相同，遞歸樹(shù)法用一棵樹(shù)把序列產(chǎn)生的過(guò)程顯示出來(lái)。例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遞歸樹(shù)k2kW(k-1)W(k-1)一步遞歸的樹(shù)k2k(k-1)2k-1(k-1)2k-1W(k-2)W(k-2)W(k-2)W(k-2)(b) 兩步遞歸樹(shù)

(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) 遞歸停止后的完整的遞歸樹(shù)12主方法求解

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

1,b>1。

用規(guī)則前先計(jì)算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。

因?yàn)閒(n)=nlgn=O(n1.8)，所以T(n)=

(n2)。13

143.

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

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

分為

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

M2=A[i2]+A[j2]是子問(wèn)題2的解。如果

M1

>M2，那么第1個(gè)解好些，但不一定是全局最優(yōu)，因?yàn)?/p>

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

A[p..mid]。從

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

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

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

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

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

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

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

章

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

2插入排序 3合并排序

7堆排序

15快排序

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

A[2]

…

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

i

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

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

A[1]，

A[2]，排好序，第2步： 把三個(gè)數(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)缺點(diǎn)缺點(diǎn)：復(fù)雜度較高，后面會(huì)介紹

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

A[2]

A[3]

…

A[n1] B[1]

B[2]

B[3]

…

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

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

C[2]

C[3]

…

C[n1+n2](偽碼見(jiàn)下頁(yè))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 //說(shuō)明序列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ù)組兩端的序號(hào)必須是變量，不能總是從1開(kāi)始。但這種修改極為容易，不在此贅述了。當(dāng)我們需要將數(shù)組A[1..n]排序時(shí)，只需調(diào)用Mergesort(A[1..n])即可。10二叉樹(shù)表示合并排序合并排序的遞歸過(guò)程可以用一棵二叉樹(shù)來(lái)表示。其劃分的順序是從根開(kāi)始，自上而下，與樹(shù)的前向遍歷一致，而合并的順序是從葉子(底)開(kāi)始，自下而上，與樹(shù)的后序遍歷順序一致。例子：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)式，直接驗(yàn)證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)。

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

n

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

5)時(shí)，有T(n)

n

lgn

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

時(shí)，仍然有T(n)

n

lgn

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

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

lg

k/2

=

lg(k/2)

=

lgk-1

=

lgk

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

lg

k/2

=

lg((k+1)/2)

=

lg(k+1)-1

=

lg(k+1)

-1=

lgk

-1。 (因?yàn)閗是奇數(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)(接下頁(yè))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)。因?yàn)楹喜⒉糠值淖詈们闆r需要至少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)缺點(diǎn)優(yōu)點(diǎn)：復(fù)雜度是最好的。在第4章中，我們會(huì)證明這一點(diǎn)。合并排序是個(gè)穩(wěn)定排序。缺點(diǎn)：不是就地操作的算法，它需要使用

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

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

=

A[2i] (如果2i

>

n,

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

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

A[

i/2

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

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

←2i，r←2i+1

//左兒子的序號(hào)l，和右兒子的序號(hào)rif

l

heap-size

and

A[l]>A[i]

then

largest←l

elselargest←i //與左兒子比較誰(shuí)大endififr

heap-size

and

A[r]>A[largest]

thenlargest←r //與右兒子比較誰(shuí)大endififlargest

i

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

thenA[i]

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

Max-Heapify([1..heap-size],largest) //遞歸修復(fù)該兒子這一點(diǎn)endifEnd堆修復(fù)算法例子19堆修復(fù)算法復(fù)雜度是2h=O(lgn)，因?yàn)樽疃噙f歸h

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

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

2i

//l是左兒子的序號(hào)2 r

2i+1

//r是右兒子的序號(hào)3 if

l≤n

4

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

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

r≤n

7

then

Build-Max-Heap

(A[1..n],

r)

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

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

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)時(shí)間建堆。然后，循環(huán)(n-1)次，因?yàn)槎研迯?fù)的時(shí)間是O(lgn),所以最壞情況復(fù)雜度是

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

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

n

lgn

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

thenerror //要增加的值比原來(lái)值還小，不合理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

這個(gè)算法復(fù)雜度為O(lgn)。262. 插入一個(gè)數(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

//這個(gè)算法復(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(接下頁(yè))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 //這個(gè)算法復(fù)雜度為O(lgn)將最大數(shù)復(fù)制到變量max當(dāng)中(不刪除最大數(shù))Heap-Maximum(A[1..heap-size],max)1 if

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

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

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

把序列中數(shù)，從A[p]到A[r-1]，逐個(gè)與中心點(diǎn)比較，小于等于A[r]的數(shù)放左邊，大于A[r]的數(shù)放右邊。最后，A[r]放中間。 左邊任何數(shù)≤A[r]<右邊任何數(shù)。遞歸地快排序左、右兩部分。劃分A[p..r]為二的算法指針j指向下一個(gè)要檢查的數(shù)，初始值為p，即指向A[p]。指針i指向當(dāng)前左邊部分中最后一個(gè)數(shù)，初始值為p-1。29劃分算法每步的具體操作：每次我們比較A[j]和A[r]時(shí)，有兩種結(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ù)字并入第一部分。這時(shí)需把指針i和j分別加1。當(dāng)A[1..r-1]中每個(gè)數(shù)都和A[r]比較后，交換A[i+1]和A[r]中數(shù)字。這樣就把A[r]中數(shù)放在了中心點(diǎn)位置上。顯然，中心點(diǎn)位置是q

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

A[r]2 i

p-13 for

j

ptor-1 //每次操作后，for循環(huán)會(huì)把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 //中心點(diǎn)在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心點(diǎn)后q劃分算法舉例32快排序算法偽碼Quicksort(A[p..r]) 1 ifp<r //如果p

r，則見(jiàn)底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ù)組中元素的個(gè)數(shù)，即n=p-r+1。(證明見(jiàn)下頁(yè))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ù)組中元素的個(gè)數(shù)。證明：

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

=0時(shí)，T(0)=0,

(0+1)lg(0+1)

–2

0=0，定理正確。n

=1時(shí)，T(1)=0,

(1+1)lg(1+1)

–2

1=0，定理正確。n

=2時(shí)，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)時(shí)(k≥3)定理正確。我們證明當(dāng)n=k

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

(a+1)lg(a+1)

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

(b+1)lg(b+1)

–2b

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

(a+1)lg(a+1)

–2a+

(b+1)lg(b+1)

–2b次比較。下面我們來(lái)簡(jiǎn)化這個(gè)式子。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) (因?yàn)閍+b=k-1)因?yàn)?a+1)lg(a+1)+(b+1)lg(b+1)在a=b=(k-1)/2時(shí)有極小值，所以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。因?yàn)楸容^次數(shù)f(a,b)必須是整數(shù)，所以有f(a,b)≥

(k+1)lg(k+1)

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

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

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

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

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

3不基於比較的線性時(shí)間排序算法

19計(jì)數(shù)排序

19基數(shù)排序

27桶排序

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

nlgn

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

計(jì)數(shù)排序

基數(shù)排序

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

決策樹(shù)模型及最壞情況下界

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

lg(n!)

nlgn次比較。

4例（圖4.1）：一個(gè)把a(bǔ)1,a2,a3

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

B[1]<B[2]

<…

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

i

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

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

(1)=1，

(2)=3，

(3)=2。因?yàn)檩斎氲膎個(gè)數(shù)都不相等，它們只能有一個(gè)排序結(jié)果，所以一個(gè)葉結(jié)點(diǎn)只能代表一個(gè)映射。因?yàn)橐粋€(gè)映射正好等于一個(gè)n個(gè)元素的全排列，所以有n!個(gè)不同的映射。因此，決策樹(shù)必