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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1520837535.A.EE4.html 不是很懂你的意思。 因為 (log_x n)=(log_x y)*(log_y n) 所以就算是自然對數也可以換底 ※ 編輯: JKLee (1.160.108.53), 03/13/2018 22:07:58