アルゴリズムとデータ構造(けんちょん本)4.1,4.2
トリボナッチ数列を計算するプログラム
メモ化なし
import time def tori(n): if n == 1: return 0 if n == 2: return 0 if n == 3: return 1 return tori(n-1) + tori(n-2) + tori(n-3) k = int(input()) memo = [-1 for _ in range(k+1)] start = time.time() print(tori(k)) print(time.time() - start)
として、標準入力から第何項を求めるか入力させる形とした。とすると手元の環境(Google colab)ではしばらく待っても終了しなかった。
メモ化あり
#import sys #sys.setrecursionlimit(100000) def tori(n): if n == 1: return 0 if n == 2: return 0 if n == 3: return 1 if memo[n] == -1: memo[n] = tori(n-1) + tori(n-2) + tori(n-3) return memo[n] k = int(input()) memo = [-1 for _ in range(k+1)] start = time.time() print(tori(k)) print(time.time() - start)
メモ化して実行するととしても0.00018秒程度で結果が返ってきた。メモ化すごい。
計算量
メモ化した場合の計算量はと思われる。
メモ化しない場合の計算量はいくつだろう?(章末問題4.3をやります)