big-o - 递归关系 - 它是多少？

Question

我需要解决：T(n) = T(n-1) + O(1)

当我找到一般的 T(n) = T(nk) + k O(1) 它是什么总和？我的意思是当我达到基本情况时： nk=1; k=n-1 是“sum k, k=1 to n”吗？但是这个总和的结果是 n(n-1)/2，我知道结果是 O(n)。所以我知道我不需要这个关系的总和，但是对于这个递归关系，什么总和是正确的？

谢谢

Answer 1

如果我们做出（合理的）假设 T(0) = 0（或 T(1) = O(1)），那么我们可以应用您的
T(n) = T(n - k) + k⋅O(1 ) 到 k = n 并获得

T(n) = T(n - n) + n⋅O(1) = 0 + n⋅O(1) = O(n)。

编辑：如果您坚持将重复表示为总和，则为：

T(n) = T(n - 1) + O(1) = T(n - 2) + O(1) + O(1) = ... = Σ _{k = 1,...n} O(1 ) = n⋅O(1) = O(n)