recursion - 计算重复的复杂度

Question

我无法理解重复的概念。鉴于你有你T(n) = 2T(n/2) +1如何计算这种关系的复杂性？我知道在合并排序中，关系是T(n) = 2T(n/2) + cn，你可以看到你有一个深度为 log2^n 和 cn 在每个级别工作的树。但是我不确定如何在给定通用功能的情况下继续进行。任何可用的教程可以清楚地解释这一点？

Answer 1

递归的解决方案是 T(n) ∈ Θ(n)。

让我们扩展公式：

• T(n) = 2*T(n/2) + 1。（给定）
• T(n/2) = 2*T(n/4) + 1。（将 n 替换为 n/2）
• T(n/4) = 2*T(n/8) + 1。（将 n 替换为 n/4）
• T(n) = 2*(2*T(n/4) + 1) + 1 = 4*T(n/4) + 2 + 1。（替代）
• T(n) = 2*(2*(2*T(n/8) + 1) + 1) + 1 = 8*T(n/8) + 4 + 2 + 1。（替代）

并做一些观察和分析：

• 我们可以看到出现了一个模式：T(n) = 2 ^k * T(n/2 ^k ) + (2 ^k − 1)。
• 现在，让 k = log ₂ n。那么 n = 2 ^k。
• 代入，我们得到：T(n) = n * T(n/n) + (n - 1) = n * T(1) + n - 1。
• 对于至少一个 n，我们需要给 T(n) 一个具体的值。所以我们假设 T(1) = 1。
• 因此，T(n) = n * 1 + n - 1 = 2*n - 1，在 Θ(n) 中。

资源：

• https://www.cs.duke.edu/courses/spring05/cps100/notes/slides07-4up.pdf
• http://www.cs.duke.edu/~ola/ap/recurrence.html

但是，对于日常工作，解决这些递归的正常方法是使用Master theorem。