如何证明该Fibonacci序列的时间复杂度为O(n)

Question

在下面的代码中，我知道时间复杂度是O(n)，但是我如何以适当的方式证明它？是说搜索数组就足够了吗？

int f[N];
F(n)
{
    if (f[n] >= 0) return f[n];
    f[n] = F(n-1) + F(n-2);
    return f[n];
}

int main()
{
    read n;
    f[0] = 0; f[1] = 1;
    for (i = 2; i <= n; i++)
        f[i] = -1;
    print F(n);
}

Answer 1

对于调用F的数组中的每个元素，它可能看起来像是一个递归，但却是一个糟糕的实现。fn-1和fn-2调用实际上只是返回值。

您将有3n次对F(n)的调用，因此仍然是O(n)。

如果你不一定要使用递归，你可以用一个循环来编写它。