大师方法 - 为什么它不能解 T(n) = 4*T(n/2) + (n^2)/logn？
我意识到它可以解决 T(n) = aT(n/b) + f(n) 类型的递归
在 MIT OCW 上，他们提到它无法解决上述复发问题。有人可以解释一下为什么吗？
最佳答案
T(n/2) + (n^2)/logn 的答案:
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does not apply,
f(n) = Ω(n^e) for e = 1, BUT
a*f(n/b) <= c*f(n) for no c<1 (works out that c >= 2)
所以我们不能应用任何案例。除此之外，我真的一无是处——而且我也不是 100% 同意这个答案。
以下内容是在此编辑之前的，并假设问题与 T(n) = T(n/2) + n^(2logn) 有关 我相当确定这是定理的情况 3。
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does apply,
a*f(n/b) <= c*f(n) for some c<1 (works out that c >= 0.5)
and f(n) = Ω(n^e) for e = 1
我可能是错的，所以检查一下并告诉我!
关于algorithm - 主方法 - 为什么它不能解 T(n) = T(n/2) + n^2/logn？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10676034/