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

Question

我被要求解决那个递归关系。我得到了下一个解决方案：https://imgur.com/a/xWoTI40

所以我决定问问我的老师是否正确。他告诉我不是；这是正确的解决方案：https://imgur.com/a/CGD0ta8

我现在完全没有头绪。我最多尝试理解为什么我的错误；最多我觉得其实是对的

有人可以解释一下吗？

Answer 1

您的解决方案是正确的。这是具有相同结果的不同方法：

t(1) = 0 (given)
t(2) = t(1) + 1 = 1
t(3) = t(2) + 2 = 1 + 2 = 3
t(4) = t(3) + 3 = 1 + 2 + 3 = 6
...
t(n) = 1 + 2 + ... + (n-1) = n * (n - 1) / 2 = Theta(n^2).

老师的解法在第二个=符号之后就错了。这是老师写的：

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

但实际上以下是正确的：

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

这正是您所得到的。看来老师丢了一个 n 学期。

事实上，老师的解决方案以-n^2的主导项结束，这显然是错误的，因为t(n) >= 0对所有n >= 0。

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

Solving a Recurrence Relation: T(n) = T(n-1) + n-1

algorithm

recurrence