再帰とメモ化によるFibonacci
メモ化は以前に計算した戻り値をキャッシュします。
再帰とメモ化によるFibonacciとは？
メモ化は以前に計算した戻り値をキャッシュします。
同じFibonacci値の再計算を防ぎます。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
サンプルコード
main.py
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))期待される出力
55仕組み
素朴な指数時間をO(n)へ改善し、O(n)のメモリを使います。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。