algorithm - 如果f(n) 包含log(n) 的某项，是否可以通过Master Method 解决这个问题？

Question

Master Method 是获得解决方案的直接方法。主方法仅适用于以下类型的循环或可以转换为以下类型的循环。

T(n) = a T(n/b) + f(n) 其中 a ≥ 1，b > 1，且 f(n) = Θ(n^c)。

有以下三种情况:

1. 如果 c < log_b(a) 则 T(n) = Θ(n^log_b(a)) .

2. 如果 c = log_b(a) 则 T(n) = Θ(n^c log(n))。

   <

3. 如果 c > log_b(a) 则 T(n) = Θ(f(n))。

在Master Method中，如果f(n)包含log(n)的某项，是否可以通过Master Method解决这个问题？例如在T(n)=4T(n/2)+n^2logn这里大师定理是否适用

Answer 1

实际上不可能直接判断主方法是否适用于某些对数函数。这将取决于您要解决的具体重复问题。这完全取决于 f 相对于 n^{log_b a} 的增长情况。

在JPC给出的例子中(其中T(n) = 4T(n/2) + log(n))，确实是可以的。但是，还要考虑示例 T(n) = 2T(n/5) + log(n)。在这种循环中，很难确定 n^{log₅ 2} 是否比 log(n) 增长得更快。如果对数函数 f(n) 变得更复杂(例如 log₃(n/2))，它会变得更难。

简而言之，当指数小于 1 时，可能很难确定对数函数与指数函数相比如何增长(对于指数 >= 1，log(n) 总是更快)。如果它似乎对您不起作用，您将不得不使用其他技术来解决复发问题。