目錄
- 演算法時間復雜度
- 主方法
- 分治法
- 歸并排序
- 乘方問題
- 斐波那契數列
演算法時間復雜度
主方法
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)
由定義可知上式成立，
參考：
主定理 Master-Theorem
MIT演算法導論公開課之課程筆記
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/16676.html
標籤：其他
下一篇：c學習