算法設(shè)計與分析課件_第1頁
算法設(shè)計與分析課件_第2頁
算法設(shè)計與分析課件_第3頁
算法設(shè)計與分析課件_第4頁
算法設(shè)計與分析課件_第5頁
已閱讀5頁,還剩556頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

演算法分析基本概念

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

確定一個程式的運行效率,可使用數(shù)學(xué)分析方法,也可使用實驗測試方法,以期在理論和實踐作出評價。1.2 歷史背景20世紀(jì)早期,能否用一種有效的過程(演算法)來求解問題受到廣泛關(guān)注,人們的注意力是放在問題的可解和不可解的分類上。問題的可判定性和可解性的研究領(lǐng)域稱為“可計算理論”。數(shù)字電腦出現(xiàn)以後,由於有限的資源,提出了盡可能少用資源的有效演算法的需求,導(dǎo)致出現(xiàn)計算複雜性的新領(lǐng)域。“計算複雜性”是研究可解類問題的效率,所謂效率是指解決問題所需的時間和空間。*1.3 二分搜索㈠順序搜索(線性搜索) 問題:設(shè)A[1..n]為一個n個元素(整數(shù))的數(shù)組,判定給定元素x是否在A中。演算法:掃描A的所有專案,將每個專案與x比較,如果在第j次比較後(1≤j≤n)搜索成功,即x=A[j],則返回j值;否則返回0,表示沒有找到。這種方法稱為順序搜索。*演算法1.1LinearSearch(Page3)輸入:n個元素的數(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*出迴圈分析:

①x=A[j],此時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]中的一個,接下來只需在A[mid+1..high]中搜索x。換句話說,A[low..mid]中的專案在後續(xù)比較中被掉棄了。類似地,如果x<A[mid],只需在A[low..mid-1]中搜索x。由於重複進行二等分,導(dǎo)致了一個稱為二分搜索的有效策略。*演算法1.2BinarySearch(Page4)輸入:n個元素的數(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]掉棄。④留在序列中僅剩一個項目A[10]=22,最後找到x=A[10],搜索成功完畢(若x≠A[10],則low≤high條件不成立,出迴圈)。10121522A[8..10]=89 10*㈣二分搜索法分析假定每個三向比較(if-then-else)計為一次比較,顯然最小比較次數(shù)為1,即搜索元素x在序列中間位置。為了計算最大比較次數(shù),不失一般性,可假定x≥A[high]。①第2次迭代前(即第1次迭代結(jié)束後)數(shù)組A中剩餘元素 若n是偶數(shù),A[(mid+1)..n]共有n/2個元素。 若n是奇數(shù),A[(mid+1)..n]共有(n-1)/2個元素。二種情況都有: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個,即

n/2j-1

=1n=10,mid=

(10+1)/2

=5,剩餘元素A[6..10],共計5個(

10/2

)。n=11,mid=

(11+1)/2

=6,剩餘元素A[7..11],共計5個(

11/2

)。

當(dāng)

n/2j-1

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

n/2j-1

=1等價於1≤n/2j-1<2等價於2j-1≤n<2j等價於(取對數(shù))j-1≤Log2n<j考慮

Log2n

≤Log2n<

Log2n

+1因為j是整數(shù),故有j-1=

Log2n

或j=

Log2n

+1二者均有j=

Log2n

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

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

14578912152223273235

定理1.1(Page6)對於一個大小為n的已排序數(shù)組,演算法BinarySearch執(zhí)行比較的最大次數(shù)為:

Log2n

+1*注:由於if-then-else嵌套使用,最大比較次數(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合併二個已排序的表㈠演算法描述

假定有一個數(shù)組A[1..m],p,q,r是它的三個索引,並有1≤p≤q<r≤m,二個子數(shù)組A[p..q]和A[q+1..r]各自按昇冪排列,重新排列A中元素的位置,使得子數(shù)組A[p..r]按昇冪排列。①使用二個指針s和t,初始化時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]的全部元素已進入B,無需再比較,此時把子數(shù)組餘下部分A[t..r]添加到B中。④當(dāng)t=r+1,說明子數(shù)組A[q+1..r]的全部元素已進入B,無需再比較,此時把子數(shù)組餘下部分A[s..q]添加到B中。⑤最後將B[p..r]複製到A[p..r]。*過程1.3Merge(Page6)輸入:數(shù)組A[1..m]和它的三個索引p,q,r,1≤p≤q<r≤m,二個子數(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]是個輔助數(shù)組 //或B[1..m]2. s←p:t←q+1:k←p //s和t分別指向數(shù)組A二個子數(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下一個空白位置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] //複製13.endprocedure**2316711134557qrkt0.procedureMerge(A[1..m],p,q,r)1. comment:B[p..r]是個輔助數(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è)有個數(shù)分別為n1和n2的二個子數(shù)組n1+n2=n,如果子數(shù)組A[p..q]中每個元素均小于另一個子數(shù)組A[q+1,r]中的所有元素,例,要合併下麵二個子數(shù)組:236711134557

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

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

n/2

n/2

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

n/2

和n-1之間。觀察結(jié)論1.2(Page7)執(zhí)行算法Merge,將個數(shù)分別為n1和n2的非空數(shù)組合並成一個為n=n1+n2的排序數(shù)組,元素的賦值次數(shù)恰好是2n。1.5 選擇排序法㈠選擇演算法假定有一個數(shù)組A[1..n],A[i..n]是它的一個子數(shù)組,1≤i<n。編寫一函數(shù),作用為:從A[i..n]中選擇一個最小的數(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個元素的數(shù)組,選擇排序演算法如下:

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

②然後在剩下的n-1個元素中找到最小元素,將其存放在A[2]中。

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

這個演算法執(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插入排序㈠插入演算法假定有一個數(shù)組A[1..n],A[1..i]是它的一個子數(shù)組,1<i≤n。A[1..i-1]已按昇冪排列。編寫一函數(shù),作用為:將x=A[i]插入到子數(shù)組A[1..i-1]中,使得A[1..i]按昇冪排列。依次掃描序號從j=i-1到j(luò)=1的元素,將x和A[j]比較。在掃描的每一步,元素都被移到序號更高的一個位置上,這種過程直到以下情況出現(xiàn)時終止:

①找到一個小於等於A[i]的元素A[j] ②元素A[1]已掃描過此時可將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個元素的數(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ù)最小,僅為n-1,每個元素A[i](2≤i≤n)只和A[i-1]比較。②當(dāng)元素已按降序排列,並且所有元素各不相同,比較次數(shù)為最大。如下所示:

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

Seletion(i)

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

Insertion(i)

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

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

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

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

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

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

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

s=1,t=2i值的範(fàn)圍: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時,i+t≤11不成立,出迴圈。出迴圈後,i+s=10+1<n=11不成立,因此不再合併,最後一個序列長度為1(或稱剩下的元素個數(shù))。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長度(即合併前)t表示合併後序列的長度(初值為1)i表示位移61095311481276105931148127*第2次迭代:t=2<n=11成立

s=2,t=4i值的範(fàn)圍:0,4,8 i=0 MERGE(A,1,2,4) i=4 MERGE(A,5,6,8) i=8時,i+t≤11不成立,出迴圈。出迴圈後,i+s=8+2<n=11成立,執(zhí)行MERGE(A,9,10,11),最後一個序列長度為3。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長度(即合併前)t表示合併後序列的長度(初值為1)i表示位移61059311481275691034811127*第3次迭代:t=4<n=11成立

s=4,t=8i值的範(fàn)圍:0,8 i=0 MERGE(A,1,4,8) i=8時,i+t≤11不成立,出迴圈。出迴圈後,i+s=8+4<n=11不成立,因此不再合併,最後一個序列長度為3。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長度(即合併前)t表示合併後序列的長度(初值為1)i表示位移56910348111273456891011127*第4次迭代:t=8<n=11成立

s=8,t=16i值的範(fàn)圍:0 i=0時,i+t≤11不成立,出迴圈。出迴圈後,i+s=0+8<n=11成立,執(zhí)行MERGE(A,1,8,11)。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長度(即合併前)t表示合併後序列的長度(初值為1)i表示位移34568910111271234567891011第5次迭代:t=16<n=11不成立,終止執(zhí)行。*演算法1.6BottomUpSort(省略變數(shù)t)輸入:n個元素的數(shù)組A[1..n]輸出:按昇冪排列的數(shù)組A[1..]1. s←1 //s表示被合併序列的長度(即合併前)

2. whiles<n //2s表示合併後序列的長度(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ù)組元素個數(shù)n為2的冪,外部迴圈次數(shù)為k=log2n。在執(zhí)行內(nèi)部迴圈後,由於n為2的冪,故第8步永遠(yuǎn)不會執(zhí)行。①在第1次迭代中,共執(zhí)行了n/2次比較。n個元素被劃分為n/2個段(段長=2),段內(nèi)有序。②在第2次迭代中,n/2個段(段長=2)元素序列被合併成n/4個段(段長=4),段內(nèi)有序。根據(jù)觀察結(jié)論1.1(Page7),每對合併需要的比較次數(shù),最少為2,最多為3。③在第3次迭代中,n/4個段(段長=4)元素序列被合併成n/8個段(段長=8),段內(nèi)有序。根據(jù)觀察結(jié)論1.1(Page7),每對合併需要的比較次數(shù),最少是4,最多7。*最少比較次數(shù)(k=log2n)④在第j次迭代中,個段(段長=2j-1)元素序列被合併成個段(段長=2j),段內(nèi)有序。根據(jù)觀察結(jié)論1.1(Page7),每對合併需要的比較次數(shù),最少是2j-1,最多為2j-1。*最多比較次數(shù)(k=log2n)(共k項)*觀察結(jié)論1.5(Page11)

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

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

假設(shè)一次比較所需的時間為10-6秒,當(dāng)數(shù)據(jù)個數(shù)n分別為27=128和220=1048576時,二個演算法執(zhí)行所耗費的時間上限如下表所示:*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秒㈠概述

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

中的低階項10n2和n

,當(dāng)n值越大,10n2+n對函數(shù)值的影響就越小。**①漸近運行時間去除表示演算法運行時間函數(shù)的低價項和首項係數(shù)(常數(shù))。②時間複雜性在演算法分析中通常是用漸近運行時間來度量一個演算法,漸近運行時間通常稱為時間複雜性。③演算法分析中的漸近符號有:O、Ω、Θ、o。④表示時間複雜性的常用函數(shù)有: 常數(shù): 1 運行時間為恒定值,和輸入無關(guān)。 次線性函數(shù):log2n(簡記為logn)

線性函數(shù): n

次平方函數(shù):nlog2n(簡記為nlogn)

平方函數(shù): n2

立方函數(shù): n3

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

n≥n0

,f(n)≤cg(n)則稱f(n)=O(g(n)),n0稱為閾值。㈡O符號(讀作大O)

若極限為非0正常數(shù),則函數(shù)f(n)和g(n)增長速度至多相差常數(shù)倍,或稱為同一級別;若極限為0,說明隨著n的增大,函數(shù)f(n)的增長要比g(n)的增長慢得多。正常數(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時有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,因為當(dāng)n≥5時有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,因為當(dāng)n≥4時有f(n)≤7g(n)

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

n≥n0

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

若極限是一個正常數(shù),說明函數(shù)f(n)的增長速度和函數(shù)g(n)相差整數(shù)倍,基本為同一級別;若極限為∞,說明隨著n的增大,函數(shù)f(n)增長的速度要比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,因為當(dāng)n>0時有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ù)因數(shù)範(fàn)圍內(nèi),O符號提供了運行時間上界,而Ω符號提供了運行時間下界。稱演算法InsertionSort的元素比較次數(shù)至少是cn(=n-1

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

n),是指無法設(shè)計出一個新的基於比較的排序演算法,它的時間複雜性小於nlog

n。Ω符號定義的一個重要推論:

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

n≥n0

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

極限是一個正常數(shù),說明函數(shù)f(n)的增長速度和函數(shù)g(n)的增長速度相差整數(shù)倍,基本為同一級別。*例: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,因為當(dāng)n≥2時有3g(n)≤f(n)≤4g(n)

所以f(n)=Θ(n)解2:令g(n)=n*Θ符號提供了演算法運行時間的精確描述,由於演算法InsertionSort的運行時間由線性到平方排列,因此不能用Θ描述。而SelectionSort演算法和BottomUpSort演算法可分別使用Θ(n2)和Θ(nlog2n)精確描述。

f(n)=Θ(g(n))是一個等價關(guān)係,由這個關(guān)係導(dǎo)出一個等價類,稱為複雜性類。例:f(n)=3n+2、g(n)=n,顯然有f(n)=Θ(g(n))。表示這二個函數(shù)屬同一複雜性類。㈤o符號(讀作小o)由等價關(guān)係f(n)=Θ(g(n))

導(dǎo)出了一個等價類,為了說明二個函數(shù)屬於不同類,引入了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ù)。如果對於每一個常數(shù)c>0,存在一個自然數(shù)n0,使得

n≥n0

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

形式地說明了當(dāng)n→∞時,f(n)對於g(n)來說可以忽略不計。f(n)=o(g(n)),當(dāng)且僅當(dāng)f(n)=O(g(n),但g(n)≠O(f(n))。例如:n是o(n2)的,等價於n是O(n2),但n2≠O(n)。*證明當(dāng)n≥?時有2n<n!證:由此可得:2n=o(n!)*

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

不要將確切的關(guān)係和漸近符號相混淆。例如:

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),它蘊含著f(n)=O(nk),f(n)=Ω(nk)。*驗證某數(shù)n是否是素數(shù)演算法描述如下:

若均不能除盡,則n為素數(shù)。只要有一個能除盡,則n為合數(shù)。為了提高效率,上述演算法可優(yōu)化如下:

原理:若存在一個數(shù)x(

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

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

2.forj←2tosifj劃分sthenreturnfalseendforreturntrue

n的平方根可以在O(1)時間內(nèi)計算出。假設(shè)輸入是偶數(shù),演算法僅僅執(zhí)行一次迴圈,所以演算法是Ω(1)的。若輸入是素數(shù),執(zhí)行迴圈次數(shù)為

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

空間複雜性的計算要比時間複雜性簡單得多,可將時間複雜性的定義和符號移植到空間複雜性的表示。例1,在演算法LinearSearch中,僅需要一個記憶體單元保存搜索結(jié)果以及迴圈控制變數(shù)i、j,可以得出空間複雜性為Θ(1)。同理演算法BinarySearch、SelectionSort和InsertionSort。*例2:在演算法Merge中,需要和輸入大小相同的記憶體n個,因此空間複雜性為Θ(n)。同理演算法BottomUpSort。例3:輸出n個字元的所有排列只需要Θ(n)空間。如果需要保留這些排列用於後續(xù)計算,至少需要n!空間,即Ω

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

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

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

的定義:

(g(n))={f(n)|對於任何正常數(shù)c>0,存在正數(shù)和n0>0使得對所有n≥n0有:0≤cg(n)<f(n)}等價於f(n)/g(n)

,asn。f(n)

(g(n))

g(n)

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

x:不大於x的最大整數(shù);

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

n/2+n/2=n;

對於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 演算法複雜性分析演算法分析中常見的複雜性函數(shù)871.6 演算法複雜性分析小規(guī)模數(shù)據(jù)複雜性增長圖881.6 演算法複雜性分析中等規(guī)模數(shù)據(jù)複雜性增長圖89小結(jié)程式與演算法漸進運算式程式複雜性習(xí)題:

90

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論