algorithm - 这种重复可以有多少个子问题，同时仍然比初始重复更快？

Question

我在处理渐近分析问题时遇到了一些麻烦:我的问题是计算最大值，如果我的问题中所述为“a”:

An Algorith A has running time T(n)= 7T(n/2) + n^2
and Algorith B has running time T' = aT'(n/4) + n^2.
What will be the maximum integer value of 'a' such that algorith B runs 
asymptotically faster than A.

我应该如何找到“a”的值，我应该只使用算法概念吗？或者他们是否有任何其他方式来找出或任何解决方案。

Answer 1

这是使用主定理的好地方。

在第一次递归中，T(n) = 7T(n/2) + n²，主定理说

• a = 7
• b = 2
• d = 2

由于 log_b a = log₂ 7 大于 d = 2，递归求解为 T(n) = Θ(n^log₂7).

现在，让我们看看 T'(n)。在这里，我们有一个未知数，b = 4，d = 2。如果满足以下条件:

• log₄a > 2, 和
• log₄a < log₂ 7

然后大定理说 T'(n) = Θ(n^log₄a) = o(n^log₂7)，我们就完成了。所以我们需要求解一个。

这样做可以

log₄a < log₂ 7

log₂a / log₂ 4 < log₂ 7 (using the change of base formula for logs)

log₂ a / 2 < log₂ 7

log₂ a < 2 log ₂ 7

log₂ a < log₂ 7² (using the power rule for logs)

log₂ a < log₂ 49

a < 49

因此，您可以选择的最大积分 a 是 48。

希望这对您有所帮助!