3

T(n)=3T(n/2)+n我需要找到 n 的递归解，如果n>1 和 T(n)=1，则为2 的幂。

使用替换n=2^m,S(m)=T(2^(m-1))我可以得到：

S(m)=2^m+3*2^(m-1)+3^2*2^(m-2)+⋯+3^(m-1) 2^1+3^m

但我不知道如何简单地做到这一点。

4

4 回答 4

7

这些类型的递归最容易通过 Master Theorem 解决，用于分析算法，解释如下：

令a为大于或等于 1 的整数，b为大于 1 的实数，c为正实数。鉴于形式的重复 -

T (n) = a * T(n/b) + n c其中 n > 1，则对于n a b的幂，如果

  1. 对数b a < c, T (n) = Θ(n c );
  2. 对数b a = c, T (n) = Θ(n c * Log n);
  3. 日志b a > c，T (n) = Θ(n log b a )。

你复发的英文翻译

Master Theorem 中要理解的最关键的事情是递归中提到的常数a、b 和 c 。让我们以您自己的重复 - T(n) = 3T(n/2) + n - 为例。

这个递归实际上是说它所代表的算法是这样的，

（解决大小为n的问题的时间）=（解决大小为n/2的3 个问题所用的时间）+ n

最后的n是合并那些3 n/2大小问题的结果的成本。

现在，您可以直观地理解：

  • 如果“解决3个大小为n/2的问题”的成本比“ n ”的权重更大，那么第一项将决定整体复杂性；
  • 如果成本“ n ”比“解决3个大小为n/2的问题”具有更大的权重，则第二项将决定整体复杂性；和，
  • 如果两个部分的权重相同，则解决子问题并合并它们的结果将具有整体复合权重。

从以上三个直观的理解，只出现了Master Theorem的三种情况。

在您的示例中，a = 3，b = 2 和 c = 1。因此它属于 case-3，因为 Log b a = Log 2 3 大于 1（c 的值）。

因此，复杂性很简单 - Θ(n log b a ) = Θ(n log 2 3 )。

于 2015-12-16T08:04:09.390 回答
3

您可以使用 Masters theorem 解决此问题，也可以通过以下方式打开递归树：

  • 在递归树的根部，你将有一个 n 的工作。
  • 在第二阶段，树分成三部分，在每一部分中，工作将是 n / 2。
  • 继续前进，直到你到达树叶。整个工作叶将为： O (1) = O (n / 2 ^ k) 当： n = 2 ^ k。
  • 请注意，在每一步 m 都有 3 ^ m 个拆分。
  • 现在我们将使用几何级数和对数规则将所有步骤组合在一起。最后，你会得到： T(n) = 3T(n/2)+n = 2n^(log3)-2n 计算
于 2018-08-11T12:22:15.863 回答
2

请查看第 60 页http://www.cs.columbia.edu/~cs4205/files/CM2.pdf。

也许你应该在这里问https://math.stackexchange.com/

于 2013-09-15T21:37:42.543 回答
1

像这样的问题可以使用Masters theorem来解决。

在你的情况下a = 3，b = 2和f(n) = n。

所以c = log_b(a) = log_2(3)，它大于 1，因此你属于第一种情况。所以你的复杂性是：

O(n^{log_2(3)}) = O(n^{1.58})

于 2015-12-16T07:30:35.720 回答