復發關係 - 它是什麼總數？

Question

我需要解決：T（N）= T（N-1）+ O（1）

當我找到的一般T（N）= T（NK）+ K O（1） 什麼總和是嗎？我的意思是當我到達基本情況時：n-k = 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）=上）。

編輯：如果堅持代表復發的總和，在這裏它是：

T（N）= T（N - 1）+ O（1）= T（N - 2）+ O （1）+ O（1）= ... =Σ _{k = 1，... n} O（1）=n⋅O（1）= O（n）