Наивная рекурсия Фибоначчи: откуда берётся экспонента
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(30) считается мгновенно, fib(40) — заметные секунды, fib(50) не дожидаются вовсе. Какая у этой функции асимптотика по времени?
- O(n): глубина рекурсии равна n, а каждый уровень стоит константу
- O(n log n): дерево вызовов сбалансировано, как у сортировки слиянием
- O(2^n): дерево вызовов ветвится надвое на каждом уровне
- O(n^2): каждый из n уровней рекурсии делает порядка n вызовов