確定重複關係的運行時間T（n）= T（n-1）+ n

-1

如何確定輸入大小爲n的算法的滿足遞歸關係的算法的運行時間（以Big-Theta表示）T(n) = T(n-1)+n其中n >= 1和初始條件T(1) = 1？確定重複關係的運行時間T（n）= T（n-1）+ n

編輯：我練了過去的答卷。被困在這個問題上。需要指導

2015-11-05 Eninfo

不，這不是一門功課的問題。這是我在過去的考試中提出的一個問題，作爲將來考試的準備。我只是被困在這個問題上。 – Eninfo

看看這樣說：T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n。這意味着如果n> = 1，那麼你將得到類似T（N）= 1 + 2 + 3 + ... + N。如果你的工作本系列的模式，你會看到(n+1)n/2。因此，Ө(n^2)

來源

2015-11-05 11:04:23 Akrytek

謝謝！這很有幫助！ – Eninfo

確定重複關係的運行時間T（n）= T（n-1）+ n

回答

相關問題