为什么使用 for 循环的 Fibonacci 的时间复杂度是 O(n^2) 而不是 O(n)？

Question

为什么下面算法的时间复杂度计算为 O(n^2) 而不是 O(n)。

FibList(n)
    array[0-n] Create Array            O(n)
    F[0] <- 0                          O(1)
    F[1] <- 1                          O(1)

    for i from 2 to n                  O(n)
        F[i] <- F[i-1] + F[i-2]        O(n) 

    return F[n]                        O(1)

O(n) + O(1) + O(1) + O(n) O(n) + O(1) = O(n^2)

Answer 1

如果您假设将具有 k1 位的整数与具有 k2 位的整数相加的成本与 max(k1, k2) 成正比（即所谓的 "bit" 成本模型，或 "logarithmic" 成本模型），则您生成的代码的时间复杂度为 O(n^2).

那是因为 F(i)（几乎）与 phi^i 成正比，其中 phi 是黄金比例。这意味着 F(i) 有 ~i 位。

因此成本：

for i from 2 to n
    F[i] <- F[i-1] + F[i-2]

与 (1 + 2 + 3 + ... n-1) 成正比，即 n(n-1)/2，因此 O(n^2)。

如果你假设任意大小的整数相加是 O(1)，那么代码就是 O(n)。

有关成本模型的背景，请参阅维基百科上的此部分https://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models，其中说

One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.

顺便说一句，你的问题中使用的方法，即写出每行的最大复杂度，然后将嵌套的复杂度相乘，不是计算紧束缚复杂度的有效方法，尽管它适用于所有复杂度都为多项式，在本例中为多项式。

为什么使用 for 循环的 Fibonacci 的时间复杂度是 O(n^2) 而不是 O(n)？

Why Time complexity of Fibonacci using for loop is O(n^2) and not O(n)?

algorithm

fibonacci

time-complexity