算法設(shè)計(jì)與分析_04算法分析舉例

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

2、，它的定義為：一個(gè)完全二叉樹(完全二叉樹：各層都是滿的，只是最下面一層從右邊起連續(xù)缺幾個(gè)結(jié)點(diǎn))，它的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于原始數(shù)據(jù)的一個(gè)元素，且規(guī)定：如果一個(gè)結(jié)點(diǎn)有子結(jié)點(diǎn)，此結(jié)點(diǎn)數(shù)據(jù)必須大于或等于其子結(jié)點(diǎn)的數(shù)據(jù)。由此可見，堆是完全二叉樹，且規(guī)定了父結(jié)點(diǎn)和子結(jié)點(diǎn)數(shù)據(jù)之間必須滿足的條件。 2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)4 由于堆陣是完全二叉樹，采用將結(jié)點(diǎn)順序編號(hào)存于一維數(shù)組中的表示法較鏈接表示法節(jié)省存儲(chǔ)也便于運(yùn)算。設(shè)某堆的結(jié)點(diǎn)數(shù)共有n個(gè)，順序?qū)⑺鼈兇嫒艘痪S數(shù)組K中，下標(biāo)從1到n。根據(jù)順序表示二叉樹的特點(diǎn)，除下標(biāo)為1的結(jié)點(diǎn)是整個(gè)樹的根結(jié)點(diǎn)而沒(méi)有父結(jié)點(diǎn)以外，其余下標(biāo)為j的結(jié)點(diǎn)（2jn）

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

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

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

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

7、2)個(gè) 2， 第二項(xiàng)包括(r-3)個(gè) 3，最后一項(xiàng)是一個(gè) 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 （當(dāng)n較大時(shí)）2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)9 下面看利用堆陣排序所需要的比較次數(shù)。排序時(shí)由后向前順次將元素與根結(jié)點(diǎn)對(duì)換，并將換到根結(jié)點(diǎn)的元素篩到合適的位置處，如果逐個(gè)進(jìn)行，堆陣越來(lái)越小，直至

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

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

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

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

12、成更小的兩部分，依此遞歸地做下去，直至每個(gè)小部分中的數(shù)據(jù)個(gè)數(shù)均不超過(guò)一個(gè)為止，排序過(guò)程即結(jié)束。2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)14 如原始數(shù)據(jù)已存于一維數(shù)組K中，設(shè)進(jìn)行比較的兩個(gè)數(shù)據(jù)所在單元下標(biāo)分別為i和j。初始時(shí)i指向數(shù)組中第一個(gè)數(shù)據(jù)，j指向第末個(gè)數(shù)據(jù)。i先不動(dòng)使j逐步前移，每次對(duì)二者的數(shù)據(jù)進(jìn)行比較，當(dāng)遇到Ki大于Kj的情況時(shí)，即將二者對(duì)調(diào)位置；然后令j固定使i逐步后移做數(shù)據(jù)比較，再遇到Ki大于Kj時(shí)又進(jìn)行位置對(duì)調(diào)；以后又是i不動(dòng)使j前移做數(shù)據(jù)比較；如此反復(fù)進(jìn)行，直至i與j兩者相遇為止。下面是一實(shí)例：2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(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算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)16 其中括號(hào)中的數(shù)據(jù)表示正進(jìn)行比較的兩個(gè)數(shù)據(jù)，左面一個(gè)的下標(biāo)為i，右面一個(gè)的下標(biāo)為j。最后一行只有一個(gè)括號(hào)，說(shuō)明i與j相等了，此單元即是作為標(biāo)準(zhǔn)的數(shù)據(jù)（

14、13）之最終位置。 從圖中可以看出，作為標(biāo)準(zhǔn)的數(shù)據(jù)（13）要多次與別的數(shù)據(jù)進(jìn)行比較和互換。為了節(jié)約運(yùn)算時(shí)間，可先將其取出給一局部工作變量賦值，以后只移動(dòng)別的數(shù)據(jù)，它不真正參加“互換”，一直到i=j時(shí)才將其置入最終合適的位置處。2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(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算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)18最壞情況分析：若每次選作標(biāo)準(zhǔn)的元素恰好是其中最小的一個(gè)，則劃分出的兩組數(shù)據(jù)，一組為零個(gè)元素，另一組只比原來(lái)少一個(gè)，這樣所需的趟數(shù)最多，如下表所示：已選取元素剩余元素個(gè)數(shù)比較趟數(shù)本趟比較次數(shù)1x) 1( n1) 1( n21xx) 2( n2) 2( n321xxx) 3( n3) 3( n1321,nxxxx1) 1( n1因此所需比較次數(shù)為： )() 1(21211nOnnini2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)19 平均情況分析：此處除了為了具體推導(dǎo)出平均情況復(fù)雜性外還有兩個(gè)目的：一是可以看出平均情況復(fù)雜性

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

17、兩種解法：第一種是試猜法，即假設(shè)一個(gè)帶有若干待定常數(shù)的函數(shù)，代入方程中導(dǎo)出這些常數(shù)，但這種方法假設(shè)這個(gè)函數(shù)要有一定經(jīng)驗(yàn)；另一種方法是直接利用遞歸方程的特點(diǎn)求解。我們現(xiàn)介紹后一種方法。而對(duì)于2n有0)(nC2022-3-4算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)21上式中求和的第一項(xiàng)不隨k改變，其平均值即為它本身：101) 1(1nknnn后兩項(xiàng)的求和恰好相等，只是次序不同，因：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算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(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算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)23上 式 簡(jiǎn) 化 為 )()()1(nbndnd這 個(gè) 遞 歸 方 程 可 以 一 直 推 下 去 ， 并 考 慮 到 有 02)1()1(Cd， 故 )()()1(nbndnd )()1()1(nbnbnd )()1()1(nbnb