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

我可能错了，所以检查一下，让我知道！

Answer 2

f(n)=(n^2)/logn 和 n^(log a/log b) 。计算上述两个函数之间的差异。

比率= (n^2/log n)/(n^2)

这个比率原来是对数的。这种递推关系属于情况2和情况3之间的差距。因此，马斯特斯定理不适用于这种递推关系。

当上述两个函数之间的差是多项式时，Masters 定理是适用的。

Answer 3

这似乎是第三种情况，因为 f(n) 更大，但它也应该满足规则性条件（对于某些 c in(0,1)，af(n/b)<=cf(n)）。这里的函数不满足规律性条件，所以主方法在这里失败

Answer 4

这是因为在所有提到的三种情况下，您都无法证明正渐近性质是合理的。这意味着当 n->infinity n^2/lg(n) -> infinity 时，这只是意味着 n^e = w(lg(n))，可以解释为“函数不能包含”没有上限为分治程序而存在。