performance - 解决递归问题 T(n) = 4T(n/4) + 3log n

Question

我真的对解决上面的重复问题感到沮丧。我试图通过使用 Master Method 来解决它，但我就是没有完成...

我有一个递归算法，它需要 3log n 次(三个二进制搜索)来识别四个子问题，每个子问题的大小为 n/4，然后单独解决它们直到 n 小于给定的某个常数通过输入。所以我得到了这种复发:

T(n) = 4*T(n/4) + 3*log(n)

Base-Case if n < c (c = some constant given by program input):

T(n) = 1

我试图找到我的递归程序的渐近运行时间，并想使用主定理来解决它。谁能告诉我是否可以将主定理用于此递归，如果可以，主定理的情况是什么？

感谢所有帮助，谢谢。

Answer 1

T(n) = O(n)，因为以 4 为底的 4 的对数是 1 而 3 * log(n) 是 O(n ^ 0.5) (0.5 < 1)。它对应于描述的 Master 定理的第一种情况 here .