求第n个斐波那契数的动态规划算法时间与空间复杂度疑问

先看你给出的算法代码：

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
        return currentFib

你的困惑和维基结论的差异，核心在于算法复杂度分析的标准假设 vs 实际大数运算的开销，分两点解释：

1. 时间复杂度：O(n) vs O(n²) #

• 算法复杂度分析的常规逻辑：默认所有基本操作（比如整数加法、变量赋值）都是固定时间的O(1)操作，不管数值本身的大小。这个算法里循环执行了n-1次，每次循环的操作都是O(1)，所以总时间复杂度是O(n)——这就是维基给出结论的依据。
• 你提到的加法成本随n上升，是因为斐波那契数是指数增长的，第n个斐波那契数的二进制位数是O(n)级别的。如果考虑大数加法的实际执行时间（每一位都要计算），那每次加法的成本是O(n)，n次循环下来总时间就是O(n²)。但这种属于更底层的实现级分析，不是算法复杂度分析的标准范畴。

2. 空间复杂度：O(1) vs O(n) #

• 常规算法复杂度分析里，空间复杂度关注的是算法所需的额外变量数量，而非单个变量的物理存储大小。这个算法全程只用到了previousFib、currentFib、newFib三个变量，不管n多大，变量的数量都是固定的，所以空间复杂度是O(1)。
• 你考虑的是单个斐波那契数的存储空间（位数O(n)），这属于实际运行时的物理内存开销，但不是算法复杂度分析中“空间复杂度”的定义。如果按物理存储算，确实是O(n)，但这不是常规分析的结论。

简单说：两种结论都对，只是基于的分析框架不同——维基用的是算法分析的标准假设，而你考虑了大数运算的实际细节。

内容的提问来源于stack exchange，提问作者Angela Liss