主定理：
n為問題規模，a為遞推的子問題數量，n/b為每個子問題的規模，f（n）為遞推意以外進行的計算作業，
a≥1，b>1為常數，f(n) 為函式，T(n) 為非負整數，則有以下結果（分類討論）：
1）若 
則有
2）若
則有
3）若
且對于某個常數c<1和所有充分大的n有
則有
其中，大O代表的是該演算法的演算法復雜度上限，即該演算法在最壞情況之下的復雜度，f(x) = O(g(x))正式的數學定義：存在正常數c，n，n0，當n>n0時，對于任意f(n)符合0<=f(n)<=c*g(n) ,如圖：
從這張圖可以看出，當橫坐標的值大于x=n0時，cg(n)的縱值總大于f(n),這可以理解為f(x)以g(n)為上界，
大omega則是代表該演算法的演算法復雜度下限，即該演算法在最優情況之下的復雜度， f(n)= Ω(g(n)) 正式的數學定義：存在正常數c、n、n0，當 n > n0 的時，任意的 f(n) 符合 0 <= c*g(n) <= f(n)，如圖：
同理，我們可以從圖中看出，在n0之后cg(n)總比f(n)小，因此可以理解為f(x)以g(n)為下界，
大theta是演算法復雜度的確界，他既描述了上界，又描述了下界，
f(n)= θ(cg(n)) 正式的數學定義：存在正常數c1、c2、n、n0，當 n > n0 的時，對于任意的f(n）對符合 c1g(n) <= f(n) <= c2g(n)，c1g(n)、c2*g(n)都是漸進正函式（當n趨于無窮大的時候，f(n)為正）， 如圖：
演算法導論中還根據大O，大Ω，大θ的定義得到以下定理：
當且僅當函式 f(n) = O(g(n)) 并且 f(n）= Ω(g(n)) 時，才有 f(n) = θ(g(n))，
回到主定理，可以看出，只要求出log以b為底的a的n次方，復雜度就可以很快的算出來，我們把公式用剛介紹的概念翻譯一下：
1）若f(n)以log以b為底的a-ε的n次方為上界，則該遞推式的演算法復雜度的確界為log以b為底的a的n次方
2）若f(n)以log以b為底的a的n次方為確界，則該遞推式的演算法復雜度的確界為log以b為底的a的n次方乘以logn
3）若f(n)以log以b為底的a+ε的n次方為下界，且n充分大，則該遞推式的演算法復雜度的確界為f(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525024.html
標籤：其他