はじめに

フィボナッチ数列は、有名な数列の１つで、次のように定義されます。

$$F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)(n≥2)$$

フィボナッチ数列は数学やプログラミングの基礎として、多くの場面で登場します。この記事では、Pythonを使ってフィボナッチ数列をいくつかの異なる方法で実装し、その効率やコードの違いを比較します。

1. 再帰的アプローチ

再帰関数の題材として、フィボナッチ数列はよく取り上げられます。再帰関数を使って実装すると、コードの記述量が短くて済むメリットがある一方で、Nが大きい場合、計算時間が長くなります。

fibonacci_recursive.py

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 (動的計画法) によるアプローチが推奨されています。

fibonacci_dp.py

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))の計算のアルゴリズム

これを用いることで、行列の累乗部分を高速化することができ、計算量を対数時間にすることができました。実装は以下の通りです。

fibonacci_matrix.py

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

ソースコード

再帰

main.py

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))

動的計画法

main.py


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))

行列

main.py

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)を得ており、非常に短い実行時間だった。

この記事が、フィボナッチ数列の理解や実装に役立つことを願っています。皆さんもぜひ、これらのアプローチを試してみてください！

最後に

この記事が初投稿なので、色々おかしなところがあるかもしれませんが、その時はコメントで優しく教えてください。ここまで読んでいただきありがとうございました。