此动态规划算法获得第 n 个斐波那契数的时间复杂度

Question

我对该算法的时间复杂度感到困惑：

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

我的直觉是这个算法需要 O(n²) 时间和 O(n) 空间。但根据 this wikipedia page，时间复杂度为 O(n)，空间复杂度为 O(1)。我的理由是

previousFib + currentFib

很快就会变得非常昂贵。具体来说，如果

previousFib

和

currentFib

的大小随 n 线性增长，那么它们不应该构成 O(n) 空间，并且

previousFib + currentFib

不应该构成 O(n) 操作吗？

Answer 1

迭代发生 N 次，因此时间复杂度为 O(n)，对象的大小不会随着每次迭代/值而改变，这里仅保留 3 个常量对象，其中值在每次迭代中被覆盖，因此空间复杂度为 O(1)