第56天：Python 斐波那契第 n 项 – 超快 O(n) 迭代解法，O(1) 空间（无递归！）

Source: Dev.to

概览

欢迎来到 #80DaysOfChallenges 之旅的第 56 天！这个中等难度的挑战展示了在 Python 中计算第 n 项斐波那契数的最高效方法：线性时间的迭代循环，且空间复杂度为常数。它避免了朴素递归的指数级爆炸以及记忆化带来的内存开销，适用于非常大的 n（例如 10 000）。

该方法在实际项目、竞赛编程以及技术面试中被广泛使用，尤其在不允许递归或记忆化的情况下。

斐波那契数列示例

F₀ = 0，F₁ = 1，F₂ = 1，F₃ = 2，F₄ = 3，F₅ = 5，…

实现

def fibonacci(n: int) -> int:
    """Return the n‑th Fibonacci number.

    Args:
        n: A non‑negative integer.

    Raises:
        ValueError: If n is negative.
    """
    if n < 0:
        raise ValueError("n must be a non‑negative integer")

    if n == 0:
        return 0
    if n == 1:
        return 1

    # Track the two most recent numbers
    prev = 0  # F(n‑2)
    curr = 1  # F(n‑1)

    for _ in range(2, n + 1):
        next_value = prev + curr
        prev = curr
        curr = next_value

    return curr

关键要点

• 常数空间 – 只存储两个变量（prev、curr）。
• 线性时间 – 从 2 循环到 n，只遍历一次。
• 无递归 – 消除了栈溢出的风险。
• 错误处理 – 验证 n 为非负整数。

使用示例

raw = input("Enter n (non‑negative integer): ").strip()

if raw == "":
    print("No input provided. Exiting.")
else:
    n = int(raw)
    result = fibonacci(n)
    print(f"Fibonacci number F{n} =", result)

运行脚本并输入 n = 10 时得到：

Fibonacci number F10 = 55

该实现可以轻松扩展到极大的数值（例如 n = 1000，瞬间完成）。

高级替代方案

• 矩阵快速幂 – O(log n) 时间。
• Binet 公式 – 使用浮点运算并进行四舍五入。
• 生成器 – 惰性产生无限斐波那契序列。

对于绝大多数实际场景，迭代的 O(n) / O(1) 解法是最优选择。

结论

第 56 天提供了在 Python 中最快的实用斐波那契实现。欢迎尝试更大的输入并分享你的结果！