递归关系: T(n) = T(n - 1) +n-1

Question

我正在尝试理解如何解决递归关系。我理解这一点，我们必须简化。

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

我真的不明白最后一部分。我理解取消like术语，但不理解下面的简化是如何工作的：

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

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

如果有人能帮我理解这一点，那就太好了。谢谢=)

Answer 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

Answer 2

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