0

我在渐近分析问题上遇到了一些麻烦:我的问题是计算最大值,如果 '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'的价值,我应该只使用算法概念还是他们的任何其他方式来找出或任何解决方案。

4

2 回答 2

2

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

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

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

由于 log b a = log 2 7 大于 d = 2,因此递归求解为 T(n) = Θ(n log 2 7 )。

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

  • 日志4 a > 2,并且
  • 日志4 a < 日志2 7

然后主定理说 T'(n) = Θ(n log 4 a ) = o(n log 2 7 ) 我们就完成了。所以我们需要解决一个。

这样做会给

日志4 a < 日志2 7

log 2 a / log 2 4 < log 2 7(使用对数基本公式的更改)

日志2 a / 2 < 日志2 7

日志2 a < 2 日志2 7

log 2 a < log 2 7 2(使用对数的幂规则)

日志2 a < 日志2 49

< 49

因此,您可以选择的最大整数 a 是 48。

希望这可以帮助!

于 2013-10-09T18:16:08.337 回答
0

求解方程以获得非递归运行时公式

于 2013-09-17T12:12:50.053 回答