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

Question

我从之前对这个问题的回答中看到，这个人给出了：

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

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

T(n) = T(n-k) +kn - k(k-1)/2

我没有完全理解第三行。我可以看到他们可能是从 1/2n(n+1) 的等差级数公式求和得出的？但是他们是怎么得到kn和k(k-1)/2前面的负号的呢？

Answer 1

k(k-1)/2 项只是数字 0 到 k-1 的总和。您可以看到为什么需要从以下计算中减去它：

T(n) = 
T(n-k) + n + (n-1) + (n-2) + ... + (n-(k-1)) =
T(n-k) + (n-0) + (n-1) + (n-2) + ... + (n-(k-1)) =
T(n-k) + n + n + n + ... + n - 0 - 1 - 2 ... - (k-1) =
T(n-k) + kn - (0 + 1 + 2 + ... + (k-1)) =
T(n-k) + kn - k*(k-1)/2

Answer 2

如果你仔细观察：

T(n) = T(n-2) + n-1 + n = T(n-2) + 2n -1
T(n)= T(n-3) + n-2 + n-1 + n = T(n-3)+ 3n -(2+1) 
.
.
.
T(n)= T(n-k) + n-(k-1) + n-(k-2) + ... + n = T(n-k) + K * n + (-1 -2 - ... -(k-2) -(k-1))= T(n-k) + kn - k(k-1)/2

可以用递归定理来证明

Answer 3

开始于：

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

我们可以改写如下：

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

第二个公式表示：

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

让我们按照与第一个相同的方式转换它：

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

通过展开更多项，我们注意到在递归 term:T(n-3) 中从 n 中减去的数字始终与乘以 n 的数字相同。我们可以改写如下：

T(n) = T(n-k)+kn+...

我们还注意到 -2 -1 是算术级数，但取反并从 k-1 开始。 k-1 的算术是 (k-1)*k/2 就像 n(n+1)/2。所以关系是

T(n) = T(n-k)+kn-(k-1)*k/2 or T(n) = T(n-k)+kn-k*(k-1)/2

希望对您有所帮助 ;)

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

Solving recurrence relation T(n) = T(n-1) + n

iteration

recurrence

relation