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

Question

Во время просмотра lecture 1B of the Structure and Interpretation of Computer Programs есть функция, которая вычисляет числа Фибоначчи. Лектор указывает, что временная сложность O (fib n) - я никогда раньше этого не видел. Я видел, что он округлен до постоянной, линейной, n + m, квадратичной, полиномиальной или экспоненциальной сложности, но существуют ли какие-либо другие O (fib n) алгоритмы или другие интересные большие O-записи, которые следует рассматривать или изучать?

Answer 1

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

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

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