O (FIB N) Алгоритмы сложности?

Question

Во время просмотра Лекция 1В структуры и интерпретации компьютерных программ, есть функция, которая рассчитывает номера Фибоначчи. Лектор указывает, что временная сложность O (Fib N) - я никогда не видел этого раньше. Я видел это округлые до постоянных, линейных, N + M, квадратичных, полиномиальных или экспоненциальных сложностей, но есть ли другие алгоритмы O (FIB N) или другие интересные большие o обозначений, которые следует просматривать или учиться?

Answer 1

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

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

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