快速排序平均情況下的復(fù)雜性_第1頁
快速排序平均情況下的復(fù)雜性_第2頁
快速排序平均情況下的復(fù)雜性_第3頁
快速排序平均情況下的復(fù)雜性_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

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

文檔簡介

1、設(shè)數(shù)組中所有元素兩兩不同，且所有置換出現(xiàn)的可能性是一樣的。A(k):數(shù)組中待排序的個數(shù)只有k個時排序所做的復(fù)雜性，設(shè)分區(qū)完成后，設(shè)(first,，splitPoint-1)中沒有兩個元素互相 之間做過比較，因此，子區(qū)間各種置換出現(xiàn)的概率還是等可能的。對對n 2(splitPoint+1, ，last)，也作同樣的假定。A (n) = n - 1 + S (A (i) + A (n - 1 - i) n i=0(4.1)A (1) = A (0) = 02 BA (n) = n - 1 + 乙 A (i) ni=0快速排序在最好情況下的復(fù)雜性為b (n lg n)定理4.2對遞歸方程(4.1)，

2、3c有 A (n) Cn成立。S i ln( i)2 n-12A (n) = n 1 + 乙 A (i) (n 1) + x c nni=0因為是單調(diào)增函數(shù)，所以:x in x)S i ln( i) 2,如c = 2，就得到:A (n) 2 n lg( n)推論4.3平均情況下即設(shè)所有置換等可能性地出現(xiàn)時快速排序所做 的比較的次數(shù)為1.386 n lg( n)。平均情況下快速排序算法復(fù)雜性的精確估算(4.2)(4.3)2n2A (n - 1) = n - 2 +乙 A (i)n 一 1i=0%方程(4.2)- (n-1)、方程(4.3)，得到:nA (n) (n 1) A(n 1) = 2 A(n 1) + 2(n 1)所以A (n) A (n 1) 2( n 1)n + 1 nn (n + 1)令：則遞歸方程化為:A( n)n + 12( n 1)B (n) = B (n 1) + n(n +1)B (1) = 0因為，調(diào)和級數(shù)：U 1ii=1其中所以：B (n) = 2 U 1 + 4 Uii(i + 1)i=1i=1W 2(ln( n) + 0.577 ) - 4n /

溫馨提示

  • 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

提交評論