algorithm - 大师方法——为什么不能解出 T(n) = T(n/2) + n^2/logn？

Question

大师的方法——为什么解不了T(n) = 4*T(n/2) + (n^2)/logn?

我意识到它可以解决 T(n) = aT(n/b) + f(n) 类型的递归

在 MIT OCW 上，他们提到它无法解决上述复发问题。有人可以解释原因吗？

Answer 1

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

我可能错了，请检查并告诉我!