展开递归递归关系

Question

我找不到我的问题的解决方案，因为通常解决方案（大 Os 术语）是所要求的，而不是展开的重复。如果已经有人问了，请告诉我，我会删除。

我在 uni 的算法和数据结构测试中遇到了这个问题，我一直在努力解决这个问题。主要是因为我不明白我是如何得出正确答案的。

我有以下关系：

T(1)=2
T(n)=2T(n-1)+2 for n>=2

答案是：

1. T(n)= 2^n+1 -2
2. T(n)= none of the answers are correct 
3. T(n)= 1/2n(n+1)-1 
4. T(n)= 2^n+1 -2-n
5. T(n)= n+ (-1)^n

这是我试过的：

T(1)=2
T(n)=2T(n-1)+2 -> T(n-1) = T(n-2)+2 
    =2T(n-2)+2+2 
    =2T(n-2)+4 -> T(n-2) = T(n-3)+3 
    =2T(n-3)+2+4 
    =2T(n-3)+6 so then -> 2T(n-k)+2k and if n=k 2T(n-n)+2n -> 2T(0)+2n

但我没有 T(0) 案例。此外，这种方法最终会让我了解大 O 解决方案，尽管这不是我现在想要找到的。

谁能给我解释一下获得正确答案的正确方法？

谢谢。

Answer 1

这个问题与https://cs.stackexchange.com/questions/18900/how-do-i-show-tn-2tn-1-k-is-o2n

相似

你可能也明白如何解决这个问题...

Answer 2

不要展开答案，只检查它们。

因此，对于每个可能的答案，检查是否 T(1)=2，以及是否替换给定的 T(n) 给出 T(n)=2T(n-1)+2 的相等性。所以对于第一个答案T(1)=2^(n+1)-2=4-2=2（应该是）和：

T(n) =?= 2*T(n)+2
2^(n+1)-2 =?= 2*(2^(n)-2)+2

使用简单的=?= 表示要检查的相等性。简化双方导致：

2^(n+1)-2 =?= 2*2^(n)-2

剩下的交给你

Answer 3

T(n)=2T(n-1)+2 等价于 T(n)+2 = 2(T(n-1)+2).

所以 T(n)+2 = 2^(n-1)(T(1)+2) = 2^(n-1)*4 = 2^(n+1)。因此 T(n) = 2^(n+1)-2.

Answer 4

简单的方法是注意它是指数的，然后只检查两个指数答案...

但是如果你想展开它，你会得到：

T(n) = 2 + 2T(n-1)
     = 2 + 4 + 4T(n-2)
     = 2 + 4 + 8 + 8T(n-3)
     = 2 + 4 + 8 + ... + 2^(n-1)T(1)
     = 2 + 4 + 8 + ... + 2^n

然后您识别进度并执行：

T(n) = 2T(n) - T(n)
     = 2^(n+1) - 2

展开递归递归关系

Unrolling recursive recurrence relations

algorithm

recursion

big-o

relation

recurrence