目錄
- 演算法時間復雜度
- 主方法
- 分治法
- 歸并排序
- 乘方問題
- 斐波那契數列
- 快速排序
- 隨機化快速排序
演算法時間復雜度
主方法
case 1:
f(n)=O(n^(log(b)a-ε)) （ε>0）
=>T(n)=Θ(n^log(b)a)
case 2:
f(n)=Θ (n^log(b)a·(lgn)^k)（k>=0）
=>T(n)=Θ(n^log(b)a·(lgn)^(k+1))
case 3
f(n)=Ω(n^(log(b)a+ε))（ε>0）&& 存在0<ε‘<1，使得af(n/b)<=(1-ε’)·f(n)
=>T(n)=Θ(f(n))
case 1可用遞回樹證明：
分治法
歸并排序
排序步驟：
-
n為1時，已經完成排序，
-
n大于1時，遞回的對A[1~┏n/2┓]這部分以及A[┏n/2┓+1~n]這部分排序，
(┏ ┓表示向上取整） -
將排序好的兩個表合并，比較兩個表，依次取出最小者到輸出序列中，
-
運行時間：
遞回函式為T(n)=2T(n/2)+Θ(n)，(遞回時間+非遞回時間)
使用主方法，為case2 ，所以T(n)= Θ(nlgn)，
乘方問題
和二分查找實質一樣，將指數n二分：
有實數X和正整數n計算X^n，
當n為偶數時，X^n=X^(n/2)·X^(n/2)，當n為奇數時，X^n=X^((n-1)/2)·X^((n-1)/2)·X，
- 運行時間：
遞回函式為T(n)=T(n/2)+Θ(1)，
使用遞回樹法T(n)= Θ(lgn)，
斐波那契數列
-
Fn=φn/5(1/2)結果取最接近的整數（round），（φ是黃金分割數）
該方法無法用計算機實作（精確度不夠的原因），
運行時間：Θ(lgn)， -
平方遞回式：
(F(n+1) Fn) = (1 1)n
(Fn F(n-1)) (1 0)
運行時間：Θ(lgn)
證明方法可采用歸納法:
- (F2 F1) = (1 1)1
(F1 F0) (1 0) - (F(n+1) Fn) = (Fn F(n-1)) (1 1)
(Fn F(n-1)) (F(n-1) F(n-2)) (1 0)
由定義可知上式成立，
快速排序
運行時間：
- 最壞情況：
輸入資料本身已經排序或逆排序，劃分的一側始終無元素，
T(n)=T(0)+T(n-1)+Θ(n)
=Θ(1)+T(n-1)+Θ(n)
=T(n-1)+Θ(n)
=Θ(n^2)（遞回樹法）
- 最優情況：
每次的關鍵資料處于正中間 劃分為兩個長度相等的部分
T(n)=2T(n/2)+Θ(n)=Θ(nlgn)
-
特殊情況：
每次的關鍵資料處于特殊位置，比如：劃分為兩個長度分別占1/10 9/10：
-
交替產生特殊情況和最壞情況：
L(n)=2U(n/2)+Θ(n)（lucky）
U(n)=L(n-1)+ Θ(n)（unlucky）
Then L(n)=2(L(n/2-1))+Θ(n/2))+Θ(n)
=2L(n/2-1)+Θ(n)
=Θ(nlgn)
隨機化快速排序
既然我們知道了快速排序的最差情況是給的序列已經是順序或倒序的，那么我們可以將給的序列用亂數打亂順序（或者隨機選擇pivot基準數），這樣運行時間不依賴于輸入序列的順序，最差的情況由亂數產生器決定，
參考：
主定理 Master-Theorem
MIT演算法導論公開課之課程筆記
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/20233.html
標籤：其他
下一篇：c學習