Сложность времени рекурсивного псевдокода

Question

Какова была бы функция временной сложности для псевдокода?

int what(int k){ 
    if(k==0 || k==1) 
     return k; 
    else 
     return what(k-1)*what(k-2); 
} 

Answer 1

Эта функция не вычисляет последовательность чисел Фибоначчи, но число вызовов последовательность Фибоначчи.

Поскольку функция не делает никакой работы, чтобы говорить о внутреннем, временная сложность такая же, как и количество вызовов.

Это O(fib N).

Answer 2

Пока число вызовов увеличивается (асимптотически) при золотом коэффициенте с увеличением k, это не последовательность Фибоначчи. Количество вызовов, для которых() выполнено для n, начинающегося с 0, равно 1, 1, 3, 5, 9, 15. Кроме того, функция what (k) равна k: -> Fib (k).

Что все выяснено, сложность остается O (Fib (n)), как указано ранее.

Answer 3

Я думаю, что временная сложность для этого кода O (п!), так как количество вызовов умножает каждый к приращение (это очень очень плохо).

(Шутка) Но у меня есть хорошие новости! Этот код можно упростить до O (1), так как он всегда возвращает 0!

int what(int k) { return 0; }