再帰的なプログラムの時間計算量

f(n) = f(n-1) + f(n-2)
とあるばあい、o(n^2)になる理由がわからない

No.2 回答者： tknakamuri 回答日時： 2023/11/21 10:15

f(1)=f(2)=1 は既知として、単純にf(n)をそこまで式を展開してゆくと

項数も計算結果もフィボナッチ数列のn番目の値になって
O(n^2)ではない。

また、展開せずに f(3)から順に計算するだけなら
計算量はO(n) だろうし・・・・

まずO(n^2)が何に対する話なのか説明してください。

No.1 回答者： ありものがたり 回答日時： 2023/11/20 19:22

何が o(n^2) だって話をしているんだろう？

漸化式 f(n) = f(n-1) + f(n-2) で与えられる f(n) の値なら、o(n^2) ではない。
f(n) を求める計算量ならば、 f(1), f(2) の値から始めて
漸化式を n-2 回適用すれば求まるから、計算量は O(n) であって
o(n^2) のうちでもある。