1、2022-3-4算法設計與分析演示稿 紀玉波制作(C)1算法設計與分析算法設計與分析算法分析舉例算法分析舉例2022-3-4算法設計與分析演示稿 紀玉波制作(C)2算法分析舉例算法分析舉例 本節舉幾個對具體算法進行分析的例子，可以由此學習分析的方法，舉一反三再分析其它的算法。2022-3-4算法設計與分析演示稿 紀玉波制作(C)3例1. 堆陣排序1堆陣 堆陣排序（Heap sort, 1964年Robert W. Floyd 和J.Williams共同設計，1978年Robert W. Floyd獲圖靈獎）是利用二叉樹的一種排序方法。堆(Heap)也譯為堆或堆壘,是與二叉排序樹不同的一種二叉樹

2、，它的定義為：一個完全二叉樹(完全二叉樹：各層都是滿的，只是最下面一層從右邊起連續缺幾個結點)，它的每個結點對應于原始數據的一個元素，且規定：如果一個結點有子結點，此結點數據必須大于或等于其子結點的數據。由此可見，堆是完全二叉樹，且規定了父結點和子結點數據之間必須滿足的條件。 2022-3-4算法設計與分析演示稿 紀玉波制作(C)4 由于堆陣是完全二叉樹，采用將結點順序編號存于一維數組中的表示法較鏈接表示法節省存儲也便于運算。設某堆的結點數共有n個，順序將它們存人一維數組K中，下標從1到n。根據順序表示二叉樹的特點，除下標為1的結點是整個樹的根結點而沒有父結點以外，其余下標為j的結點（2jn）

3、都有父結點，父結點的下標為i= 。故堆陣的條件可以表示成: KiKj 當2jn 和i= 由堆的定義可知，其根結點（即在數組中下標為1的結點）具有最大的數值，堆陣排序就是利用這一特點進行的。堆陣排序過程分為構成堆和利用它來排序兩個階段，下面分別進行介紹。2/ j2/ j2022-3-4算法設計與分析演示稿 紀玉波制作(C)52構成堆陣的過程 可以采用兩種方法構成堆陣。第一種方法是從根結點起逐個插入結點，在插入結點過程中進行父子結點數據比較和必要的互換調整，使之總滿足堆的條件；第二種方法則是先把所有數據按任意次序置入完全二叉樹的各結點中，然后由下而上逐層進行父子結點數據比較，進行必要的互換調整，直

4、至使其最后完全滿足堆的條件，數據的比較調整可以使用“篩”運算進行。篩運算從最末尾結點（下標為n）的父結點（下標為 ）開始，向前逐結點進行，直至篩完根結點即形成此堆陣。篩每個結點時，將其數值與其兩個子結點中數值較大者進行比較，如小于子結點數值，則與之進行互換，互換后又將它看成父結點，再與下一層的子結點進行比較，如此做下去，直至不小于其子結點的數值或已篩到端結點而不再有子結點了，此數據的篩運算即完成。2/n2022-3-4算法設計與分析演示稿 紀玉波制作(C)63利用堆陣排序 由于在一個堆中根結點數據總是所有數據中之最大者，利用堆陣排序的方法是從根結點逐個取出數據，每次將新的元素再提到根結點，如此

5、反復進行。為了節約存儲，要求排序得到的有序數據序列仍存放于原數組中，故將從根結點取出的數據由數組的末端起逐單元存放。每存放一個數據，同時將原在該單元的數據換到根結點，但這樣互換后一般會破壞堆的條件，為此，需對根結點再做一次篩運算，就又可形成新的滿足條件的堆。隨著數組末端存放的由堆中取出的數據越來越多，堆的結點數逐漸減少，當到取出了(n-1)個數據，堆陣只剩下一個根結點，此最后一個數據一定是全部數據中的最小者，堆陣排序過程即全部結束。2022-3-4算法設計與分析演示稿 紀玉波制作(C)7 4時間復雜性分析 堆陣排序分為建立堆陣和利用堆陣排序兩大步驟。設堆陣有r個滿層，元素個數n=2r-1。最壞

6、的情況假設每個元素都需要從原來位置篩到堆陣的最底層，僅原來在最底層的不必篩，這樣一來最上層的一個元素要下降r-1層；第二層的兩個元素要下降r-2層；中間第i層2(i-1)個元素要下降r- I層；下面倒數第一層，也即第r-1層的2(r-2)個元素下降一層。每篩下一層要進行兩次比較（先左右兩子節點相比，然后此元素與其中較大者比）。因此在最壞的情況下，為了建立堆陣所需要的比較次數為：) 1 (2) 3(4)2(2) 1( 1 (2)(2211)2() 1(ririrrrir2022-3-4算法設計與分析演示稿 紀玉波制作(C)8 (上式中共有(r-1)項，第一項包括(r-1)個 1，第二項包括(r-

7、2)個 2， 第二項包括(r-3)個 3，最后一項是一個 2(r-2),將它們重新組 合后可得下式) )2421 ()421 ()21 ()1(2)2( r 2020)1(2) 12(2)2221 (2rkrkkk )1(2222(2)1(32rr )1()22(2rr （ 因10212rkkr） ) 1) 1(log(2) 1(2nn （因12rn） nnn2) 1log(22 （當n較大時）2022-3-4算法設計與分析演示稿 紀玉波制作(C)9 下面看利用堆陣排序所需要的比較次數。排序時由后向前順次將元素與根結點對換，并將換到根結點的元素篩到合適的位置處，如果逐個進行，堆陣越來越小，直至

8、排序完畢。設在某一步堆陣有i個元素，其深度為 ，最壞情況將根元素篩到堆陣最下層需要比較次為 ，故最壞情況排序過程的總比較次數為：1log i 11log2nii 因13log2log，27log6log5log4log ,315log9log8log當 n 恰 為 2 的 整 數 次 方 時 ， 上 述 合 式 為 ： 1log1112lognjjniji（ 例 如 n=16 時 ， 上 式 為 （ 1 2+2 4+3 8） =312jjj）ilog22022-3-4算法設計與分析演示稿 紀玉波制作(C)10若n不恰為2的整數次方時，則后面幾項表成： )2(loglognn（例如n=19時，比

9、n=16多出三項，每項均為419log，恰好是4（19-24）=43=12）因為 112012011112011111112222) 1(2)22(2kjkjjkjjjkjkjjjkjjjkjjjjjjjj 222222) 1() 12( 22) 1(11kkkkkkkkk故排序總的比較次數為： ) 22log(2)2(log222log(21loglog1loglognnnnnnnnn nnn2log2 （當n較大時） （+2 n，建立堆棧的比較次數）2022-3-4算法設計與分析演示稿 紀玉波制作(C)11 因此堆陣排序總的比較次數當n較大時最壞情況為2nlogn(其復雜性為O(nlogn

10、)，為排序問題下界的兩倍。雖然此排序算法時間上不是最優，但它是“就地”進行運算，也不需要指示字分量，故所占空間比較節省。2022-3-4算法設計與分析演示稿 紀玉波制作(C)12例2. 快速排序 快速排序(Quick sort)是1962年由霍爾（Hoare）提出的，故也稱為霍爾快速排序。這是一種基于分部分進行互換的排序方法，其基本思想是將所有數據逐步劃分成越來越多的許多小部分，每劃分一次，以后的互換只在劃分成的各小部分中進行，再將各小部分劃分成更小的部分。此算法是把一個大問題劃分成一些子問題，對這些子問題再用同樣的算法遞歸地進行處理，最后將所有子問題的解答合在一起即得到原來大問題的解，這種處

11、理問題的算法叫做分治法（Divide and conquer）。2022-3-4算法設計與分析演示稿 紀玉波制作(C)13 進行快速排序運算，首先任選其中一個數據（例如選第一個數據）作為標準，經過一定的互換運算，令它將其余的數據劃分為兩部分，它本身處于這兩部分數據之間，并且它前面的所有的數據均小于或等于它，它后面的所有的數據均大于或等于它。由此可看出兩點：第一，此數據的位置就是它最終的合適位置，進一步的運算過程中此數據即不必再動；第二，以后的排序運算只需在劃分成的每部分里進行，兩部分之間不會再有數據互換。第一次劃分以后，再用相同的算法對劃成的部分進行類似的運算，即從每部分中任選一個數據將其劃分

12、成更小的兩部分，依此遞歸地做下去，直至每個小部分中的數據個數均不超過一個為止，排序過程即結束。2022-3-4算法設計與分析演示稿 紀玉波制作(C)14 如原始數據已存于一維數組K中，設進行比較的兩個數據所在單元下標分別為i和j。初始時i指向數組中第一個數據，j指向第末個數據。i先不動使j逐步前移，每次對二者的數據進行比較，當遇到Ki大于Kj的情況時，即將二者對調位置；然后令j固定使i逐步后移做數據比較，再遇到Ki大于Kj時又進行位置對調；以后又是i不動使j前移做數據比較；如此反復進行，直至i與j兩者相遇為止。下面是一實例：2022-3-4算法設計與分析演示稿 紀玉波制作(C)15(13) 1

13、5 7 10 20 4 8 (19)(13) 15 7 10 20 4 (8) 19 8 (15) 7 10 20 4 (13) 19 8 (13) 7 10 20 (4) 15 19 8 4 (7) 10 20 (13) 15 19 8 4 7 (10) 20 (13) 15 19 8 4 7 10 (20) (13) 15 19 8 4 7 10 (13) 20 15 19 第一趟比較2022-3-4算法設計與分析演示稿 紀玉波制作(C)16 其中括號中的數據表示正進行比較的兩個數據，左面一個的下標為i，右面一個的下標為j。最后一行只有一個括號，說明i與j相等了，此單元即是作為標準的數據（

14、13）之最終位置。 從圖中可以看出，作為標準的數據（13）要多次與別的數據進行比較和互換。為了節約運算時間，可先將其取出給一局部工作變量賦值，以后只移動別的數據，它不真正參加“互換”，一直到i=j時才將其置入最終合適的位置處。2022-3-4算法設計與分析演示稿 紀玉波制作(C)17(1 13 3) 15 7 10 20 4 8 19(8 8) 4 7 10 13 20 15 19(7 7) 4 8 (1 10 0) 13 20 15 19 4 7 8 10 13 (2 20 0) 15 19 4 7 8 10 13 (1 19 9) 15 20 4 7 8 10 13 19 15 20 每一

15、趟比較2022-3-4算法設計與分析演示稿 紀玉波制作(C)18最壞情況分析：若每次選作標準的元素恰好是其中最小的一個，則劃分出的兩組數據，一組為零個元素，另一組只比原來少一個，這樣所需的趟數最多，如下表所示：已選取元素剩余元素個數比較趟數本趟比較次數1x) 1( n1) 1( n21xx) 2( n2) 2( n321xxx) 3( n3) 3( n1321,nxxxx1) 1( n1因此所需比較次數為： )() 1(21211nOnnini2022-3-4算法設計與分析演示稿 紀玉波制作(C)19 平均情況分析：此處除了為了具體推導出平均情況復雜性外還有兩個目的：一是可以看出平均情況復雜性

16、分析較最壞情況復雜性分析要困難得多；二是舉例說明遞歸方程的解法。 設選作標準的元素將數據分成兩組，一組有k個元素，另一組有（n-k-1）元素。由于要考慮各種可能的情況，k值可能為0（n-1），相應的另一組的個數則為（n-1）0。令對n個元素進行快速排序所需要的平均比較次數為C（n），并設k的各種取值出現的概率相等，則C（n）為各種k的取值的平均值10)1()() 1(1)(nk2n knCkCnnnC2022-3-4算法設計與分析演示稿 紀玉波制作(C)20 式中括號中第一項為第一趟所需的比較次數，后面兩項分別為左右兩部分數據繼續進行快速排序所需的平均總比較次數， 。 這是一個遞歸方程，常可用

17、兩種解法：第一種是試猜法，即假設一個帶有若干待定常數的函數，代入方程中導出這些常數，但這種方法假設這個函數要有一定經驗；另一種方法是直接利用遞歸方程的特點求解。我們現介紹后一種方法。而對于2n有0)(nC2022-3-4算法設計與分析演示稿 紀玉波制作(C)21上式中求和的第一項不隨k改變，其平均值即為它本身：101) 1(1nknnn后兩項的求和恰好相等，只是次序不同，因：k012n-2n-1C(k)C(0)C(1)C(2)C(n-2)C(n-1)C(n-k-1)C(n-1)C(n-2)C(n-3)C(1)C(0)故上述公式可以表示成 10)(2) 1()(nk2n kCnnnC用n乘左右兩

18、邊，得 10)(2) 1()(nk kCnnnnC令1nn 10)(2) 1()() 1(nk kCnnnCn2022-3-4算法設計與分析演示稿 紀玉波制作(C)22將 此 兩 式 相 減 ， 得 )(22)()1()1(nCnnnCnCn即 nnCnnCn2)()2()1()1(等 式 兩 邊 用)2)(1(nn除 ， 得 )2)(1(21)(2)1(nnnnnCnnC令 )2)(1(2)(,1)()(nnnnbnnCnd， 則 )1(2)1(ndnnC2022-3-4算法設計與分析演示稿 紀玉波制作(C)23上 式 簡 化 為 )()()1(nbndnd這 個 遞 歸 方 程 可 以 一 直 推 下 去 ， 并 考 慮 到 有 02)1()1(Cd， 故 )()()1(nbndnd )()1()1(nbnbnd )()1()1(nbnb