1. はじめに
この記事では、フィボナッチ数列を次の4つの方法で解く。
- 再帰
- 動的計画法（タビュレーション）
- 動的計画法（メモ化再帰）
- 行列累乗
再帰はもっとも単純だが非効率であり、動的計画法では計算量を $O(N)$ に削減できる。さらに、行列累乗を用いると $O(\log N)$ まで高速化できる。
フィボナッチ数列は、プログラミングの入門問題として頻繁に登場するが、その計算方法には複数のアプローチが存在する。
本記事では、これら4つの手法を取り上げ、それぞれの特徴と性能を比較・検討する。
2. フィボナッチ数列とは
フィボナッチ数列 $F_n$ は次の漸化式で定義される。
$$
F_{0} = 0, \quad F_{1} = 1, \quad F_{n} = F_{n-1} + F_{n-2} \quad (n \ge 2)
$$
3. 再帰による実装
もっとも素朴な実装の一つが、定義そのままを再帰で表すことである。
Python による実装を次に示す。
def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
この実装は単純で簡潔に書くことができるが、同じ計算を何度も繰り返すため、計算量は $O(2^N)$ となる。
4. 動的計画法
動的計画法はタビュレーションとメモ化の2種類があり、いずれの方法も計算量は $O(N)$ である。
4.1. 動的計画法（タビュレーション）
タビュレーションとは、下から順に値を表に埋めていく方法である。すでに求めた小さい問題の解を利用して、より大きい問題を解く。
Python による実装を次に示す。
def fib_tabulation(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1 # 初期化
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
時間計算量と空間計算量はともに $O(N)$ である。
しかしフィボナッチ数列は性質上、直前2項しか使用しないため、次のように書けば $O(1)$ の空間計算量で計算できる。
Python による実装を次に示す。
def fib_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
4.2. 動的計画法（メモ化再帰）
メモ化は再帰的に呼び出しながらすでに計算した結果を保存して再利用する方法である。考え方はタビュレーションと同じであるが、処理の流れは上から下となる。
Python による実装を次に示す。
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
# すでに計算されている場合は、値を再利用する
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
5. 行列累乗
フィボナッチ数列は、行列を用いて表すことができる。
フィボナッチ数列の $i$ 番目の値を $a_i$ とすると、$n$ 番目の項について次の関係式が成り立つ。
\begin{align}
\begin{pmatrix}
a_n \\
a_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n-1} \\
a_{n-2}
\end{pmatrix}
\end{align}
この関係を繰り返し適用すると、$a_n$ は次のようにあらわせる。
\begin{align}
\begin{pmatrix}
a_{n+1} \\
a_{n}
\end{pmatrix}
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n-1} \\
a_{n-2}
\end{pmatrix}
\\[4pt]
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} ^ 2
\begin{pmatrix}
a_{n-2} \\
a_{n-3}
\end{pmatrix}
\\[4pt]
&=
\vdots
\\[4pt]
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} ^ {n-1}
\begin{pmatrix}
a_{1} \\
a_{0}
\end{pmatrix}
\\[4pt]
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} ^ {n-1}
\begin{pmatrix}
1 \\
0
\end{pmatrix}
\end{align}
したがって、$2 \times 2$ 行列の $n - 1$ 乗を高速に求めればよい。これは繰り返し2乗法を用いることで、計算量を $O(\log N)$ に削減することができる。
5.1. 繰り返し2乗法
繰り返し2乗法は、累乗の計算の指数を2進数で分解することで、計算を高速化する手法である。
例えば、$2^{10}$ を普通に計算する場合は $2$ を 10 回掛ける必要がある。
しかし、繰り返し2乗法では次のようにして $O(\log N)$ 回の掛け算で求められる。
\begin{align}
2^{10} &= 2^{8} \times 2^{2} \\
&= ((2^{2})^{2})^{2} \times (2^{2}) \\
&= 1024
\end{align}
指数を2進数（$10 = 1010_{2}$）で表すと、掛け算すべき項（$2^8$ と $2^2$）を選ぶことで、不要な計算を省略し効率的に計算することができる。
一般的には、次の関係式を利用して累乗を半分に分解する。
\begin{align}
a^{2k} &= (a^2)^k \\
a^{2k+1} &= a \times (a^2)^k
\end{align}
これを繰り返すことで、指数を $n \to \lfloor n/2 \rfloor$ と半分ずつに減らせるため、計算量は $O(\log N)$ となる。
このアルゴリズムを行列に適用すると、行列のべき乗（行列累乗）も同様に $O(\log N)$ で計算できる。
5.2. Python による実装
Python での実装を次に示す。
def matmul(A, B):
"""2×2行列の掛け算"""
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0],
A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0],
A[1][0]*B[0][1] + A[1][1]*B[1][1]]
]
def matpow(A, n):
"""2×2行列 A の n 乗（二分累乗法）"""
res = [[1, 0], [0, 1]] # 単位行列
while n > 0:
if n & 1: # n が奇数なら res に A を掛ける
res = matmul(res, A)
A = matmul(A, A) # A を二乗
n >>= 1 # n を半分に
return res
def fib_matrix(n):
"""行列累乗によるフィボナッチ数列の計算"""
if n == 0:
return 0
M = [[1, 1], [1, 0]]
return matpow(M, n - 1)[0][0]
6. それぞれの手法の比較
ここでは、これまでに説明した手法の性能の違いについて、比較・検討する。
比較・検討するために、以下のテストを行う。
- テストケースとして $n = [1, 10, 100, 1000, 10000, 100000, 1000000]$ を使用する
- 各手法について、結果が返るまでの実行時間を計測する
なお、テストの実行時間が長くなりすぎる場合は、5秒を上限として計測を打ち切る。
6.1. Python によるテストの実装
Python によるテストに使用したコードを次に示す。
import time, signal
from functools import wraps
LIMIT = 5
class TimeoutException(Exception):
"""時間超過時に送出される例外"""
pass
def measure_time(limit=None):
"""実行時間を計測し、limit秒や再帰制限超過を検出するデコレータ"""
def decorator(func):
is_running = False # 再帰多重起動防止フラグ
def _handle_timeout(signum, frame):
raise TimeoutException(f"{func.__name__}: timeout (> {limit}s)")
@wraps(func)
def wrapper(*args, **kwargs):
nonlocal is_running
if is_running:
# 再帰内部では通常通り実行（計測しない）
return func(*args, **kwargs)
signal.signal(signal.SIGALRM, _handle_timeout)
if limit:
signal.alarm(limit)
start = time.time()
is_running = True
try:
result = func(*args, **kwargs)
elapsed = time.time() - start
print(f"{func.__name__}: {elapsed:.3e} 秒")
return elapsed
except TimeoutException as e:
print(e)
return None
except RecursionError:
print(f"{func.__name__}: RecursionError（計測不能）")
return None
except Exception as e:
print(f"{func.__name__}: Error - {e}")
return None
finally:
is_running = False
signal.alarm(0)
return wrapper
return decorator
"""
再帰による計算
"""
@measure_time(LIMIT)
def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
"""
タビュレーションによる計算
"""
@measure_time(LIMIT)
def fib_tabulation(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1 # 初期化
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
"""
タビュレーションによる計算（メモリ効率良）
"""
@measure_time(LIMIT)
def fib_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
"""
メモ化再帰による計算
"""
@measure_time(LIMIT)
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
# すでに計算されている場合は、値を再利用する
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
"""
行列累乗による計算
"""
def matmul(A, B):
"""2×2行列の掛け算"""
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0],
A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0],
A[1][0]*B[0][1] + A[1][1]*B[1][1]]
]
def matpow(A, n):
"""2×2行列 A の n 乗（二分累乗法）"""
res = [[1, 0], [0, 1]] # 単位行列
while n > 0:
if n & 1: # n が奇数なら res に A を掛ける
res = matmul(res, A)
A = matmul(A, A) # A を二乗
n >>= 1 # n を半分に
return res
@measure_time(LIMIT)
def fib_matrix(n):
"""行列累乗によるフィボナッチ数列の計算"""
if n == 0:
return 0
M = [[1, 1], [1, 0]]
return matpow(M, n - 1)[0][0]
# ===== 実験 =====
N_list = [1, 10, 100, 1000, 10000, 100000, 1000000]
funcs = [fib_recursive, fib_tabulation, fib_optimized, fib_memo, fib_matrix]
results = {f.__name__: [] for f in funcs}
for n in N_list:
print(f"\n==== n = {n} ====")
for func in funcs:
t = func(n)
results[func.__name__].append(t)
print("\n計測完了 ✅")
6.2. テストの実行結果
実行結果を次に示す。
==== n = 1 ====
fib_recursive: 2.146e-06 秒
fib_tabulation: 9.537e-07 秒
fib_optimized: 9.537e-07 秒
fib_memo: 1.192e-06 秒
fib_matrix: 4.053e-06 秒
==== n = 10 ====
fib_recursive: 8.702e-05 秒
fib_tabulation: 8.821e-06 秒
fib_optimized: 2.146e-06 秒
fib_memo: 1.574e-05 秒
fib_matrix: 1.645e-05 秒
==== n = 100 ====
fib_recursive: timeout (> 5s)
fib_tabulation: 3.362e-05 秒
fib_optimized: 1.240e-05 秒
fib_memo: 2.251e-04 秒
fib_matrix: 2.766e-05 秒
==== n = 1000 ====
fib_recursive: RecursionError（計測不能）
fib_tabulation: 2.754e-04 秒
fib_optimized: 1.125e-04 秒
fib_memo: RecursionError（計測不能）
fib_matrix: 6.652e-05 秒
==== n = 10000 ====
fib_recursive: RecursionError（計測不能）
fib_tabulation: 3.987e-03 秒
fib_optimized: 2.139e-03 秒
fib_memo: RecursionError（計測不能）
fib_matrix: 5.400e-04 秒
==== n = 100000 ====
fib_recursive: RecursionError（計測不能）
fib_tabulation: 8.960e-01 秒
fib_optimized: 1.785e-01 秒
fib_memo: RecursionError（計測不能）
fib_matrix: 1.575e-02 秒
==== n = 1000000 ====
fib_recursive: RecursionError（計測不能）
fib_tabulation: timeout (> 5s)
fib_optimized: timeout (> 5s)
fib_memo: RecursionError（計測不能）
fib_matrix: 5.771e-01 秒
計測完了 ✅
結果から、再帰による実装は $n = 100$ 付近からすでに計測不能となっている。これは、フィボナッチ数列の再帰実装が同じ計算を何度も繰り返すため、計算量が指数関数的に増加することによる。
また、メモ化再帰の結果についてもみると、メモ化は重複計算が解消されるため理論上は $O(N)$ で動作するが、再帰呼び出しの深さが増えすぎることで Python の再帰上限に達し、$n = 1000$ 付近から RecursionError によって停止している。
タビュレーション（DP） と空間計算量の $O(1)$ 最適化版 は再帰を使わないため安定して高速であり、大きな $n$ においても線形時間で計算が完了した。特に $O(1)$ 最適化版は、通常のタビュレーションよりも高速であることがわかる。
最後に、行列累乗計算では、$n = 1000000$ のような大規模な入力に対しても 1 秒未満で結果を返しており、$O(\log N)$ アルゴリズムの計算効率を示している。
7. まとめ
この記事では、4つの異なる手法によるフィボナッチ数列の計算方法と、その性能比較を行った。
| 手法 | 時間計算量 | 空間計算量 | 特徴 |
|---|---|---|---|
| 再帰関数 | $O(2^N)$ | $O(N)$ | 計算量が指数的に増加し、$n=100$ 付近で計測不能。 |
| メモ化再帰 | $O(N)$ | $O(N)$ | 重複計算は防げるが、再帰深度制限により $n \ge 1000$ で停止。 |
| DP（タビュレーション） | $O(N)$ | $O(N)$ | 高速だが、大規模入力ではメモリ使用量が増加する。 |
| DP（O(1)最適化） | $O(N)$ | $O(1)$ | 実装が簡潔で実用的。$n=10^5$ でも高速に動作。 |
| 行列累乗 | $O(\log N)$ | $O(1)$ | 最も高速。$n=10^6$ でも1秒未満で計算が完了。 |