算法設(shè)計與分析-04算法分析舉例

算法設(shè)計與分析——算法分析舉例2023/2/41算法設(shè)計與分析演示稿紀(jì)玉波制作(C)算法分析舉例本節(jié)舉幾個對具體算法進行分析的例子，可以由此學(xué)習(xí)分析的方法，舉一反三再分析其它的算法。2023/2/42算法設(shè)計與分析演示稿紀(jì)玉波制作(C)例1.堆陣排序1．堆陣堆陣排序（Heapsort,1964年RobertW.Floyd和J.Williams共同設(shè)計，1978年RobertW.Floyd獲圖靈獎）是利用二叉樹的一種排序方法。堆(Heap)也譯為堆或堆壘,是與二叉排序樹不同的一種二叉樹，它的定義為：一個完全二叉樹(完全二叉樹：各層都是滿的，只是最下面一層從右邊起連續(xù)缺幾個結(jié)點)，它的每個結(jié)點對應(yīng)于原始數(shù)據(jù)的一個元素，且規(guī)定：如果一個結(jié)點有子結(jié)點，此結(jié)點數(shù)據(jù)必須大于或等于其子結(jié)點的數(shù)據(jù)。由此可見，堆是完全二叉樹，且規(guī)定了父結(jié)點和子結(jié)點數(shù)據(jù)之間必須滿足的條件。

2023/2/43算法設(shè)計與分析演示稿紀(jì)玉波制作(C)由于堆陣是完全二叉樹，采用將結(jié)點順序編號存于一維數(shù)組中的表示法較鏈接表示法節(jié)省存儲也便于運算。設(shè)某堆的結(jié)點數(shù)共有n個，順序?qū)⑺鼈兇嫒艘痪S數(shù)組K中，下標(biāo)從1到n。根據(jù)順序表示二叉樹的特點，除下標(biāo)為1的結(jié)點是整個樹的根結(jié)點而沒有父結(jié)點以外，其余下標(biāo)為j的結(jié)點（2≤j≤n）都有父結(jié)點，父結(jié)點的下標(biāo)為i=。故堆陣的條件可以表示成:K[i]≥K[j]當(dāng)2≤j≤n和i=由堆的定義可知，其根結(jié)點（即在數(shù)組中下標(biāo)為1的結(jié)點）具有最大的數(shù)值，堆陣排序就是利用這一特點進行的。堆陣排序過程分為構(gòu)成堆和利用它來排序兩個階段，下面分別進行介紹。2023/2/44算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2．構(gòu)成堆陣的過程可以采用兩種方法構(gòu)成堆陣。第一種方法是從根結(jié)點起逐個插入結(jié)點，在插入結(jié)點過程中進行父子結(jié)點數(shù)據(jù)比較和必要的互換調(diào)整，使之總滿足堆的條件；第二種方法則是先把所有數(shù)據(jù)按任意次序置入完全二叉樹的各結(jié)點中，然后由下而上逐層進行父子結(jié)點數(shù)據(jù)比較，進行必要的互換調(diào)整，直至使其最后完全滿足堆的條件，數(shù)據(jù)的比較調(diào)整可以使用“篩”運算進行。篩運算從最末尾結(jié)點（下標(biāo)為n）的父結(jié)點（下標(biāo)為）開始，向前逐結(jié)點進行，直至篩完根結(jié)點即形成此堆陣。篩每個結(jié)點時，將其數(shù)值與其兩個子結(jié)點中數(shù)值較大者進行比較，如小于子結(jié)點數(shù)值，則與之進行互換，互換后又將它看成父結(jié)點，再與下一層的子結(jié)點進行比較，如此做下去，直至不小于其子結(jié)點的數(shù)值或已篩到端結(jié)點而不再有子結(jié)點了，此數(shù)據(jù)的篩運算即完成。2023/2/45算法設(shè)計與分析演示稿紀(jì)玉波制作(C)3．利用堆陣排序由于在一個堆中根結(jié)點數(shù)據(jù)總是所有數(shù)據(jù)中之最大者，利用堆陣排序的方法是從根結(jié)點逐個取出數(shù)據(jù)，每次將新的元素再提到根結(jié)點，如此反復(fù)進行。為了節(jié)約存儲，要求排序得到的有序數(shù)據(jù)序列仍存放于原數(shù)組中，故將從根結(jié)點取出的數(shù)據(jù)由數(shù)組的末端起逐單元存放。每存放一個數(shù)據(jù)，同時將原在該單元的數(shù)據(jù)換到根結(jié)點，但這樣互換后一般會破壞堆的條件，為此，需對根結(jié)點再做一次篩運算，就又可形成新的滿足條件的堆。隨著數(shù)組末端存放的由堆中取出的數(shù)據(jù)越來越多，堆的結(jié)點數(shù)逐漸減少，當(dāng)?shù)饺〕隽?n-1)個數(shù)據(jù)，堆陣只剩下一個根結(jié)點，此最后一個數(shù)據(jù)一定是全部數(shù)據(jù)中的最小者，堆陣排序過程即全部結(jié)束。2023/2/46算法設(shè)計與分析演示稿紀(jì)玉波制作(C)4．時間復(fù)雜性分析堆陣排序分為建立堆陣和利用堆陣排序兩大步驟。設(shè)堆陣有r個滿層，元素個數(shù)n=2r-1。最壞的情況假設(shè)每個元素都需要從原來位置篩到堆陣的最底層，僅原來在最底層的不必篩，這樣一來最上層的一個元素要下降r-1層；第二層的兩個元素要下降r-2層；……；中間第i層2(i-1)個元素要下降r-I層；……；下面倒數(shù)第一層，也即第r-1層的2(r-2)個元素下降一層。每篩下一層要進行兩次比較（先左右兩子節(jié)點相比，然后此元素與其中較大者比）。因此在最壞的情況下，為了建立堆陣所需要的比較次數(shù)為：2023/2/47算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/48算法設(shè)計與分析演示稿紀(jì)玉波制作(C)下面看利用堆陣排序所需要的比較次數(shù)。排序時由后向前順次將元素與根結(jié)點對換，并將換到根結(jié)點的元素篩到合適的位置處，如果逐個進行，堆陣越來越小，直至排序完畢。設(shè)在某一步堆陣有i個元素，其深度為，最壞情況將根元素篩到堆陣最下層需要比較次為，故最壞情況排序過程的總比較次數(shù)為：2023/2/49算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/410算法設(shè)計與分析演示稿紀(jì)玉波制作(C)因此堆陣排序總的比較次數(shù)當(dāng)n較大時最壞情況為2nlogn(其復(fù)雜性為O(nlogn))，為排序問題下界的兩倍。雖然此排序算法時間上不是最優(yōu)，但它是“就地”進行運算，也不需要指示字分量，故所占空間比較節(jié)省。2023/2/411算法設(shè)計與分析演示稿紀(jì)玉波制作(C)例2.快速排序快速排序(Quicksort)是1962年由霍爾（Hoare）提出的，故也稱為霍爾快速排序。這是一種基于分部分進行互換的排序方法，其基本思想是將所有數(shù)據(jù)逐步劃分成越來越多的許多小部分，每劃分一次，以后的互換只在劃分成的各小部分中進行，再將各小部分劃分成更小的部分。此算法是把一個大問題劃分成一些子問題，對這些子問題再用同樣的算法遞歸地進行處理，最后將所有子問題的解答合在一起即得到原來大問題的解，這種處理問題的算法叫做分治法（Divideandconquer）。2023/2/412算法設(shè)計與分析演示稿紀(jì)玉波制作(C)進行快速排序運算，首先任選其中一個數(shù)據(jù)（例如選第一個數(shù)據(jù)）作為標(biāo)準(zhǔn)，經(jīng)過一定的互換運算，令它將其余的數(shù)據(jù)劃分為兩部分，它本身處于這兩部分?jǐn)?shù)據(jù)之間，并且它前面的所有的數(shù)據(jù)均小于或等于它，它后面的所有的數(shù)據(jù)均大于或等于它。由此可看出兩點：第一，此數(shù)據(jù)的位置就是它最終的合適位置，進一步的運算過程中此數(shù)據(jù)即不必再動；第二，以后的排序運算只需在劃分成的每部分里進行，兩部分之間不會再有數(shù)據(jù)互換。第一次劃分以后，再用相同的算法對劃成的部分進行類似的運算，即從每部分中任選一個數(shù)據(jù)將其劃分成更小的兩部分，依此遞歸地做下去，直至每個小部分中的數(shù)據(jù)個數(shù)均不超過一個為止，排序過程即結(jié)束。2023/2/413算法設(shè)計與分析演示稿紀(jì)玉波制作(C)如原始數(shù)據(jù)已存于一維數(shù)組K中，設(shè)進行比較的兩個數(shù)據(jù)所在單元下標(biāo)分別為i和j。初始時i指向數(shù)組中第一個數(shù)據(jù)，j指向第末個數(shù)據(jù)。i先不動使j逐步前移，每次對二者的數(shù)據(jù)進行比較，當(dāng)遇到K[i]大于K[j]的情況時，即將二者對調(diào)位置；然后令j固定使i逐步后移做數(shù)據(jù)比較，再遇到K[i]大于K[j]時又進行位置對調(diào)；以后又是i不動使j前移做數(shù)據(jù)比較；……；如此反復(fù)進行，直至i與j兩者相遇為止。下面是一實例：2023/2/414算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/415算法設(shè)計與分析演示稿紀(jì)玉波制作(C)其中括號中的數(shù)據(jù)表示正進行比較的兩個數(shù)據(jù)，左面一個的下標(biāo)為i，右面一個的下標(biāo)為j。最后一行只有一個括號，說明i與j相等了，此單元即是作為標(biāo)準(zhǔn)的數(shù)據(jù)（13）之最終位置。從圖中可以看出，作為標(biāo)準(zhǔn)的數(shù)據(jù)（13）要多次與別的數(shù)據(jù)進行比較和互換。為了節(jié)約運算時間，可先將其取出給一局部工作變量賦值，以后只移動別的數(shù)據(jù)，它不真正參加“互換”，一直到i=j時才將其置入最終合適的位置處。2023/2/416算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/417算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/418算法設(shè)計與分析演示稿紀(jì)玉波制作(C)平均情況分析：此處除了為了具體推導(dǎo)出平均情況復(fù)雜性外還有兩個目的：一是可以看出平均情況復(fù)雜性分析較最壞情況復(fù)雜性分析要困難得多；二是舉例說明遞歸方程的解法。設(shè)選作標(biāo)準(zhǔn)的元素將數(shù)據(jù)分成兩組，一組有k個元素，另一組有（n-k-1）元素。由于要考慮各種可能的情況，k值可能為0～（n-1），相應(yīng)的另一組的個數(shù)則為（n-1）～0。令對n個元素進行快速排序所需要的平均比較次數(shù)為C（n），并設(shè)k的各種取值出現(xiàn)的概率相等，則C（n）為各種k的取值的平均值2023/2/419算法設(shè)計與分析演示稿紀(jì)玉波制作(C)式中括號中第一項為第一趟所需的比較次數(shù)，后面兩項分別為左右兩部分?jǐn)?shù)據(jù)繼續(xù)進行快速排序所需的平均總比較次數(shù)，。這是一個遞歸方程，?？捎脙煞N解法：第一種是試猜法，即假設(shè)一個帶有若干待定常數(shù)的函數(shù)，代入方程中導(dǎo)出這些常數(shù)，但這種方法假設(shè)這個函數(shù)要有一定經(jīng)驗；另一種方法是直接利用遞歸方程的特點求解。我們現(xiàn)