求解递归 T(n) = T(n/2) + lg n？

Question

我对如何解决递归关系有一些问题。

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

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

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

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

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) 

继续我的工作，得到一些我能看到的东西是一个基本的等式？

Answer 1

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

一些替代品

如果您知道 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 ² )

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

由于 S(k) = T(2 ^k ) = T(n)，我们得到 T(n) = Θ(k ² ) = Θ(log ² 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)。

希望这可以帮助！