Pythonを用いてn番目のフィボナッチ数を求める処理の実行時間について

Pythonを用いて，効率的にn番目のフィボナッチ数を求める処理を考えて遊んでいたのですが，実行時間について分からないことが出来たのでご教示願います．

下記のコードには，3つの関数fib1, fib2, fib3があります．
いずれもn番目のフィボナッチ数を求める関数で，動的計画法を用いて（いるつもりで）います．
各関数の大雑把な説明はコメントに書いていますが，fib1とfib2の違いとしては，n-1を先に探索するのかn-2を先に探索するのかの違いだけです．

コードの後半の行では，各関数の実行時間を計測しているのですが，この時の結果がほぼ確実に，fib3 < fib2 < fib1になります．
微差なのかもしれないが，なぜfib1よりfib2の方が早くなるのでしょうか（fib1の方が再帰のネストが深くなるのが原因？）

OSはubuntu(wsl)で，python 3.8.0を使っています．

Pythonは不慣れで知識も少ないため，コードや質問が分かりづらいかもしれませんが，ご回答いただければ幸いです．

実行するコード

from time import time class Fibonacci: """再帰処理によってフィボナッチ数を求めるクラス.""" fib1_dict = {} # fib1()の辞書 fib2_dict = {} # fib2()の辞書 def fib1(n): """再帰処理でフィボナッチの辞書を作りながら計算する.""" if n < 2: return n # n-1が登録されてない場合 if n-1 not in Fibonacci.fib1_dict.keys(): Fibonacci.fib1_dict[n-1] = Fibonacci.fib1(n-1) # n-2が登録されてない場合 if n-2 not in Fibonacci.fib1_dict.keys(): Fibonacci.fib1_dict[n-2] = Fibonacci.fib1(n-2) return Fibonacci.fib1_dict[n-1] + Fibonacci.fib1_dict[n-2] def fib2(n): """再帰処理でフィボナッチの辞書を作りながら計算する.""" if n < 2: return n # n-2が登録されてない場合 if n-2 not in Fibonacci.fib2_dict.keys(): Fibonacci.fib2_dict[n-2] = Fibonacci.fib2(n-2) # n-1が登録されてない場合 if n-1 not in Fibonacci.fib2_dict.keys(): Fibonacci.fib2_dict[n-1] = Fibonacci.fib2(n-1) return Fibonacci.fib2_dict[n-1] + Fibonacci.fib2_dict[n-2] def fib3(n): """第0項から第n項まで順に計算する.""" if n < 2: return n num1 = 0 num2 = 1 tmp = 1 for i in range(1, n): tmp = num1 + num2 num1 = num2 num2 = tmp return tmp n = 400 t0 = time() ans1 = Fibonacci.fib1(n) t1 = time() t2 = time() ans2 = Fibonacci.fib2(n) t3 = time() t4 = time() ans3 = fib3(n) t5 = time() print(f'fib1({n})={ans1}: {t1 - t0} seconds.') print(f'fib2({n})={ans2}: {t3 - t2} seconds.') print(f'fib3({n})={ans3}: {t5 - t4} seconds.')

実行例

fib1(400)=省略: 0.0003783702850341797 seconds. fib2(400)=省略: 0.00022530555725097656 seconds. fib3(400)=省略: 3.361701965332031e-05 seconds.