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

Question

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

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) 总是更快）。如果它似乎对您不起作用，您将不得不使用其他技术来解决重复问题。