Какова временная сложность печати всех чисел Фибоначчи от 0 до n?

Question

Здесь был задан тот же вопрос: Сложность времени для всех чисел Фибоначчи от 0 до n , но я не могу понять предоставленный ответ.

Следующий код печатает все числа Фибоначчиот 0 до п.Что такое сложность времени?

void allFib(int n){
    for(int i = 0 ; i < n ; i++){
        System.out.println(i + ": " + fib(i));
    }
}    

int fib(int n ){
    if(n <= 0) return 0;
    else if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

Я не понимаю, почему сложность времени составляет O (2 ^ n), а не O (n * 2 ^ n).Говорят, что:

fib (1) занимает 2 ^ 1 шагов

...

fib (n) занимает2 ^ n шагов

Я не могу понять, как это верно, поскольку fib (1) немедленно возвращает 1 на основе оператора else, поэтому он должен сделать 1 шаг.Даже если бы это утверждение было правдой, я все еще не могу понять, как сложность времени составляет всего O (2 ^ n).

Answer 1

Для написанной программы, если временная сложность fib(n) равна T1(n), общая временная сложность программы составляет T(n) = sum_{i=0}^{n-1} T1(i).Теперь попробуйте вычислить T1(i).По определению функции fib, T1(i) = T1(i-1) + T2(i-2) + 2 и T1(0) = 1 (одно сравнение) и T1(1) = 2 (два сравнения).

Из известного предыдущего анализа мы знаем, что T1(i) = Theta(2^i).Следовательно, T(n) = Theta(sum_{i=1}^{n-1} 2^i) = Theta(2^n - 1) = Theta(2^n).