算法设计与分析课件

演算法分析基本概念

*1.1 引言DonaldE.Knuth電腦科學就是演算法研究例，編譯程序和操作系統是具有特定目標的演算法的直接實現。**演算法（Algorithm） 解题方案的准确完整的描述，是在有限步骤内求解某一问题所使用的一组定义明确的规则。①無論是解題思路還是編寫程式，都是在實施某種演算法。前者是推理實現，後者是操作實現。②演算法不是程式，但演算法是用程式或程式偽代碼來描述的。演算法分析（AlgorithmAnalysis）演算法分析是研究演算法一旦轉換成某種語言的程式，該程式在電腦上運行需要多少時間和存儲空間，才能完成解題方案。*

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

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

A[mid+1]，A[mid+2]，…，A[high]中的一個，接下來只需在A[mid+1..high]中搜索x。換句話說，A[low..mid]中的專案在後續比較中被掉棄了。類似地，如果x<A[mid]，只需在A[low..mid-1]中搜索x。由於重複進行二等分，導致了一個稱為二分搜索的有效策略。*演算法1.2BinarySearch（Page4）輸入：n個元素的數組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考慮搜索數組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)計為一次比較，顯然最小比較次數為1，即搜索元素x在序列中間位置。為了計算最大比較次數，不失一般性，可假定x≥A[high]。①第2次迭代前（即第1次迭代結束後）數組A中剩餘元素 若n是偶數，A[(mid+1)..n]共有n/2個元素。 若n是奇數，A[(mid+1)..n]共有(n-1)/2個元素。二種情況都有：A[mid+1..n]=

n/2

=

n/22-1

②第3次迭代前數組A中剩餘元素

n/2

/2

=

n/4

=

n/22

=

n/23-1

③第j次迭代前數組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

)。

當

n/2j-1

=1，j為最大迭代次數（最大循環次數、最大比較次數）

n/2j-1

=1等價於1≤n/2j-1<2等價於2j-1≤n<2j等價於（取對數）j-1≤Log2n<j考慮

Log2n

≤Log2n<

Log2n

+1因為j是整數，故有j-1=

Log2n

或j=

Log2n

+1二者均有j=

Log2n

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

可將二分搜索法的执行描述为决策树，红色的结点是与x=22相比較的數字。

14578912152223273235

定理1.1（Page6）對於一個大小為n的已排序數組，演算法BinarySearch執行比較的最大次數為:

Log2n

+1*注：由於if-then-else嵌套使用，最大比較次數實質上應為迭代次數2倍，即2(

Log2n

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

Log2n

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

決策樹的高度為

Log2n

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

Log2n

+1。1.4合併二個已排序的表㈠演算法描述

假定有一個數組A[1..m]，p，q，r是它的三個索引，並有1≤p≤q<r≤m，二個子數組A[p..q]和A[q+1..r]各自按昇冪排列，重新排列A中元素的位置，使得子數組A[p..r]按昇冪排列。①使用二個指針s和t，初始化時s=p、t=q+1，s和t各自指向A[p]和A[q+1]，空數組B[p..r]用作暫存器。②每一次比較元素A[s]和A[t]，將小的元素添加到B中。然後更新指針，若A[s]≤A[t]，則s加1，否則t加1。③當s=q+1，說明子數組A[p..q]的全部元素已進入B，無需再比較，此時把子數組餘下部分A[t..r]添加到B中。④當t=r+1，說明子數組A[q+1..r]的全部元素已進入B，無需再比較，此時把子數組餘下部分A[s..q]添加到B中。⑤最後將B[p..r]複製到A[p..r]。*過程1.3Merge（Page6）輸入：數組A[1..m]和它的三個索引p，q，r，1≤p≤q<r≤m，二個子數組A[p..q]和A[q+1..r]各自按昇冪排列。輸出：子數組A[p..r]按昇冪排列。0.procedureMerge(A[1..m],p,q,r)1. comment:B[p..r]是个辅助数组 //或B[1..m]2. s←p:t←q+1:k←p //s和t分別指向數組A二個子數組元素3. while(s≤q)and(t≤r) //k指向數組B當前空白元素位置4. ifA[s]≤A[t]thenB[k]←A[s]:s←s+15. elseB[k]←A[t]:t←t+16. endif7. k←k+1 //指向數組B下一個空白位置8. endwhile9. ifs=q+1thenB[k..r]←A[t..r]//說明子數組A[p..q]元素已處理完10. elseB[k..r]←A[s..q]//否則t=r+1，說明子數組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]是个辅助数组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]*㈡算法分析設有個數分別為n1和n2的二個子數組n1+n2=n，如果子數組A[p..q]中每个元素均小于另一个子数组A[q+1,r]中的所有元素，例，要合併下麵二個子數組：236711134557

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

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

n/2

和

n/2

，需要比較的最大次數在

n/2

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

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

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

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

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

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

①找到一個小於等於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 *㈡插入排序算法

設A[1..n]為n個元素的數組，插入排序演算法描述如下：

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

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

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

④直到A[n]插入到A[1..n-1]中為止。演算法1.6InsertionSort(参见9)輸入：數組A[1..n]輸出：按昇冪排列的數組A[1..n]1. fori←2ton2. Insertion(i)endfor *㈢插入排序算法分析執行InsertionSort，元素比較次數取決於輸入元素的順序。①當序列已按昇冪排列時，元素比較次數最小，僅為n-1，每個元素A[i]（2≤i≤n）只和A[i-1]比較。②當元素已按降序排列，並且所有元素各不相同，比較次數為最大。如下所示：

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

Seletion(i)

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

Insertion(i)

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

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

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

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

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

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

當n不是2的整數冪時，自底向上合併排序的過程如下所示：*第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時，i+t≤11不成立，出迴圈。出迴圈後，i+s=10+1＜n=11不成立，因此不再合併，最後一個序列長度為1（或稱剩下的元素個數）。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長度（即合併前）t表示合併後序列的長度（初值為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時，i+t≤11不成立，出迴圈。出迴圈後，i+s=8+2＜n=11成立，執行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值的範圍：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值的範圍：0 i=0時，i+t≤11不成立，出迴圈。出迴圈後，i+s=0+8＜n=11成立，執行MERGE(A,1,8,11)。MERGE(A,i+1,i+s,i+t)s表示被合併序列的長度（即合併前）t表示合併後序列的長度（初值為1）i表示位移34568910111271234567891011第5次迭代：t=16＜n=11不成立，終止執行。*演算法1.6BottomUpSort（省略變數t）輸入：n個元素的數組A[1..n]輸出：按昇冪排列的數組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*㈣自底向上合併排序演算法分析

假設數組元素個數n為2的冪，外部迴圈次數為k=log2n。在執行內部迴圈後，由於n為2的冪，故第8步永遠不會執行。①在第1次迭代中，共執行了n/2次比較。n個元素被劃分為n/2個段（段長=2），段內有序。②在第2次迭代中，n/2個段（段長=2）元素序列被合併成n/4個段（段長=4），段內有序。根據觀察結論1.1（Page7），每對合併需要的比較次數，最少為2，最多為3。③在第3次迭代中，n/4個段（段長=4）元素序列被合併成n/8個段（段長=8），段內有序。根據觀察結論1.1（Page7），每對合併需要的比較次數，最少是4，最多7。*最少比較次數（k=log2n）④在第j次迭代中，個段（段長=2j-1）元素序列被合併成個段（段長=2j），段內有序。根據觀察結論1.1（Page7），每對合併需要的比較次數，最少是2j-1，最多為2j-1。*最多比較次數(k=log2n)（共k項）*觀察結論1.5（Page11)

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

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

假設一次比較所需的時間為10-6秒，當數據個數n分別為27=128和220=1048576時，二個演算法執行所耗費的時間上限如下表所示：*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秒來運行”是沒有意義的，也是沒有必要的。因為影響一個演算法的實際運行時間與諸多因素有關（例機器性能、語言選擇、編譯程序優劣、程式員素質等），甚至無需計算出演算法運行時間的近似數，理由：①演算法分析通常是將解決同一問題的各種演算法進行相互比較，執行時間是相對的，而不是絕對的。②演算法可以用各種語言來表示，甚至使用人類語言。③演算法應獨立於機器，無論科技如何進步，對演算法運行時間的評估始終成立。④演算法分析不拘泥小規模數據的輸入，主要關心在大的輸入實例時，演算法運行狀況。例某一演算法運行時間為2n3，當n變得很大時，常數2將不起作用。觀察函數n2log2n+10n2+n

中的低階項10n2和n

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

線性函數： n

次平方函數：nlog2n（簡記為nlogn)

平方函數： n2

立方函數： n3

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

n≥n0

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

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

令g(n)=n，當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： 當n≥2，有f(n)≤10n2+4n+n=10n2+5n

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

令g(n)=n2，因為當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))。解： 當n≥4，有n2≤2n

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

令g(n)=2n，因為當n≥4時有f(n)≤7g(n)

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

n≥n0

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

若極限是一個正常數，說明函數f(n)的增長速度和函數g(n)相差整數倍，基本為同一級別；若極限為∞，說明隨著n的增大，函數f(n)增長的速度要比g(n)快得多。可以是正常數或∞*例1：f(n)=3n+2，求g(n)，使得f(n)=Ω(g(n))。解： 當n>0，f(n)=3n+2≥3n。 令g(n)=n，因為當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*在常數因數範圍內，O符號提供了運行時間上界，而Ω符號提供了運行時間下界。稱演算法InsertionSort的元素比較次數至少是cn（=n-1

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

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

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

f(n)=Ω(g(n))，当且仅当g(n)=O(f(n))*㈣Θ符號（讀作theta）定義1.4（Page16）令f(n)和g(n)是從自然數集到非負實數集的二個函數。如果存在一個自然數n0和二個正常數c1和c2，使得

n≥n0

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

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

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

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

令g(n)=n，因為當n≥2時有3g(n)≤f(n)≤4g(n)

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

f(n)=Θ(g(n))是一個等價關係，由這個關係導出一個等價類，稱為複雜性類。例：f(n)=3n+2、g(n)=n，顯然有f(n)=Θ(g(n))。表示這二個函數屬同一複雜性類。㈤o符號（讀作小o）由等價關係f(n)=Θ(g(n))

導出了一個等價類，為了說明二個函數屬於不同類，引入了o符號。f(n)=o(g(n))，当且仅当f(n)=O(g(n))，但g(n)≠O(f(n))。*定義1.3（Page19）

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

n≥n0

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

形式地說明了當n→∞時，f(n)對於g(n)來說可以忽略不計。f(n)=o(g(n))，当且仅当f(n)=O(g(n)，但g(n)≠O(f(n))。例如：n是o(n2)的，等價於n是O(n2)，但n2≠O(n)。*證明當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 類似於 <

不要將確切的關係和漸近符號相混淆。例如：

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

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

若均不能除盡，則n為素數。只要有一個能除盡，則n為合數。為了提高效率，上述演算法可優化如下：

原理：若存在一個數x（

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

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

2.forj←2tosifj劃分sthenreturnfalseendforreturntrue

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

，所以該演算法是O()的。演算法的時間複雜性不能用Θ來描述。*1.9空間複雜性空間複雜性定義（P19）为了求解问题的实例，执行计算步骤所需要的内存空间的数目，它不包括分配用来存储输入的空间。换句话说，仅仅是算法需要的工作空间。

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

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

一般來說，如果可以證明任何一個求解問題Π的演算法必定是Ω(f(n))，那么我们把在O(f(n))時間內求解問題Π的任何演算法都稱為問題Π的最優演算法。任何基於比較的排序演算法，可以證明它的運行時間必定是Ω(nlogn)。这就意味着：不能指望找到一个基于比较的排序算法，它的渐近运行时间少于nlogn。因為這個理由，我們通常把時間複雜性為O(nlogn)的基於比較的排序演算法，稱為該問題的最優演算法。根據這一定義，演算法BottomUpSort是該問題的最優演算法．我們還稱，演算法BottomUpSort在常數因數範圍內是最優的，以表示可能存在另一個基於比較的排序演算法，它的運行時間是BottomUpSort演算法的執行時間乘以一個常數因數。

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

的定義：

(g(n))={f(n)|對於任何正常數c>0，存在正數和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 演算法複雜性分析漸近分析記號的若干性質（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）對稱性：f(n)=θ(g(n))<==>g(n)=θ(f(n)).（4）互對稱性：f(n)=Ｏ(g(n))<==>g(n)=Ω(f(n))；f(n)=ｏ(g(n))<==>g(n)=ω(f(n))；（5）算術運算：Ｏ(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(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的證明：對於任意f1(n)∈Ｏ(f(n))，存在正常數c1和自然數n1，使得對所有n≥n1，有f1(n)≤c1f(n)。類似地，對於任意g1(n)∈Ｏ(g(n))，存在正常數c2和自然數n2，使得對所有n≥n2，有g1(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)＝Ｏ(max{f(n),g(n)}).851.6 演算法複雜性分析取整函數

x：不大於x的最大整數；

x：不小於x的最小整數。取整函數的若干性質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

為單調遞增函數。861.6 演算法複雜性分析演算法分析中常見的複雜性函數871.6 演算法複雜性分析小規模數據複雜性增長圖881.6 演算法複雜性分析中等規模數據複雜性增長圖89小結程式與演算法漸進運算式程式複雜性習題：

90

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