斐波那契数列

Python计算斐波那契数列

斐波那契数列是一个经典的数学问题，定义如下：

• ( F(0) = 0 )
• ( F(1) = 1 )
• ( F(n) = F(n-1) + F(n-2) )，对于 ( n \geq 2 )

1. 递归方法

递归方法是最直观的实现方式，但它的时间复杂度较高，为 ( O(2^n) )，因为存在大量的重复计算。

示例代码

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# 测试
n = 10
print(f"Fibonacci({n}) using recursion: {fibonacci_recursive(n)}")

输出

Fibonacci(10) using recursion: 55

2. 循环方法

循环方法通过迭代计算斐波那契数列，避免了递归中的重复计算，时间复杂度为 ( O(n) )。

示例代码

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 测试
n = 10
print(f"Fibonacci({n}) using iteration: {fibonacci_iterative(n)}")

输出

Fibonacci(10) using iteration: 55

3. 矩阵乘法方法（通过NumPy调用SIMD指令）

矩阵乘法方法利用斐波那契数列的矩阵表示形式，通过快速幂算法可以在 ( O(\log n) ) 时间内计算出斐波那契数列的第 ( n ) 项(一阶线性递推可以改为矩阵乘法)。

矩阵表示

斐波那契数列可以表示为矩阵的幂：
[ \begin{pmatrix} F(n+1) \ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F(1) \ F(0) \end{pmatrix} ]

快速幂算法

快速幂算法用于高效计算矩阵的幂。

示例代码

首先，确保你已经安装了 NumPy 库。如果没有安装，可以使用以下命令安装：

pip install numpy # 没有配置镜像源需要添加-i参数

然后，使用以下代码实现斐波那契数列的矩阵乘法方法：

import numpy as np

def fibonacci_matrix(n):
    if n<=1:
        return 1

    matrix = np.array([[1, 1], [1, 0]], dtype=int)
    base=np.array([1,0]).reshape(2,1)
    result=np.linalg.matrix_power(matrix,n)@base
    
    return result[0,0]

# 测试
n = 10
print(f"Fibonacci({n}) using matrix multiplication with NumPy: {fibonacci_matrix(n)}")

输出

Fibonacci(10) using matrix multiplication with NumPy: 55

4. 通项公式方法

斐波那契数列有一个闭合形式的通项公式，称为 Binet 公式：
[ F(n) = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}} ]
其中 ( \phi = \frac{1 + \sqrt{5}}{2} ) 是黄金比例。

示例代码

import math

def fibonacci_formula(n):
    phi = (1 + math.sqrt(5)) / 2
    return int((phi**n - (-phi)**(-n)) / math.sqrt(5))

# 测试
n = 10
print(f"Fibonacci({n}) using the formula: {fibonacci_formula(n)}")

输出

Fibonacci(10) using the formula: 55

总结

• 递归方法：直观但效率低，时间复杂度为 ( O(2^n) )。
• 循环方法：避免了重复计算，时间复杂度为 ( O(n) )。
• 矩阵乘法方法（使用 NumPy）：利用矩阵表示和快速幂算法，时间复杂度为 ( O(\log n) )，效率最高。
• 通项公式方法：使用闭合形式的公式直接计算，时间复杂度为 ( O(1) )，但可能因浮点数精度问题导致误差。