Как доказать временную сложность этой последовательности Фибоначчи O (n)

Question

В следующем коде я знаю, что сложность по времени равна O (n), но как мне это доказать надлежащим образом?Говорит ли ты, что для поиска в массиве достаточно 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., это может показаться вам рекурсией, но плохой реализацией.каждый из вызовов f [n-1] и f [n-2] фактически просто возвращает значения.

У вас будет 3n вызов F (n), так что O (n).

Если вы не обязаны выполнять рекурсию, вы можете запрограммировать ее с помощью одного цикла.