解决递归问题 T(n) = 4T(n/4) + 3log n
Problems Solving Recurrence T(n) = 4T(n/4) + 3log n
我真的对解决上面的重复问题感到沮丧。我试图通过使用大师方法来解决它，但我就是没有完成...
我有一个递归算法，它需要 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
我试图找到我的递归程序的渐近 运行 时间，并想使用主定理来解决它。谁能告诉我这个循环是否可以使用主定理，如果可以，主定理的情况是什么？
感谢所有帮助，谢谢。
T(n) = O(n)，因为以 4 为底的 4 的对数是 1，而 3 * log(n) 是 O(n ^ 0.5)(0.5 < 1)。它对应于 here 中描述的 Master 定理的第一种情况。
我真的对解决上面的重复问题感到沮丧。我试图通过使用大师方法来解决它，但我就是没有完成...
我有一个递归算法，它需要 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
我试图找到我的递归程序的渐近 运行 时间，并想使用主定理来解决它。谁能告诉我这个循环是否可以使用主定理，如果可以，主定理的情况是什么？
感谢所有帮助，谢谢。
T(n) = O(n)，因为以 4 为底的 4 的对数是 1，而 3 * log(n) 是 O(n ^ 0.5)(0.5 < 1)。它对应于 here 中描述的 Master 定理的第一种情况。