1

我试图了解如何解决递归关系。我理解到我们必须简化的程度。

T(N) = T(N-1) + N-1              Initial condition: T(1)=O(1)=1
T(N) = T(N-1) + N-1
T(N-1) = T(N-2) + N-2
T(N-2) = T(N-3) + N-3
……
T(2) = T(1) + 1


**Summing up right and left sides**

T(N) + T(N-1) + T(N-2) + T(N-3) + …. T(3) + T(2) =

= T(N-1) + T(N-2) + T(N-3) + …. T(3) + T(2) + T(1) +

(N-1) + (N-2) + (N-3) + …. +3 + 2 + 1


** Canceling like terms and simplifying **

T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2

T(N) = 1 + N*(N - 1)/2

我真的不明白最后一部分。我了解取消类似条款，但不了解以下简化的工作原理：

T(N) = T(1) + (N-1) + (N-2) + (N-3) + …. +3 + 2 + 1
T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2

第二行是如何从第一行衍生出来的？对我来说没有任何意义。

如果有人可以帮助我理解这一点，那将是一个很大的帮助。谢谢 =)

4

2 回答 2

1

在你的倒数第二行：

 S = (N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1

你可以说：

2S = S + S
   = (N-1) + (N-2) + (N-3) + ... +   3   +   2   +   1
       1   +   2   +   3   + ... + (N-3) + (N-2) + (N-1)
   =   N   +   N   +   N   + ... +   N   +   N   +   N
       |__________________ N-1 times ________________|

你从N - 1到数1，所以N - 1序列中有项。但是整个序列就是N这样你可以说：

2S = N * (N - 1)
 S = (N * (N - 1)) / 2

所以在你的最后一块：

T(N) = T(1) + (N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1
     = T(1) + (N * (N - 1)) / 2
于 2012-06-02T03:41:21.467 回答
0 
T(N) = T(1) + (N-1) + (N-2) + (N-3) + …. +3 + 2 + 1
     = T(1) + (N-1) +  (N-2) + (N-3) + ..... + ( N-(N-3)) + (N-(N-2)) + (N-(N-1))
     = T(1) + [N+N+N+..... n-1 times] - [1+2+3+......+(N-3)+(N-2)+(N-1)]
     = T(1) + N*(N-1) - (N*(N-1))/2
     = T(1) + N*(N-1)/2
于 2012-06-02T03:50:55.727 回答