はじめに
フィボナッチ数列は、有名な数列の１つで、次のように定義されます。
$$F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)(n≥2)$$
フィボナッチ数列は数学やプログラミングの基礎として、多くの場面で登場します。この記事では、Pythonを使ってフィボナッチ数列をいくつかの異なる方法で実装し、その効率やコードの違いを比較します。
1. 再帰的アプローチ
再帰関数の題材として、フィボナッチ数列はよく取り上げられます。再帰関数を使って実装すると、コードの記述量が短くて済むメリットがある一方で、Nが大きい場合、計算時間が長くなります。
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
n = int(input())
print(fibonacci_recursive(n))
2. 動的計画法によるアプローチ
再帰を使わずに、動的計画法を用いて効率的に計算することもできます。LeetCodeの509. Fibonacci Numberという問題では、Dynamic Programming (動的計画法) によるアプローチが推奨されています。
def fibonacci_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
n = int(input())
print(fibonacci_dp(n))
3. 行列を使ったアプローチ
行列を使うことで、対数時間での計算が実現できます。
冒頭でも述べた通り、フィボナッチ数列は$$F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)(n≥2)$$の形で表すことができます。これを漸化式の形で表すと、$$a_{n+2} = a_{n+1} + a_n$$となります。これを行列を用いて、以下の様に表すことができます。
$$
\begin{pmatrix}
a_{n+2} \\
a_{n+1}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \\ 1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n+1} \\ a_n
\end{pmatrix}
$$
したがって、
$$
\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} \\ &=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} ^2
\begin{pmatrix}
a_{n-2} \\
a_{n-3}
\end{pmatrix} \\
&= \cdots \\ &=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} ^ {n - 1}
\begin{pmatrix}
a_1 \\
a_0
\end{pmatrix}
\end{align}
$$
フィボナッチ数列の定義より、$a_1 = 1, a_0 = 0$であるので、
$$
\begin{pmatrix}
a_{n} \\
a_{n-1}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} ^ {n - 1}
\begin{pmatrix}
1 \\
0
\end{pmatrix}
$$
ここで、$ A =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
$とすると、$A^{n - 1}$を計算して $ A[0][0] $を返せば求めることができます。（行列の定義より、$a_n = A[0][0] × a_1 + A[0][1] × a_0 $ となり、$ a_1 = 1, a_0 = 0 $ より、$ A[0][0] $ が $a_n$の答えになります。）
累乗計算の高速化
フィボナッチ数列を行列で表すことができるのを説明しましたが、今のままでは計算量は $O(N)$のままであり、対数時間にすることが出来ていません。では、どうすれば高速化することが出来るでしょうか?
繰り返し2乗法
繰り返し2乗法は下記サイトで、詳しく説明されています。ご覧ください。
繰り返し二乗法によるべき乗(pow(x,n))の計算のアルゴリズム
これを用いることで、行列の累乗部分を高速化することができ、計算量を対数時間にすることができました。実装は以下の通りです。
class FibonacciMatrix:
def __init__(self, n):
self.n = n
def multiply_matrices(self, A, B):
"""行列 A と B を掛け算し、結果を返します。"""
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 matrix_exponentiation(self):
"""行列の累乗を計算し、結果を返します。"""
result = [[1, 0], [0, 1]]
base = [[1, 1], [1, 0]]
exponent = self.n - 1
while exponent > 0:
if exponent & 1:
result = self.multiply_matrices(result, base)
base = self.multiply_matrices(base, base)
exponent >>= 1
return result[0][0]
N = int(input())
fib_matrix = FibonacciMatrix(N)
result = fib_matrix.matrix_exponentiation()
print(result)
実際に上記3つの方法で問題を解いてみる。
今回使用する問題はこちら。また、コンパイラは Python(CPython 3.11.4) と Python(PyPy 3.10-v7.3.12) の両方で試してみます。
競技プログラミングの鉄則より B28 - Fibonacci Easy
ソースコード
再帰
import sys
sys.setrecursionlimit(10000)
MOD = 1000000007
def fibonacci_recursive(n):
if n <= 1:
return n % MOD
return (fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)) % MOD
n = int(input())
print(fibonacci_recursive(n))
動的計画法
MOD = 1000000007
def fibonacci_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
return dp[n]
n = int(input())
print(fibonacci_dp(n))
行列
class FibonacciMatrix:
MOD = 10**9 + 7
def __init__(self, n):
self.n = n
self.base_matrix = [[1, 1], [1, 0]]
def _multiply_matrices(self, A, B):
"""行列 A と B を掛け算し、結果を返します。"""
return [
[
(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % self.MOD,
(A[0][0] * B[0][1] + A[0][1] * B[1][1]) % self.MOD
],
[
(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % self.MOD,
(A[1][0] * B[0][1] + A[1][1] * B[1][1]) % self.MOD
]
]
def _matrix_exponentiation(self):
"""行列の累乗を計算し、結果を返します。"""
result = [[1, 0], [0, 1]]
base = self.base_matrix
exponent = self.n - 1
while exponent > 0:
if exponent & 1:
result = self._multiply_matrices(result, base)
base = self._multiply_matrices(base, base)
exponent >>= 1
return result[0][0]
def main():
N = int(input())
fib_matrix = FibonacciMatrix(N)
result = fib_matrix._matrix_exponentiation()
print(result)
if __name__ == '__main__':
main()
Python(CPython 3.11.4) と Python(PyPy 3.10-v7.3.12)
結果
| 手法 | Python(CPython 3.11.4) | Python(PyPy 3.10-v7.3.12) |
|---|---|---|
| 再帰 | 実行時エラー（RE） | 実行時エラー（RE） |
| DP | 正解（AC） / 実行時間: 1080ms | 正解（AC） / 実行時間: 140ms |
| 行列 | 正解（AC） / 実行時間: 10ms | 正解（AC） / 実行時間: 56ms |
まとめ
この記事では、フィボナッチ数列を異なるアプローチで実装し、それぞれの手法の効率や、実行時間を比較しました。以下にそれぞれのアプローチの特徴をまとめます。
1. 再帰的アプローチ:
・簡潔な実装が可能だが、計算量が指数的になり、大きな入力に対しては実行時間が長くなる。
・結果：CPythonとPypyの両方で実行時エラーが出てしまった。
2. 動的計画法(DP):
・メモリを使って部分問題を解決しながら、全体の問題を効率的に解決する。計算量は線形で、再帰と比較すると、実行時間も短くなる。
・結果：両方の環境で正解(AC)を得ており、特にPypyでは実行時間が短い結果となった。
3. 行列を使ったアプローチ:
・行列を用いることで、繰り返し2乗法が適用でき、対数時間でフィボナッチ数列を計算することができる。
・結果：両方の環境で正解(AC)を得ており、非常に短い実行時間だった。
この記事が、フィボナッチ数列の理解や実装に役立つことを願っています。皆さんもぜひ、これらのアプローチを試してみてください！
最後に
この記事が初投稿なので、色々おかしなところがあるかもしれませんが、その時はコメントで優しく教えてください。ここまで読んでいただきありがとうございました。