フィボナッチ数列の計算回数

atCoderでフィボナッチ数列の類似問題に躓いたのでメモ

素直な実装（no_memo.py）

何も考えずに再起関数で実装
N > 30くらいからもっさりする

import sys


# 再起上限を増やす
sys.setrecursionlimit(10**8)


# 入力受け取り
N = int(input())
# 再帰回数を記録する変数
c = 0



def fibo(n):
    global c
    c += 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)



print("f_n    :", fibo(N))
print("count  :", c)

改善した実装(memo.py)

途中で計算した項を記録して呼び出すように改善（メモ化再帰というらしい）
めちゃくちゃ速い

import sys


# 再起上限を増やす
sys.setrecursionlimit(10**8)


# 入力受け取り
N = int(input())
# 再帰回数を記録する変数
c = 0


# 計算結果を記録する配列
rec = [0] * (N + 1)
# 計算済みか記録する配列
done = [False] * (N + 1)


# N = 0, 1を与える
rec[0] = 0
done[0] = True
if N > 0:
    rec[1] = 1
    done[1] = True



def fibo(n):
    global c
    c += 1
    if done[n]:
        return rec[n]
    else:
        rec[n] = fibo(n - 1) + fibo(n - 2)
        done[n] = True
        return rec[n]



print("f_n   :", fibo(N))
print("count :", c)

計算回数を考察

N = 10 までの計算回数のグラフが下図

メモ化の場合

1. 初回の呼び出しで1回
2. fibo(n-1) の計算で count(n-1) 回
3. fibo(n-2) の計算で配列から呼び出すので1回

よって、
count(n) = count(n-1) + 2
となり、計算回数はおよそ 2N 回だとわかる。

一方でメモ化しない場合

1. 初回の呼び出しで1回
2. fibo(n-1) の計算で count(n-1) 回
3. fibo(n-2) の計算で count(n-2) 回

よって、
count(n) = count(n-1) + count(n-2) + 1
となる。フィボナッチ数列が出てきた。
初項が1で、nが増えるごとに1ずつ加算されていくため、一般的なフィボナッチ数列よりだいぶ速いペースでインフレする。

試しに no_memo.py で N = 40 を計算すると、カウントは3億回を超えていた。
怖い

最後に

幅優先探索がむずくて、馴染みのある問題に手を付けたがこちらもむずかった。
メモ化の発想はすぐに思いつけたので、計算回数を考える意識をつけなければと思った。

次の目標はBFSとDFSをしっかり理解して、素直な実装なら何も見ずに書けるようになること。
あと、ブログのコードブロックの見た目を考える。

手を動かさなければ。

以上