我无法理解重复的概念。鉴于你有你T(n) = 2T(n/2) +1
如何计算这种关系的复杂性?我知道在合并排序中,关系是T(n) = 2T(n/2) + cn
,你可以看到你有一个深度为 log2^n 和 cn 在每个级别工作的树。但是我不确定如何在给定通用功能的情况下继续进行。任何可用的教程可以清楚地解释这一点?
问问题
71 次
1 回答
2
递归的解决方案是 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 2 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。
于 2013-03-06T07:04:16.393 回答