解決する必要があります: T(n) = T(n-1) + O(1)
一般的な T(n) = T(nk) + k O(1) を見つけたとき、それは何の合計ですか? つまり、基本ケースに到達したときです: nk=1; k=n-1 「k、k=1～nの合計」ですか？しかし、この合計の結果は n(n-1)/2 であり、結果が O(n) であることはわかっています。この関係では合計が必要ないことはわかっていますが、この再帰関係ではどの合計が正しいのでしょうか?
ありがとう
解決する必要があります: T(n) = T(n-1) + O(1)
一般的な T(n) = T(nk) + k O(1) を見つけたとき、それは何の合計ですか? つまり、基本ケースに到達したときです: nk=1; k=n-1 「k、k=1～nの合計」ですか？しかし、この合計の結果は n(n-1)/2 であり、結果が O(n) であることはわかっています。この関係では合計が必要ないことはわかっていますが、この再帰関係ではどの合計が正しいのでしょうか?
ありがとう