[Python] EX 02 フィボナッチ数の生成関数

フィボナッチ数を生成する関数の計算速度を測定しました。メモ化再帰法が最速でした。

今の私の知識では反復法一択ですが、再帰的手法についてはこれから学んでいきます。

import time,datetime

def fib_A(n): # 反復法
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

def fib_B(n): # 再帰法
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib_B(n-1) + fib_B(n-2)

def fib_C(n, memo={}): # メモ化再帰法
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = fib_C(n-1, memo) + fib_C(n-2, memo)
        return memo[n]

if __name__ == '__main__':

    list_time = list()
    for function in [fib_A,fib_B,fib_C]:
        start = time.time()
        print(function)
        print(function(40))

        # 処理時間算出
        process_time = time.time() - start
        td = datetime.timedelta(seconds = process_time)

        list_time.append(td.microseconds)

    print(list_time)
--------------------------------------------------

出力
--------------------------------------------------
<function fib_A at 0x10743cf70>
63245986
<function fib_B at 0x107637040>
63245986
<function fib_C at 0x1076370d0>
63245986
[42, 549224, 35]