masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

アルゴリズムとデータ構造(けんちょん本)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)

として、標準入力から第何項を求めるか入力させる形とした。k=50とすると手元の環境(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)

メモ化して実行するとk=50としても0.00018秒程度で結果が返ってきた。メモ化すごい。

計算量

メモ化した場合の計算量はO(N)と思われる。
メモ化しない場合の計算量はいくつだろう?(章末問題4.3をやります)