[理工] [分享] Extension of Master Theorem
Master Theorem 假設 T(n) = a*T(n/b) + f(n).
我這裡令 E = log_b a.
下圖表示出 f(n) 與 T(n) 之間的複雜度關係。
https://i.imgur.com/y21Kv4o.png
在 f(n) 的複雜度介於 n^(E-ε) 與 n^(E+ε) 之間時 (圖中紅虛線)，
M.T.可以處理的例子很有限。
我希望複雜度在這個範圍內的所有 f(n)，依然可以代公式來求 T(n)。
以下是我得到的結果。
----------------------------------------------
警告:
這是一道沒有醬汁的炸鳳尾蝦(X)
這是沒有嚴謹證明過的定理(O)
如果你發現任何反例或錯誤，請讓我知道，謝謝。
----------------------------------------------
為了儘可能的將複雜度介於 n^(E-ε) 與 n^(E+ε) 之間的 f(n) 一網打盡，
於是假設:
f(n) =
c * n^E * (log n)^(α_1) * (log log n)^(α_2) * (log log log n)^(α_3) * ...
其中 c 為 constant。
並且令 max{ i | α_i ≠ 0 } 為 constant，以確保 f(n) 為常數個函數相乘。
為了表示方便，這裡定義 log~x n 代表 log log ...log n，即 log 疊代x次。
^^^^^^^^^^^^^^
上面有x個 log
重新表示 f(n) :
f(n) = c * n^E * (log n)^(α_1) * (log~2 n)^(α_2) * (log~3 n)^(α_3) * ...
= c * n^E * Π_{i=1}^∞ (log~i n)^(α_i)
則
T(n) = Θ( n^E + f(n) * Π_{i=1}^β (log~i n) )
where β = min{ j | α_j ≠ -1 }.
β的找法：
從疊代次數為 1 的 log 疊代函數開始找，找到第一個次方不等於 -1 的 log 疊代函數，
則它的疊代次數就是 β。
------
例1
T(n) = 5*T(n/25) + n^0.5/log n
解1
E = log_b a = 0.5
f(n) = n^0.5/log n = n^E * (log n)^(-1) * (log~2 n)^0
β = min{ j | α_j ≠ -1 } = 2
所以
T(n) = Θ( n^E + f(n) * Π_{i=1}^β (log~i n) )
= Θ( n^0.5 + n^0.5/log n * log n * log~2 n )
= Θ( n^0.5 + n^0.5 * log~2 n )
= Θ( n^0.5 * log~2 n )
= Θ( n^0.5 * log log n )
------
例2
T(n) = 2*T(n/2) + n/(lg n)^2
解2
E = log_b a = 1
f(n) = n/(lg n)^2 = n^1 * (lg n)^(-2) = n^E * (lg n)^(-2)
β = min{ j | α_j ≠ -1 } = 1
所以
T(n) = Θ( n^E + f(n) * Π_{i=1}^β (log~i n) )
= Θ( n^1 + n/(lg n)^2 * log n )
= Θ( n + n/(lg n) )
= Θ(n)
------
例3
T(n) = 9*T(n/3) + n^2
解3
E = log_b a = 2
f(n) = n^2 = n^E * (log n)^0
β = min{ j | α_j ≠ -1 } = 1
所以
T(n) = Θ( n^E + f(n) * Π_{i=1}^β (log~i n) )
= Θ( n^2 + n^2 * log n )
= Θ( n^2 * log n )
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.72.73.139
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1520837535.A.EE4.html
推
03/12 14:58,
6年前
, 1F
03/12 14:58, 1F
推
03/12 18:11,
6年前
, 2F
03/12 18:11, 2F
不是很懂你的意思。
因為
(log_x n)=(log_x y)*(log_y n)
所以就算是自然對數也可以換底
※ 編輯: JKLee (1.160.108.53), 03/13/2018 22:07:58