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

算法分析基本概念

*1.1 引言DonaldE.Knuth計(jì)算機(jī)科學(xué)就是算法研究例，編譯程序和操作系統(tǒng)是具有特定目標(biāo)的算法的直接實(shí)現(xiàn)。**算法（Algorithm） 解題方案的準(zhǔn)確完整的描述，是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。①無論是解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)，后者是操作實(shí)現(xiàn)。②算法不是程序，但算法是用程序或程序偽代碼來描述的。算法分析（AlgorithmAnalysis）算法分析是研究算法一旦轉(zhuǎn)換成某種語言的程序，該程序在計(jì)算機(jī)上運(yùn)行需要多少時(shí)間和存儲(chǔ)空間，才能完成解題方案。*

確定一個(gè)程序的運(yùn)行效率，可使用數(shù)學(xué)分析方法，也可使用實(shí)驗(yàn)測(cè)試方法，以期在理論和實(shí)踐作出評(píng)價(jià)。1.2 歷史背景20世紀(jì)早期，能否用一種有效的過程（算法）來求解問題受到廣泛關(guān)注，人們的注意力是放在問題的可解和不可解的分類上。問題的可判定性和可解性的研究領(lǐng)域稱為“可計(jì)算理論”。數(shù)字計(jì)算機(jī)出現(xiàn)以后，由于有限的資源，提出了盡可能少用資源的有效算法的需求，導(dǎo)致出現(xiàn)計(jì)算復(fù)雜性的新領(lǐng)域?！坝?jì)算復(fù)雜性”是研究可解類問題的效率，所謂效率是指解決問題所需的時(shí)間和空間。*1.3 二分搜索㈠順序搜索（線性搜索） 問題：設(shè)A[1..n]為一個(gè)n個(gè)元素（整數(shù)）的數(shù)組，判定給定元素x是否在A中。算法：掃描A的所有項(xiàng)目，將每個(gè)項(xiàng)目與x比較，如果在第j次比較后（1≤j≤n）搜索成功，即x=A[j]，則返回j值；否則返回0，表示沒有找到。這種方法稱為順序搜索。*算法1.1LinearSearch（Page3）輸入：n個(gè)元素的數(shù)組A[1..n]和元素x。輸出：如果x=A[j]，1≤j≤n，則輸出j，否則輸出0。1. j←12. while(j<n)and(x≠A[j])3. j←j+14. endwhile5. if(x=A[j])thenreturnjelsereturn0*出循環(huán)分析：

①x=A[j]，此時(shí)j<n。

②j等于n，但A[n]與x尚未比較。1.j←1while(j≤n)if(x=A[j])thenreturnj

j←j+15.endwhilereturn0㈡順序搜索法分析

最少比較次數(shù)為1，最多比較次數(shù)為n。㈢二分搜索令A(yù)[low..high]為元素按升序排列的非空數(shù)組，數(shù)A[mid]為中間元素。假定x>A[mid]，如果x在A中，則它必定是

A[mid+1]，A[mid+2]，…，A[high]中的一個(gè)，接下來只需在A[mid+1..high]中搜索x。換句話說，A[low..mid]中的項(xiàng)目在后續(xù)比較中被掉棄了。類似地，如果x<A[mid]，只需在A[low..mid-1]中搜索x。由于重復(fù)進(jìn)行二等分，導(dǎo)致了一個(gè)稱為二分搜索的有效策略。*算法1.2BinarySearch（Page4）輸入：n個(gè)元素的數(shù)組A[1..n]（按升序排列）和元素x。輸出：如果x=A[j]，1≤j≤n，則輸出j，否則輸出0。1. low←1:high←n:j←02. while(low≤high)and(j=0)3. mid←

(low+high)/2

//取整4. if(x=A[mid])thenj←mid elseif(x<A[mid])thenhigh←mid-16. elselow←mid+1 //x>A[mid]7. endwhile8. returnj**1457891012152223273235A[1..14]=A[8..14]=121522A[8..10]=①要搜索元素x=22。首先將x與A的中間元素比較，A[(1+14)/2]=A[7]=10，由于x>A[7]，可以把A[1..7]掉棄。②在剩余元素A[8..14]中搜索x，A[(8+14)/2]=A[11]=23，由于x<A[11]，可以把A[11..14]掉棄。12152223273235考慮搜索數(shù)組1 7 148 11 1489 10*A[10]=22③在剩余元素A[8..10]中搜索x，A[(8+10)/2]=A[9]=15，由于x>A[9]，可以把A[8..9]掉棄。④留在序列中僅剩一個(gè)項(xiàng)目A[10]=22，最后找到x=A[10]，搜索成功完畢（若x≠A[10]，則low≤high條件不成立，出循環(huán)）。10121522A[8..10]=89 10*㈣二分搜索法分析假定每個(gè)三向比較(if-then-else)計(jì)為一次比較，顯然最小比較次數(shù)為1，即搜索元素x在序列中間位置。為了計(jì)算最大比較次數(shù)，不失一般性，可假定x≥A[high]。①第2次迭代前（即第1次迭代結(jié)束后）數(shù)組A中剩余元素 若n是偶數(shù)，A[(mid+1)..n]共有n/2個(gè)元素。 若n是奇數(shù)，A[(mid+1)..n]共有(n-1)/2個(gè)元素。二種情況都有：A[mid+1..n]=

n/2

=

n/22-1

②第3次迭代前數(shù)組A中剩余元素

n/2

/2

=

n/4

=

n/22

=

n/23-1

③第j次迭代前數(shù)組A中剩余元素

n/2j-1

④搜索x的終止條件是余下元素僅僅為1個(gè)，即

n/2j-1

=1n=10,mid=

(10+1)/2

=5,剩余元素A[6..10],共計(jì)5個(gè)(

10/2

)。n=11,mid=

(11+1)/2

=6,剩余元素A[7..11],共計(jì)5個(gè)(

11/2

)。

當(dāng)

n/2j-1

=1，j為最大迭代次數(shù)（最大循環(huán)次數(shù)、最大比較次數(shù)）

n/2j-1

=1等價(jià)于1≤n/2j-1<2等價(jià)于2j-1≤n<2j等價(jià)于（取對(duì)數(shù)）j-1≤Log2n<j考慮

Log2n

≤Log2n<

Log2n

+1因?yàn)閖是整數(shù)，故有j-1=

Log2n

或j=

Log2n

+1二者均有j=

Log2n

+1*105 231 8 15 32 4 7 9 12 22 27 35*

可將二分搜索法的執(zhí)行描述為決策樹，紅色的結(jié)點(diǎn)是與x=22相比較的數(shù)字。

14578912152223273235

定理1.1（Page6）對(duì)于一個(gè)大小為n的已排序數(shù)組，算法BinarySearch執(zhí)行比較的最大次數(shù)為:

Log2n

+1*注：由于if-then-else嵌套使用，最大比較次數(shù)實(shí)質(zhì)上應(yīng)為迭代次數(shù)2倍，即2(

Log2n

+1)。如果考慮while語句的比較次數(shù)，則最大比較次為4(

Log2n

+1)。x首先與10比較，由于22比10大，故與23比較。以此類推，直至22。

決策樹的高度為

Log2n

，由決策樹可知，二分搜索法的最大比較次數(shù)是

Log2n

+1。1.4合并二個(gè)已排序的表㈠算法描述

假定有一個(gè)數(shù)組A[1..m]，p，q，r是它的三個(gè)索引，并有1≤p≤q<r≤m，二個(gè)子數(shù)組A[p..q]和A[q+1..r]各自按升序排列，重新排列A中元素的位置，使得子數(shù)組A[p..r]按升序排列。①使用二個(gè)指針s和t，初始化時(shí)s=p、t=q+1，s和t各自指向A[p]和A[q+1]，空數(shù)組B[p..r]用作暫存器。②每一次比較元素A[s]和A[t]，將小的元素添加到B中。然后更新指針，若A[s]≤A[t]，則s加1，否則t加1。③當(dāng)s=q+1，說明子數(shù)組A[p..q]的全部元素已進(jìn)入B，無需再比較，此時(shí)把子數(shù)組余下部分A[t..r]添加到B中。④當(dāng)t=r+1，說明子數(shù)組A[q+1..r]的全部元素已進(jìn)入B，無需再比較，此時(shí)把子數(shù)組余下部分A[s..q]添加到B中。⑤最后將B[p..r]復(fù)制到A[p..r]。*過程1.3Merge（Page6）輸入：數(shù)組A[1..m]和它的三個(gè)索引p，q，r，1≤p≤q<r≤m，二個(gè)子數(shù)組A[p..q]和A[q+1..r]各自按升序排列。輸出：子數(shù)組A[p..r]按升序排列。0.procedureMerge(A[1..m],p,q,r)1. comment:B[p..r]是個(gè)輔助數(shù)組 //或B[1..m]2. s←p:t←q+1:k←p //s和t分別指向數(shù)組A二個(gè)子數(shù)組元素3. while(s≤q)and(t≤r) //k指向數(shù)組B當(dāng)前空白元素位置4. ifA[s]≤A[t]thenB[k]←A[s]:s←s+15. elseB[k]←A[t]:t←t+16. endif7. k←k+1 //指向數(shù)組B下一個(gè)空白位置8. endwhile9. ifs=q+1thenB[k..r]←A[t..r]//說明子數(shù)組A[p..q]元素已處理完10. elseB[k..r]←A[s..q]//否則t=r+1，說明子數(shù)組A[q+1..r]已處理完。11. endif12. A[p..r]←B[p..r] //復(fù)制13.endprocedure**2316711134557qrkt0.procedureMerge(A[1..m],p,q,r)1. comment:B[p..r]是個(gè)輔助數(shù)組2. s←p:t←q+1:k←p 3. while(s≤q)and(t≤r)4. ifA[s]≤A[t]thenB[k]←A[s]:s←s+15. elseB[k]←A[t]:t←t+16. endif7. k←k+18. endwhile9. ifs=q+1thenB[k..r]←A[t..r]10. elseB[k..r]←A[s..q]11. endif12. A[p..r]←B[p..r]13.endprocedurespA[p..r]=A[p..q]+A[q+1..r]B[p..r]*㈡算法分析設(shè)有個(gè)數(shù)分別為n1和n2的二個(gè)子數(shù)組n1+n2=n，如果子數(shù)組A[p..q]中每個(gè)元素均小于另一個(gè)子數(shù)組A[q+1,r]中的所有元素，例，要合并下面二個(gè)子數(shù)組：236711134557

該算法只需執(zhí)行3次比較，即n1次比較。另一方面，比較次數(shù)最多為n-1=n1+n2-1次。例如要合并下面二個(gè)子數(shù)組：2366711134557就需要7次比較。所以，算法Merge的最少比較次數(shù)是n1，最大比較次數(shù)為n-1。*觀察結(jié)論1.1（Page7）執(zhí)行算法Merge，將個(gè)數(shù)分別為n1和n2的非空數(shù)組合并成一個(gè)為n=n1+n2的排序數(shù)組。設(shè)n1≤n2

，元素的比較次數(shù)在n1和n-1之間。特例，如果二個(gè)數(shù)組大小為

n/2

和

n/2

，需要比較的最大次數(shù)在

n/2

和n-1之間。觀察結(jié)論1.2（Page7）執(zhí)行算法Merge，將個(gè)數(shù)分別為n1和n2的非空數(shù)組合并成一個(gè)為n=n1+n2的排序數(shù)組，元素的賦值次數(shù)恰好是2n。1.5 選擇排序法㈠選擇算法假定有一個(gè)數(shù)組A[1..n]，A[i..n]是它的一個(gè)子數(shù)組，1≤i<n。編寫一函數(shù)，作用為：從A[i..n]中選擇一個(gè)最小的數(shù)A[k]（i<k≤n），將A[i]和A[k]互換（若k=i，無需交換）。過程Selection(參見Page8)輸入：A[i..n]輸出：A[i..n]，其中A[i]為A[i..n]中的最小的數(shù)。0.procedureSelection(i)1. k←i2. forj←i+1ton3. ifA[j]<A[k]thenk←j4. endfor5. ifk≠ithen交換A[i]和A[k] 6.endprocedure **㈡選擇排序算法設(shè)A[1..n]為n個(gè)元素的數(shù)組，選擇排序算法如下：

①首先找到最小元素，并將其存放在A[1]中。

②然后在剩下的n-1個(gè)元素中找到最小元素，將其存放在A[2]中。

③重復(fù)此過程，直至找到第二大元素，并將其存放在A[n-1]中。算法1.4SelectionSort（參見Page8）輸入：數(shù)組A[1..n]輸出：按升序排列的數(shù)組A[1..n]1. fori←1ton-12. Selection(i)endfor *㈢選擇排序算法分析

這個(gè)算法執(zhí)行的元素比較次數(shù)為：可以看出元素的交換次數(shù)界于0和n-1之間，由于每次交換需要3次元素賦值，因此元素賦值次數(shù)界于0和3(n-1)之間。觀察結(jié)論1.3(Page8)

執(zhí)行算法SelectionSort所需的元素比較次數(shù)為n(n-1)/2，元素的賦值次數(shù)界于0與3(n-1)之間。1.6插入排序㈠插入算法假定有一個(gè)數(shù)組A[1..n]，A[1..i]是它的一個(gè)子數(shù)組，1<i≤n。A[1..i-1]已按升序排列。編寫一函數(shù)，作用為：將x=A[i]插入到子數(shù)組A[1..i-1]中，使得A[1..i]按升序排列。依次掃描序號(hào)從j=i-1到j(luò)=1的元素，將x和A[j]比較。在掃描的每一步，元素都被移到序號(hào)更高的一個(gè)位置上，這種過程直到以下情況出現(xiàn)時(shí)終止：

①找到一個(gè)小于等于A[i]的元素A[j] ②元素A[1]已掃描過此時(shí)可將x插入到A[j]（A[j]已移入A[j+1]）。**過程Insertion（參見9）輸入：A[1..i-1]已按升序排列 輸出：A[1..i]按升序排列0.procedureInsertion(i)1. x←A[i]2. j←i-13. while(j>0)and(A[j]>x)4. A[j+1]←A[j]5. j←j-16. endwhile 7. A[j+1]←x8.endprocedure *㈡插入排序算法

設(shè)A[1..n]為n個(gè)元素的數(shù)組，插入排序算法描述如下：

①從子數(shù)組A[1]開始，它自然是已排序好的。

②接下來，將A[2]插入到A[1]的前面或后面。

③然后，再將A[3]插入到A[1..2]中。

④直到A[n]插入到A[1..n-1]中為止。算法1.6InsertionSort(參見9)輸入：數(shù)組A[1..n]輸出：按升序排列的數(shù)組A[1..n]1. fori←2ton2. Insertion(i)endfor *㈢插入排序算法分析執(zhí)行InsertionSort，元素比較次數(shù)取決于輸入元素的順序。①當(dāng)序列已按升序排列時(shí)，元素比較次數(shù)最小，僅為n-1，每個(gè)元素A[i]（2≤i≤n）只和A[i-1]比較。②當(dāng)元素已按降序排列，并且所有元素各不相同，比較次數(shù)為最大。如下所示：

因?yàn)槊總€(gè)元素A[i](2≤i≤n)都和子序列A[1..i-1]中的每個(gè)元素比較，這一結(jié)果與算法SelectionSort相一致。*觀察結(jié)論1.4（Page9）執(zhí)行算法InsertionSort的元素比較次數(shù)在n-1到n(n-1)/2之間。元素賦值次數(shù)等于元素比較次數(shù)加上n-1。說明：若原全部元素已按升序排列，在Insertion過程中，每次僅需一次比較，故總比較次數(shù)為n-1，循環(huán)中的賦值不執(zhí)行。因?yàn)樵诔鲅h(huán)后有一次賦值，所以此時(shí)元素賦值總的次數(shù)為n-1。若原全部元素已按降序排列，在Insertion過程中，出循環(huán)由(j>0)不成立引起，此時(shí)元素總的比較次數(shù)為n(n-1)/2，所以循環(huán)體中元素賦值總的次數(shù)為n(n-1)/2。考慮出循環(huán)后賦值，此時(shí)元素賦值總次數(shù)應(yīng)為n(n-1)/2+n-1。*“選擇排序法”和“插入排序法”小結(jié)輸入：A[1..i-1]已按升序排列輸出：A[1..i]按升序排(1)選擇法（往后選擇）

Seletion(i)

從A[i..n]中選擇一個(gè)最小的數(shù)，將其和A[i]交換，使得A[1..i]有序。(2)插入法（向前插入）

Insertion(i)

將A[i]中的元素插入到A[1..i]中一個(gè)合適位置，使得A[1..i]有序。*245994521746492517461467124456791.7 自底向上合并排序㈠引入插入和選擇排序法的最大比較次數(shù)都與n2成正比，從這個(gè)意義上來說二種算法的效率都是比較低的，考慮下面的排序方法：㈡自底向上合并排序算法

設(shè)A[1..n]為需排序的n個(gè)元素的數(shù)組①第1次迭代生成個(gè)數(shù)為2（=21）的排序序列，該序列共有=個(gè)。若剩余1個(gè)元素，則讓它進(jìn)入下一輪合并。*945217464925174694521744925174②第2次迭代生成個(gè)數(shù)為4（=22）的排序序列，共有=個(gè)。若剩余1或2個(gè)，則讓它進(jìn)入下一輪合并。如果剩余3個(gè)，則將2個(gè)元素（已排序）和另外1個(gè)元素合并成一個(gè)3元素的排序序列。*245949251746146724594925174147

③第j次迭代（假設(shè)j=3）生成元素個(gè)數(shù)為2j個(gè)的排序序列，該序列共有個(gè)，可能剩余的元素個(gè)數(shù)k，其大小在1至2j-1之間。若1≤k≤2j-1，則讓它們進(jìn)入下一次合并（局部已有序）。若2j-1＜k＜2j，則將2j-1個(gè)元素（局部已有序）和另外k-2j-1個(gè)元素（局部已有序）合并成個(gè)數(shù)為k的排序序列。*剩余元素為7個(gè)245914671244567924591471244579④總的迭代次數(shù)j的值范圍為：2j-1<n≤2j

。*算法1.6BottomUpSort（Page10）輸入：n個(gè)元素的數(shù)組A[1..n]輸出：按升序排列的數(shù)組A[1..n]1. t←12. whilet<n3. s←t:t←2s:i←0//i表示要處理數(shù)據(jù)的起始地址(簡(jiǎn)稱位移)4. whilei+t≤n5. Merge(A,i+1,i+s,i+t)

//Merge(A,p,q,r)6. i←i+t //i表示要處理數(shù)據(jù)的起始地址(簡(jiǎn)稱位移)7. endwhile8. ifi+s<nthenMerge(A,i+1,i+s,n)

endwhile //n-i>s表示剩余的元素個(gè)數(shù)大于被合并的子序列長(zhǎng)度s為被合并的子序列長(zhǎng)度，初始時(shí)為1，每循環(huán)一次乘以2。t為s的二倍，即二個(gè)子序列合并后的長(zhǎng)度，可省略(見下頁)。當(dāng)n不是t的整數(shù)倍，出內(nèi)層循環(huán)后執(zhí)行第8步。如果剩余元素?cái)?shù)目大于s，就要將最后一個(gè)長(zhǎng)度為s的子序列和剩余元素進(jìn)行一次合并排序，此時(shí)二個(gè)子序列合并后的長(zhǎng)度小于t=2s。*61095311481276105931148127569103481112734568910111271234567891011㈢示例

當(dāng)n不是2的整數(shù)冪時(shí)，自底向上合并排序的過程如下所示：*第1次迭代：t=1＜n=11成立

s=1,t=2i值的范圍：0,2,4,8 i=0 MERGE(A,1,1,2) i=2 MERGE(A,3,3,4) i=4 MERGE(A,5,5,6) i=6 MERGE(A,7,7,8) i=8 MERGE(A,9,9,10) i=10時(shí)，i+t≤11不成立，出循環(huán)。出循環(huán)后，i+s=10+1＜n=11不成立，因此不再合并，最后一個(gè)序列長(zhǎng)度為1（或稱剩下的元素個(gè)數(shù)）。MERGE(A,i+1,i+s,i+t)s表示被合并序列的長(zhǎng)度（即合并前）t表示合并后序列的長(zhǎng)度（初值為1）i表示位移61095311481276105931148127*第2次迭代：t=2＜n=11成立

s=2,t=4i值的范圍：0,4,8 i=0 MERGE(A,1,2,4) i=4 MERGE(A,5,6,8) i=8時(shí)，i+t≤11不成立，出循環(huán)。出循環(huán)后，i+s=8+2＜n=11成立，執(zhí)行MERGE(A,9,10,11)，最后一個(gè)序列長(zhǎng)度為3。MERGE(A,i+1,i+s,i+t)s表示被合并序列的長(zhǎng)度（即合并前）t表示合并后序列的長(zhǎng)度（初值為1）i表示位移61059311481275691034811127*第3次迭代：t=4＜n=11成立

s=4,t=8i值的范圍：0,8 i=0 MERGE(A,1,4,8) i=8時(shí)，i+t≤11不成立，出循環(huán)。出循環(huán)后，i+s=8+4＜n=11不成立，因此不再合并，最后一個(gè)序列長(zhǎng)度為3。MERGE(A,i+1,i+s,i+t)s表示被合并序列的長(zhǎng)度（即合并前）t表示合并后序列的長(zhǎng)度（初值為1）i表示位移56910348111273456891011127*第4次迭代：t=8＜n=11成立

s=8,t=16i值的范圍：0 i=0時(shí)，i+t≤11不成立，出循環(huán)。出循環(huán)后，i+s=0+8＜n=11成立，執(zhí)行MERGE(A,1,8,11)。MERGE(A,i+1,i+s,i+t)s表示被合并序列的長(zhǎng)度（即合并前）t表示合并后序列的長(zhǎng)度（初值為1）i表示位移34568910111271234567891011第5次迭代：t=16＜n=11不成立，終止執(zhí)行。*算法1.6BottomUpSort（省略變量t）輸入：n個(gè)元素的數(shù)組A[1..n]輸出：按升序排列的數(shù)組A[1..]1. s←1 //s表示被合并序列的長(zhǎng)度（即合并前）

2. whiles<n //2s表示合并后序列的長(zhǎng)度（s初值為1）

3. i←04. whilei+2*s≤n5. Merge(A,i+1,i+s,i+2s)6. i←i+2s7. endwhile8. ifi+s<nthenMerge(A,i+1,i+s,n)9.

s←2s

10. endwhile*㈣自底向上合并排序算法分析

假設(shè)數(shù)組元素個(gè)數(shù)n為2的冪，外部循環(huán)次數(shù)為k=log2n。在執(zhí)行內(nèi)部循環(huán)后，由于n為2的冪，故第8步永遠(yuǎn)不會(huì)執(zhí)行。①在第1次迭代中，共執(zhí)行了n/2次比較。n個(gè)元素被劃分為n/2個(gè)段（段長(zhǎng)=2），段內(nèi)有序。②在第2次迭代中，n/2個(gè)段（段長(zhǎng)=2）元素序列被合并成n/4個(gè)段（段長(zhǎng)=4），段內(nèi)有序。根據(jù)觀察結(jié)論1.1（Page7），每對(duì)合并需要的比較次數(shù)，最少為2，最多為3。③在第3次迭代中，n/4個(gè)段（段長(zhǎng)=4）元素序列被合并成n/8個(gè)段（段長(zhǎng)=8），段內(nèi)有序。根據(jù)觀察結(jié)論1.1（Page7），每對(duì)合并需要的比較次數(shù)，最少是4，最多7。*最少比較次數(shù)（k=log2n）④在第j次迭代中，個(gè)段（段長(zhǎng)=2j-1）元素序列被合并成個(gè)段（段長(zhǎng)=2j），段內(nèi)有序。根據(jù)觀察結(jié)論1.1（Page7），每對(duì)合并需要的比較次數(shù)，最少是2j-1，最多為2j-1。*最多比較次數(shù)(k=log2n)（共k項(xiàng)）*觀察結(jié)論1.5（Page11)

用算法BottomUpSort對(duì)n個(gè)元素進(jìn)行排序，當(dāng)n為2的整數(shù)冪時(shí)，比較次數(shù)在(nlog2n)/2到nlog2n-n+1之間。執(zhí)行該算法的元素賦值次數(shù)為2nlog2n。1.8時(shí)間復(fù)雜性

在計(jì)算復(fù)雜性領(lǐng)域中，主要是研究一個(gè)算法所需要的時(shí)間和空間。即當(dāng)給出合法的輸入時(shí)，為了得到輸出，該算法執(zhí)行時(shí)所需要的時(shí)間和空間，其中時(shí)間尤為重要。執(zhí)行算法BottomUpSort的最大比較次數(shù)nlog2n-n+1執(zhí)行算法SelectionSort的最大比較次數(shù)n(n-1)/2

假設(shè)一次比較所需的時(shí)間為10-6秒，當(dāng)數(shù)據(jù)個(gè)數(shù)n分別為27=128和220=1048576時(shí)，二個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間上限如下表所示：*nSelectionSortBottomUpSort2710-6*128(128-1)/2≈0.008秒10-6*(128*7-128+1)≈0.0008秒22010-6*220*(220-1)/2≈6.4天10-6*(220*20-220+1)≈20秒㈠概述

稱“一個(gè)算法A對(duì)于輸入x要用y秒來運(yùn)行”是沒有意義的，也是沒有必要的。因?yàn)橛绊懸粋€(gè)算法的實(shí)際運(yùn)行時(shí)間與諸多因素有關(guān)（例機(jī)器性能、語言選擇、編譯程序優(yōu)劣、程序員素質(zhì)等），甚至無需計(jì)算出算法運(yùn)行時(shí)間的近似數(shù)，理由：①算法分析通常是將解決同一問題的各種算法進(jìn)行相互比較，執(zhí)行時(shí)間是相對(duì)的，而不是絕對(duì)的。②算法可以用各種語言來表示，甚至使用人類語言。③算法應(yīng)獨(dú)立于機(jī)器，無論科技如何進(jìn)步，對(duì)算法運(yùn)行時(shí)間的評(píng)估始終成立。④算法分析不拘泥小規(guī)模數(shù)據(jù)的輸入，主要關(guān)心在大的輸入實(shí)例時(shí)，算法運(yùn)行狀況。例某一算法運(yùn)行時(shí)間為2n3，當(dāng)n變得很大時(shí)，常數(shù)2將不起作用。觀察函數(shù)n2log2n+10n2+n

中的低階項(xiàng)10n2和n

，當(dāng)n值越大，10n2+n對(duì)函數(shù)值的影響就越小。**①漸近運(yùn)行時(shí)間去除表示算法運(yùn)行時(shí)間函數(shù)的低價(jià)項(xiàng)和首項(xiàng)系數(shù)（常數(shù)）。②時(shí)間復(fù)雜性在算法分析中通常是用漸近運(yùn)行時(shí)間來度量一個(gè)算法，漸近運(yùn)行時(shí)間通常稱為時(shí)間復(fù)雜性。③算法分析中的漸近符號(hào)有：O、Ω、Θ、o。④表示時(shí)間復(fù)雜性的常用函數(shù)有： 常數(shù)： 1 運(yùn)行時(shí)間為恒定值，和輸入無關(guān)。 次線性函數(shù)：log2n（簡(jiǎn)記為logn)

線性函數(shù)： n

次平方函數(shù)：nlog2n（簡(jiǎn)記為nlogn)

平方函數(shù)： n2

立方函數(shù)： n3

指數(shù)函數(shù)： 2n 運(yùn)行時(shí)間是爆炸性的 階乘函數(shù)（超指數(shù)函數(shù)）：n! 運(yùn)行時(shí)間是爆炸性的*定義1.2（Page16）令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果存在一個(gè)自然數(shù)n0和一個(gè)正常數(shù)c，使得

n≥n0

，f(n)≤cg(n)則稱f(n)=O(g(n))，n0稱為閾值。㈡O符號(hào)（讀作大O）

若極限為非0正常數(shù)，則函數(shù)f(n)和g(n)增長(zhǎng)速度至多相差常數(shù)倍，或稱為同一級(jí)別；若極限為0，說明隨著n的增大，函數(shù)f(n)的增長(zhǎng)要比g(n)的增長(zhǎng)慢得多。正常數(shù)，可以是0。*例1：f(n)=3n+2，求g(n)，使得f(n)=O(g(n))。解1： 當(dāng)n≥2，f(n)=3n+2≤3n+n=4n

令g(n)=n，當(dāng)n≥2時(shí)有f(n)≤4g(n) ∵f(n)≤4g(n) ∴f(n)=O(g(n))=O(n)解2：令g(n)=n同理可證：f(n)=O(nk)，k≥1*例2：f(n)=10n2+4n+2，求g(n)，使得f(n)=O(g(n))。解1： 當(dāng)n≥2，有f(n)≤10n2+4n+n=10n2+5n

當(dāng)n≥5，有f(n)≤10n2+5n≤10n2+n2=11n2

令g(n)=n2，因?yàn)楫?dāng)n≥5時(shí)有f(n)≤11g(n)

所以f(n)=O(g(n))=O(n2)解2：令g(n)=n2同理可證：f(n)=O(nk)，k≥2*例3：f(n)=6*2n+n2，求g(n)，使得f(n)=O(g(n))。解： 當(dāng)n≥4，有n2≤2n

故當(dāng)n≥4，有f(n)=6*2n+n2≤6*2n+2n=7*2n

令g(n)=2n，因?yàn)楫?dāng)n≥4時(shí)有f(n)≤7g(n)

所以f(n)=O(g(n))=O(2n)O符號(hào)提供了運(yùn)行時(shí)間的上界。算法InsertionSort執(zhí)行的比較次數(shù)最多為cn2（=n(n-1)/2），c為某個(gè)適當(dāng)選擇的常數(shù)，可稱該算法的運(yùn)行時(shí)間是O(n2)。只要當(dāng)排序元素的個(gè)數(shù)不小于某個(gè)閾值n0時(shí)，運(yùn)行時(shí)間最多為cn2。應(yīng)強(qiáng)調(diào)的是，即使當(dāng)輸入很大時(shí)，也不能說運(yùn)行時(shí)間恰好為O(n2)，因?yàn)楫?dāng)輸入已經(jīng)按升序排列，算法InsertionSort執(zhí)行的比較次數(shù)為n-1。*㈢Ω符號(hào)（讀作omiga）定義1.3（Page16）令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果存在一個(gè)自然數(shù)n0和一個(gè)正常數(shù)c，使得

n≥n0

，f(n)≥cg(n)則稱f(n)=Ω(g(n))，n0稱為閾值。

若極限是一個(gè)正常數(shù)，說明函數(shù)f(n)的增長(zhǎng)速度和函數(shù)g(n)相差整數(shù)倍，基本為同一級(jí)別；若極限為∞，說明隨著n的增大，函數(shù)f(n)增長(zhǎng)的速度要比g(n)快得多?？梢允钦?shù)或∞*例1：f(n)=3n+2，求g(n)，使得f(n)=Ω(g(n))。解： 當(dāng)n>0，f(n)=3n+2≥3n。 令g(n)=n，因?yàn)楫?dāng)n>0時(shí)有f(n)≥3g(n)

所以f(n)=Ω(g(n))=Ω(n)例2：f(n)=10n2+4n+2，求g(n)，使得f(n)=Ω(g(n))。解：令g(n)=n同理可證：f(n)=Ω(nk)，0≤k≤2*在常數(shù)因子范圍內(nèi)，O符號(hào)提供了運(yùn)行時(shí)間上界，而Ω符號(hào)提供了運(yùn)行時(shí)間下界。稱算法InsertionSort的元素比較次數(shù)至少是cn（=n-1

），c為某一合適的常數(shù)。在這種情況下，稱算法InsertionSort的運(yùn)行時(shí)間是Ω(n)。無論何時(shí)，當(dāng)排序元素個(gè)數(shù)不小于某一個(gè)閾值n0時(shí)，運(yùn)行時(shí)間至少是cn。稱排序問題的比較次數(shù)為Ω(nlog

n)，是指無法設(shè)計(jì)出一個(gè)新的基于比較的排序算法，它的時(shí)間復(fù)雜性小于nlog

n。Ω符號(hào)定義的一個(gè)重要推論：

f(n)=Ω(g(n))，當(dāng)且僅當(dāng)g(n)=O(f(n))*㈣Θ符號(hào)（讀作theta）定義1.4（Page16）令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果存在一個(gè)自然數(shù)n0和二個(gè)正常數(shù)c1和c2，使得

n≥n0

，c1g(n)≤f(n)≤c2g(n)則稱f(n)=Θ(g(n))，n0稱為閾值。Θ符號(hào)定義的一個(gè)重要推論：f(n)=Θ(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))并且g(n)=O(f(n))

極限是一個(gè)正常數(shù)，說明函數(shù)f(n)的增長(zhǎng)速度和函數(shù)g(n)的增長(zhǎng)速度相差整數(shù)倍，基本為同一級(jí)別。*例：f(n)=3n+2，求g(n)，使得f(n)=Θ(g(n))。解： 當(dāng)n≥2，f(n)=3n+2≤3n+n=4n

當(dāng)n≥1，f(n)=3n+2≥3n

故當(dāng)n≥2，有3n≤f(n)≤4n

令g(n)=n，因?yàn)楫?dāng)n≥2時(shí)有3g(n)≤f(n)≤4g(n)

所以f(n)=Θ(n)解2：令g(n)=n*Θ符號(hào)提供了算法運(yùn)行時(shí)間的精確描述，由于算法InsertionSort的運(yùn)行時(shí)間由線性到平方排列，因此不能用Θ描述。而SelectionSort算法和BottomUpSort算法可分別使用Θ(n2)和Θ(nlog2n)精確描述。

f(n)=Θ(g(n))是一個(gè)等價(jià)關(guān)系，由這個(gè)關(guān)系導(dǎo)出一個(gè)等價(jià)類，稱為復(fù)雜性類。例：f(n)=3n+2、g(n)=n，顯然有f(n)=Θ(g(n))。表示這二個(gè)函數(shù)屬同一復(fù)雜性類。㈤o符號(hào)（讀作小o）由等價(jià)關(guān)系f(n)=Θ(g(n))

導(dǎo)出了一個(gè)等價(jià)類，為了說明二個(gè)函數(shù)屬于不同類，引入了o符號(hào)。f(n)=o(g(n))，當(dāng)且僅當(dāng)f(n)=O(g(n))，但g(n)≠O(f(n))。*定義1.3（Page19）

令f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。如果對(duì)于每一個(gè)常數(shù)c>0，存在一個(gè)自然數(shù)n0，使得

n≥n0

，f(n)<cg(n)則稱f(n)=o(g(n))。

形式地說明了當(dāng)n→∞時(shí)，f(n)對(duì)于g(n)來說可以忽略不計(jì)。f(n)=o(g(n))，當(dāng)且僅當(dāng)f(n)=O(g(n)，但g(n)≠O(f(n))。例如：n是o(n2)的，等價(jià)于n是O(n2)，但n2≠O(n)。*證明當(dāng)n≥？時(shí)有2n＜n!證：由此可得：2n=o(n!)*

我們用f(n)﹤g(n)來表示f(n)是o(g(n))的。用該記號(hào)可簡(jiǎn)明地表示復(fù)雜性的層次。1﹤logn﹤n1/2﹤n﹤nlogn﹤n2﹤n3﹤2n﹤n!O 類似于 ≤Ω 類似于 ≥Θ 類似于 =o 類似于 <

不要將確切的關(guān)系和漸近符號(hào)相混淆。例如：

100n≥n 100n=O(n) n≤100n 100n=Ω(n) n≠100n 100n=Θ(n)

一般地，設(shè)f(n)=aknk+ak-1nk-1+…+a1n+a0，則f(n)=Θ(nk)，它蘊(yùn)含著f(n)=O(nk)，f(n)=Ω(nk)。*驗(yàn)證某數(shù)n是否是素?cái)?shù)算法描述如下：

若均不能除盡，則n為素?cái)?shù)。只要有一個(gè)能除盡，則n為合數(shù)。為了提高效率，上述算法可優(yōu)化如下：

原理：若存在一個(gè)數(shù)x（

≤x＜n），能整除n。設(shè)商為y，則有n=xy，顯然0<y≤

)且y能整除n。顯然檢查了y，就沒有必要再檢查x。*例1.16素?cái)?shù)測(cè)試的蠻力算法算法1.7算法Brute-ForcePrimalityTest輸入：正整數(shù)n≥2輸出：若n是素?cái)?shù)，則輸出true，否則輸出false。1.s←

2.forj←2tosifj劃分sthenreturnfalseendforreturntrue

n的平方根可以在O(1)時(shí)間內(nèi)計(jì)算出。假設(shè)輸入是偶數(shù)，算法僅僅執(zhí)行一次循環(huán)，所以算法是Ω(1)的。若輸入是素?cái)?shù)，執(zhí)行循環(huán)次數(shù)為

，所以該算法是O()的。算法的時(shí)間復(fù)雜性不能用Θ來描述。*1.9空間復(fù)雜性空間復(fù)雜性定義（P19）為了求解問題的實(shí)例，執(zhí)行計(jì)算步驟所需要的內(nèi)存空間的數(shù)目，它不包括分配用來存儲(chǔ)輸入的空間。換句話說，僅僅是算法需要的工作空間。

空間復(fù)雜性的計(jì)算要比時(shí)間復(fù)雜性簡(jiǎn)單得多，可將時(shí)間復(fù)雜性的定義和符號(hào)移植到空間復(fù)雜性的表示。例1，在算法LinearSearch中，僅需要一個(gè)內(nèi)存單元保存搜索結(jié)果以及循環(huán)控制變量i、j，可以得出空間復(fù)雜性為Θ(1)。同理算法BinarySearch、SelectionSort和InsertionSort。*例2：在算法Merge中，需要和輸入大小相同的存儲(chǔ)器n個(gè)，因此空間復(fù)雜性為Θ(n)。同理算法BottomUpSort。例3：輸出n個(gè)字符的所有排列只需要Θ(n)空間。如果需要保留這些排列用于后續(xù)計(jì)算，至少需要n!空間，即Ω

(n!)。許多問題的處理需要在時(shí)間和空間之間平衡。一般來說，給算法分配的空間越大，算法運(yùn)行速度就越快，反之亦然。迄今為止所討論的大多數(shù)算法中，增加空間并不可能導(dǎo)致算法速度的加快，有可能反而降低。但是，減小空間會(huì)導(dǎo)致算法速度的降低是毫無疑問的。*1.10最優(yōu)算法

一般來說，如果可以證明任何一個(gè)求解問題Π的算法必定是Ω(f(n))，那么我們把在O(f(n))時(shí)間內(nèi)求解問題Π的任何算法都稱為問題Π的最優(yōu)算法。任何基于比較的排序算法，可以證明它的運(yùn)行時(shí)間必定是Ω(nlogn)。這就意味著：不能指望找到一個(gè)基于比較的排序算法，它的漸近運(yùn)行時(shí)間少于nlogn。因?yàn)檫@個(gè)理由，我們通常把時(shí)間復(fù)雜性為O(nlogn)的基于比較的排序算法，稱為該問題的最優(yōu)算法。根據(jù)這一定義，算法BottomUpSort是該問題的最優(yōu)算法．我們還稱，算法BottomUpSort在常數(shù)因子范圍內(nèi)是最優(yōu)的，以表示可能存在另一個(gè)基于比較的排序算法，它的運(yùn)行時(shí)間是BottomUpSort算法的執(zhí)行時(shí)間乘以一個(gè)常數(shù)因子。

算法概述661.1 算法與程序算法：是滿足下述性質(zhì)的指令序列。輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。程序：程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。例如操作系統(tǒng)，是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問題，每一個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。671.2 算法與數(shù)據(jù)結(jié)構(gòu)描述算法可以有多種方式自然語言方式、表格方式、圖示形式等本書將采用C++與自然語言相結(jié)合的方式算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系不了解施加于數(shù)據(jù)上的算法就無法決定如何構(gòu)造數(shù)據(jù)，可以說算法是數(shù)據(jù)結(jié)構(gòu)的靈魂；反之算法的結(jié)構(gòu)和選擇又常常在很大程度上依賴于數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)則是算法的基礎(chǔ)。算法＋數(shù)據(jù)結(jié)構(gòu)＝程序681.3 表達(dá)算法的抽象機(jī)制從機(jī)器語言到高級(jí)語言的抽象高級(jí)程序設(shè)計(jì)語言的主要好處是：高級(jí)語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；高級(jí)語言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；高級(jí)語言不依賴于機(jī)器語言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫出來的程序可植性好、重用率高；把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開發(fā)周期短，程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。691.3 表達(dá)算法的抽象機(jī)制抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。抽象數(shù)據(jù)類型帶給算法設(shè)計(jì)的好處有：算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離；算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便于空間和時(shí)間耗費(fèi)的折衷；用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性；算法自然呈現(xiàn)模塊化；為自頂向下逐步求精和模塊化提供有效途徑和工具；算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。701.4 描述算法與算法設(shè)計(jì)描述算法可以有多種方式，如自然語言方式、圖形表格方式等。在這里，我們將采用C++語言來描述算法。C++語言的優(yōu)點(diǎn)是類型豐富、語句精煉，具有面向?qū)ο蠛兔嫦蜻^程的雙重優(yōu)點(diǎn)。用C++來描述算法可使整個(gè)算法結(jié)構(gòu)緊湊、可讀性強(qiáng)。在課程中，有時(shí)為了更好地闡明算法的思路，我們還采用C++與自然語言相結(jié)合的方式來描述算法。算法設(shè)計(jì)方法主要有：分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界、概率算法等，我們將在后面的章節(jié)中陸續(xù)介紹。711.4 描述算法與算法設(shè)計(jì)問題求解(ProblemSolving)72證明正確性分析算法設(shè)計(jì)程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法1.5算法分析的基本原則正確性定義：在給定有效輸入后，算法經(jīng)過有限時(shí)間的計(jì)算并產(chǎn)生正確的答案，就稱算法是正確的。正確性證明的內(nèi)容：方法的正確性證明——算法思路的正確性。證明一系列與算法的工作對(duì)象有關(guān)的引理、定理以及公式。程序的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。程序正確性證明的方法：大型程序的正確性證明——可以將它分解為小的相互獨(dú)立的互不相交的模塊，分別驗(yàn)證。小模塊程序可以使用以下方法驗(yàn)證：數(shù)學(xué)歸納法、軟件形式方法等。731.5算法分析的基本原則工作量——時(shí)間復(fù)雜性分析計(jì)量工作量的標(biāo)準(zhǔn):對(duì)于給定問題，該算法所執(zhí)行的基本運(yùn)算的次數(shù)?；具\(yùn)算的選擇：根據(jù)問題選擇適當(dāng)?shù)幕具\(yùn)算。74問題基本運(yùn)算在表中查找x比較實(shí)矩陣相乘實(shí)數(shù)乘法排序比較遍歷二叉樹置指針1.5算法分析的基本原則占用空間——空間復(fù)雜性分析兩種占用：存儲(chǔ)程序和輸入數(shù)據(jù)的空間存儲(chǔ)中間結(jié)果或操作單元所占用空間——額外空間影響空間的主要因素：存儲(chǔ)程序的空間一般是常數(shù)(和輸入規(guī)模無關(guān))輸入數(shù)據(jù)空間為輸入規(guī)模O(n)空間復(fù)雜性考慮的是額外空間的大小如果額外空間相對(duì)于輸入規(guī)模是常數(shù)，稱為原地工作的算法。751.5算法分析的基本原則簡(jiǎn)單性含義：算法簡(jiǎn)單，程序結(jié)構(gòu)簡(jiǎn)單。好處：容易驗(yàn)證正確性便于程序調(diào)試簡(jiǎn)單的算法效率不一定高。要在保證一定效率的前提下力求得到簡(jiǎn)單的算法。761.5算法分析的基本原則最優(yōu)性含義：指求解某類問題中效率最高的算法兩種最優(yōu)性最壞情況：設(shè)A是解某個(gè)問題的算法，如果在解這個(gè)問題的算法類中沒有其它算法在最壞情況下的時(shí)間復(fù)雜性比A在最壞情況下的時(shí)間復(fù)雜性低，則稱A是解這個(gè)問題在最壞情況下的最優(yōu)算法。平均情況：設(shè)A是解某個(gè)問題的算法，如果在解這個(gè)問題的算法類中沒有其它算法在平均情況下的時(shí)間復(fù)雜性比A在平均情況下的時(shí)間復(fù)雜性低，則稱A是解這個(gè)問題在平均情況下的最優(yōu)算法。尋找最優(yōu)算法的途徑(以最壞情況下的最優(yōu)性為例)設(shè)計(jì)算法A，求W(n)。相當(dāng)于對(duì)問題給出最壞情況下的一個(gè)上界。尋找函數(shù)F(n)，使得對(duì)任何算法都存在一個(gè)規(guī)模為n的輸入并且該算法在這個(gè)輸入下至少要做F(n)次基本運(yùn)算。相當(dāng)于對(duì)問題給出最壞情況下所需基本運(yùn)算次數(shù)的一個(gè)下界。如果W(n)=F(n)，則A是最優(yōu)的。如果W(n)>F(n)，A不是最優(yōu)的或者F(n)的下界過低。改進(jìn)A或設(shè)計(jì)新算法A’使得W’(n)<W(n)。重新證明新下界F’(n)使得F’(n)>F(n)。重復(fù)以上兩步，最終得到W’(n)=F’(n)為止。771.5算法分析的基本原則例：在n個(gè)不同的數(shù)中找最大的數(shù)?；具\(yùn)算：比較算法：FindMax輸入：數(shù)組L，項(xiàng)數(shù)n11輸出：L中的最大項(xiàng)MAXMAX←L(1);i←2;whilei≤ndoifMAX<L(i)thenMAX←L(i);i←i+1;end。行3的比較進(jìn)行n－1次，故W(n)=n－1。定理：在n個(gè)數(shù)的數(shù)組中找最大的數(shù)，并以比較作為基本運(yùn)算的算法類中的任何算法最壞情況下至少要做n－1次比較。證：因?yàn)镸AX是唯一的，其它的n－1個(gè)數(shù)必須在比較后被淘汰。一次比較至多淘汰一個(gè)數(shù)，所以至少需要n－1次比較。結(jié)論：FindMax算法是最優(yōu)算法。781.6 算法復(fù)雜性分析算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，則有：T=T(N,I)和S=S(N,I)。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問題的規(guī)模（輸入大?。?91.6 算法復(fù)雜性分析以上分別是最壞情況下、最好情況下和平均情況下的時(shí)間復(fù)雜性。其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達(dá)到TMax(N)的合法輸入；I-是DN中使T(N,I-)達(dá)到TMin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。801.6 算法復(fù)雜性分析函數(shù)的漸進(jìn)性態(tài)與漸進(jìn)表達(dá)式：一般來說，當(dāng)N單調(diào)增加且趨于∞時(shí)，T(N)也將單調(diào)增加趨于∞。對(duì)于T(N)，如果存在函數(shù)T'(N)，使得當(dāng)N→∞使有(T(N)-T'(N))/T(N)→0，那么我們就說T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)性態(tài)。在數(shù)學(xué)上，T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)表達(dá)式。例如：3N2+4NlogN+7與3N2。811.6 算法復(fù)雜性分析算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、Ω、θ、o、ω設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≤Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則：O(f)+O(g)=O(max(f,g))；O(f)+O(g)=O(f+g)；O(f)O(g)=O(fg)；如果g(N)=O(f(N))，則O(f)+O(g)=O(f)；O(Cf(N))=O(f(N))，其中C是一個(gè)正的常數(shù)；f=O(f)。821.6 算法復(fù)雜性分析Ω的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≥Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是它的一個(gè)下界，記為f(N)=Ω(g(N))。即f(N)的階不低于g(N)的階。θ的定義：定義f(N)=θ(g(N))當(dāng)且僅當(dāng)f(N)=O(g(N))且f(N)=Ω(g(N))。此時(shí)稱f(N)與g(N)同階。o的定義：對(duì)于任意給定的ε＞0，都存在正整數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)/Cg(N)＜ε,則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比g(N)低，記為f(N)=o(g(N))。例如，4NlogN+7=o(3N2+4NlogN+7)。

的定義：

(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有n≥n0有：0≤cg(n)＜f(n)}等價(jià)于f(n)/g(n)

，asn。f(n)

(g(n))

g(n)

o(f(n))831.6 算法復(fù)雜性分析漸近分析記號(hào)的若干性質(zhì)（1）傳遞性：f(n)=θ(g(n))，g(n)=θ(h(n))→f(n)=θ(h(n))；f(n)=Ｏ(g(n))，g(n)=Ｏ(h(n))→f(n)=Ｏ(h(n))；f(n)=Ω(g(n))，g(n)=Ω(h(n))→f(n)=Ω(h(n))；f(n)=ｏ(g(n))，g(n)=ｏ(h(n))→f(n)=ｏ(h(n))；f(n)=ω(g(n))，g(n)=ω(h(n))→f(n)=ω(h(n))；（2）反身性：f(n)=θ(f(n))；f(n)=Ｏ(f(n))；f(n)=Ω(f(n)).（3）對(duì)稱性：f(n)=θ(g(n))<==>g(n)=θ(f(n)).（4）互對(duì)稱性：f(n)=Ｏ(g(n))<==>g(n)=Ω(f(n))；f(n)=ｏ(g(n))<==>g(n)=ω(f(n))；（5）算術(shù)運(yùn)算：Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})；Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n)+g(n))；Ｏ(f(n))*Ｏ(g(n))=Ｏ(f(n)*g(n))；Ｏ(cf(n))=Ｏ(f(n))；g(n)=Ｏ(f(n))→Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n))。841.6 算法復(fù)雜性分析規(guī)則Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的證明：對(duì)于任意f1(n)∈Ｏ(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n≥n1，有f1(n)≤c1f(n)。類似地，對(duì)于任意g1(n)∈Ｏ(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n≥n2，有g(shù)1(n)≤c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的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)＝Ｏ(max{f(n),g(n)}).851.6 算法復(fù)雜性分析取整函數(shù)

x：不大于x的最大整數(shù)；

x：不小于x的最小整數(shù)。取整函數(shù)的若干性質(zhì)x-1<xxx<x+1；

n/2+n/2=n;

對(duì)于n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;其中，f(x)=x,g(x)=x

為單調(diào)遞增函數(shù)。861.6 算法復(fù)雜性分析算法分析中常見的復(fù)雜性函數(shù)871.6 算法復(fù)雜性分析小規(guī)模數(shù)據(jù)復(fù)雜性增長(zhǎng)圖881.6 算法復(fù)雜性分析中等規(guī)模數(shù)據(jù)復(fù)雜性增長(zhǎng)圖89小結(jié)程序與算法漸進(jìn)表達(dá)式程序復(fù)雜性習(xí)題：

90

遞歸與分治策略912.1遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計(jì)算機(jī)算法設(shè)計(jì)與分析中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡(jiǎn)潔且易于理解。下面來看幾個(gè)實(shí)例。922.1遞歸的概念例1階乘函數(shù)可遞歸地定義為：其中：n=0時(shí)，n!=1為邊界條件n>0時(shí)，n!=n(n-1)!為遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。932.1遞歸的概念例2Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，…，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}94小兔子問題2.1遞歸的概念例3Ackerman函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義。但本例中的Ackerman函數(shù)卻無法找到非遞歸的定義。952.1遞歸的概念A(yù)(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)：M=0時(shí)，A(n,0)=n+2M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2^n。M=3時(shí)，類似的可以推出M=4時(shí)，A(n,4)的增長(zhǎng)速度非?？?，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。定義其擬逆函數(shù)α(n)為：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在復(fù)雜度分析中常遇到。對(duì)于通常所見到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。962.1遞歸的概念例4排列問題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構(gòu)成。972.1遞歸的概念例5整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。例如正整數(shù)6有如下11種不同的劃分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。982.1遞歸的概念前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系：q(n,1)=1，n≥1；當(dāng)最大數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式：n=1+1+...+1(共n個(gè))。Q(n,m)=q(n,n)，m≥n；最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。q(n,n)=1+q(n,n-1)；正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。q(n,m)=q(n,m-1)+q(n-m,m),n>m>1；正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤m-1的劃分組成。992.1遞歸的概念正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。1002.1遞歸的概念例6Hanoi塔問題設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：每次只能移動(dòng)1個(gè)圓盤；任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。publicstaticvoidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}思考：如果塔的個(gè)數(shù)變?yōu)閍,b,c,d四個(gè)，現(xiàn)要將n個(gè)圓盤從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。1012.1遞歸的概念遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。用遞推來實(shí)現(xiàn)遞歸函數(shù)。通過Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。1022.2分治法的基本思想分治法的基本思想分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。103凡治眾如治寡，分?jǐn)?shù)是也?！獙O子兵法2.2分治法的基本思想104nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n