硕士定理,f(n)= log n

Question

对于硕士定理,T(n) = a*T(n/b) + f(n)我使用3个案例:

1. 如果a*f(n/b) = c*f(n)为某些常数c > 1那么T(n) = (n^log(b) a)
2. 如果a*f(n/b) = f(n)那么T(n) = (f(n) log(b) n)
3. 如果a*f(n/b) = c*f(n)为某些常数c < 1那么T(n) = (f(n))

但是当f(n) = log n或时n*log n,值c取决于n的值.如何使用master's定理求解递归函数？

Answer 1

通常,f(n)必须是多项式才能应用主定理 - 它不适用于所有函数.然而,主定理有一个有限的"第四种情况",它允许它应用于多对数函数.

如果 f(n)= O(n ^{log _b a} log ^k n),则 T(n)= O(n ^{log _b a} log ^{k + 1} n).

换句话说,假设你有T(n)= 2T(n/2)+ n log n.f(n)不是多项式,但f(n)= n log n,k = 1.因此,T(n)= O(n log ² n)

有关更多信息,请参阅此讲义:http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf

Answer 2

您可能会发现维基百科关于马斯特定理的文章中的这三种情况更有用：

• 情况 1：f(n) = θ(n ^c )，其中 c < log _b a
• 情况 2：f(n) = θ(n ^c log ^k n)，其中 c = log _b a
• 情况 3：f(n) = θ(n ^c )，其中 c > log _b a

现在不再直接依赖于 n 的选择 - 重要的是 f 的长期增长率以及它与常数 a 和 b 的关系。如果没有看到您试图解决的特定复发的更多细节，我无法提供任何更具体的建议。

希望这可以帮助！