07 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，从0项开始）。斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

示例：

输入: 0, 输出: 0
输入: 1, 输出: 1
输入: 5, 输出: 5
输入: 10, 输出: 55

解题思路

方法一：递归

缺点：时间复杂度高O(2^n)，存在大量重复计算

方法二：动态规划（迭代）

核心思想：自底向上计算，保存中间结果。

时间复杂度：O(n) 空间复杂度：O(n)

方法三：迭代优化

核心思想：只需要保存前两个值，空间复杂度优化到O(1)。

时间复杂度：O(n) 空间复杂度：O(1)

方法四：矩阵快速幂

核心思想：利用矩阵乘法的性质，将时间复杂度降到O(log n)。

Python 实现

# 方法一：递归（不推荐）
def fibonacci_recursive(n):
    """
    递归解法（不推荐，效率低）
    """
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


# 方法二：动态规划
def fibonacci_dp(n):
    """
    动态规划解法
    """
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


# 方法三：迭代优化
def fibonacci(n):
    """
    迭代解法，空间优化到O(1)
    """
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b


# 方法四：矩阵快速幂
def fibonacci_matrix(n):
    """
    矩阵快速幂解法，时间复杂度O(log n)
    """
    if n <= 1:
        return n

    def matrix_multiply(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_pow(a, power):
        result = [[1, 0], [0, 1]]  # 单位矩阵
        while power:
            if power & 1:
                result = matrix_multiply(result, a)
            a = matrix_multiply(a, a)
            power >>= 1
        return result

    base = [[1, 1], [1, 0]]
    result = matrix_pow(base, n - 1)
    return result[0][0]


# 测试代码
if __name__ == "__main__":
    for i in range(11):
        print(f"F({i}) = {fibonacci(i)}")

# 输出:
# F(0) = 0
# F(1) = 1
# F(2) = 1
# F(3) = 2
# F(4) = 3
# F(5) = 5
# F(6) = 8
# F(7) = 13
# F(8) = 21
# F(9) = 34
# F(10) = 55

图解

斐波那契数列定义:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), n >= 2

计算过程:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...