1

我在如何解决重复关系方面遇到了一些问题。

T(n) = T(n/2) + log2(n)，T(1) = 1，其中 n 是 2 的幂

这是一个家庭作业问题，所以不要只给我答案。我只是想知道如何开始这个问题。

在课堂上，我们复习了 Master 定理。但我认为这不是解决这种特殊关系的最佳方式。

我真的不知道如何开始这个问题......我应该去吗

T(n) = T(n/2) + log_base2(n)
T(n/2) = [T(n/4)+log_base2(n/2)]
  T(n) = [T(n/4)+log_base2(n/2)] + log_base2(n)

并且继续努力得到一些我可以看到的东西构成一个基本方程？

4

4 回答 4

6

此递归求解为Θ((log n) 2 )。这里有两种方法可以看到这一点。

一些替代品

如果您知道 n 是 2 的完美幂（即 n = 2 k），则可以将递归重写为

T(2 k ) = T(2 k-1 ) + k

让我们定义一个新的递归 S(k) = T(2 k )。然后我们得到

S(k) = S(k - 1) + k

如果我们扩展这个重复，我们得到

S(k) = S(k - 1) + k

= S(k - 2) + (k - 1) + k

= S(k - 3) + (k - 2) + (k - 1) + k

= S(k - 4) + (k - 3) + (k - 2) + (k - 1) + k

...

= S(0) + 1 + 2 + 3 + ... + k

= S(0) + Θ(k 2 )

假设 S(0) = 1，则此递归求解为 Θ(k 2 )。

由于 S(k) = T(2 k ) = T(n)，我们得到 T(n) = Θ(k 2 ) = Θ(log 2 n)。

迭代递归

这里的另一个选择是扩展一些递归项，看看是否出现了任何好的模式。这是我们得到的：

T(n) = T(n / 2) + lg n

= T(n / 4) + lg (n / 2) + lg n

= T(n / 8) + lg (n / 4) + lg (n / 2) + lg n

...

最终，在 lg n 层之后，这种递归式触底，我们只剩下这个表达式：

lg n + lg (n / 2) + lg (n / 4) + ... + lg (n / 2 lg n)

使用对数的性质，我们可以将其重写为

lg n + (lg n - 1) + (lg n - 2) + (lg n - 3) + ... + (lg n - lg n)

或者，反过来写，这是总和

0 + 1 + 2 + 3 + ... + lg n

该总和是高斯对 lg n 的总和，其计算结果为 (lg n)(lg n + 1) / 2 = Θ((log n)2)。

希望这可以帮助！

于 2013-11-05T01:10:35.610 回答
1

如果 n 是 2 的幂，那么您可以扩展递归并精确求解，使用 lg(a/b) = lg(a) - lg(b)。

T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1) + 1
     = (lg(n) - 0) + (lg(n) - 1) .... + (lg(n) - lg(n)) + 1
     = lg(n)*lg(n) - lg(n)*(lg(n)+1)/2 + 1
     = lg(n)*lg(n)/2 - lg(n)/2 + 1
于 2015-05-04T23:27:16.447 回答
0

这可以通过 Akra-Bazzi 定理来完成。请参阅http://people.mpi-inf.mpg.de/~mehlhorn/DatAlg2008/NewMasterTheorem.pdf中的第三个示例。

于 2015-05-04T22:08:36.483 回答
0

这可以用Master theorem解决。你的a=1和b=2和f(n) = log(n)。然后c = log2(1) = 0。因为你c和f(n)你陷入了第二种情况（哪里k=1）。

所以解是Θ(log 2 n)

于 2015-12-15T08:29:01.487 回答