大门|大门-CS-2004 |问题90

递推方程

T(1) = 1
T(n) = 2T(n - 1) + n, n ≥ 2 

评估为

a、 二, ⁿ⁺¹ –n–2 b、 二, ^N –n c、 二, ⁿ⁺¹ -2n-2 d、 二, ^N +n （A） A. （B） B （C） C （D） D 答复: （A） 说明： 如果画递归树，我们可以注意到总的工作量是， T（n）=n+2（n-1）+4（n-2）+8（n-3）+2 ^n-1 *（n-n+1） T（n）=n+2（n-1）+4（n-2）+8（n-3）+2 ^n-1 * 1

为了解这个级数，让我们使用我们学校的技巧，我们将T（n）乘以2，然后在变换项后减去。

2*T(n) =     2n + 4(n-1) + 8(n-2) + 16(n-3) + 2n 
  T(n) = n + 2(n-1) + 4(n-2) + 8(n-3) + 2n-1 * 1

我们得到

2T(n) - T(n) =  -n + 2 + 4 + 8 + ..... 2n
T(n) = -n + 2n+1 - 2 [Applying GP sum formula for 2, 4, ...]
     = 2n+1 - 2 - n

Alternate Way to solve is to use hit and try method.
Given T(n) = 2T(n-1) + n and T(1) = 1

For n = 2, T(2) = 2T(2-1) + 2 
                = 2T(1) + 2 
                = 2.1 + 2 = 4

Now when you will put n = 2 in all options, 
only 1st option 2^(n+1) - n - 2 satisfies it. 

这个问题的小测验