algorithm - 解决递归关系 : 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。