O (fib n) алгоритмы сложности?

Question

При просмотре лекции 1B «Структура и интерпретация компьютерных программ» есть функция, которая вычисляет числа Фибоначчи. Лектор отмечает, что временная сложность составляет O (FIB N) - я никогда не видел этого раньше. Я видел округление до постоянной, линейной, n + m, квадратичной, полиномиальной или экспоненциальной сложности, но есть ли другие алгоритмы O (fib n) или другие интересные большие нотации O, которые следует посмотреть или изучить?

Answer 1

O(fib N) - ничего странного или особенного - это в точности то же самое, что и экспоненциальная сложность, - просто лектор не нашел времени, чтобы объяснить это. (Вы можете легко * связать fib(N) с phi^n.)

Вы не должны верить мне, хотя - у вас есть лучшее объяснение Math.stackexchange .

*: Я поясню, что я подразумеваю под «легко» - это означает, что доказательство легко доступно, например, в этой статье Википедии (благодаря предыдущему ответчику, который первоначально дал ссылку на это).