フィボナッチ数列
更新日:
用語解説
フィボナッチ数列は、直前の二つの項を足して次の項を作る数列です。0、1、1、2、3、5、8、…と続きます。
■ 試験で押さえるポイント
定義どおりに再帰で計算すると、同じ計算を何度も繰り返して時間が指数的に増えます。
途中の結果を保存する（動的計画法）と、O（n）で計算できます。
隣り合う項の比は、黄金比（約1.618）に近づきます。
■ 選択肢での判断ポイント
単純な再帰と動的計画法で計算量が大きく異なる点がよく問われます。初項の取り方（0から始めるか）も確認します。