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/cn.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