O (FIB N) Алгоритмы сложности?
-
30-09-2019 - |
Вопрос
Во время просмотра Лекция 1В структуры и интерпретации компьютерных программ, есть функция, которая рассчитывает номера Фибоначчи. Лектор указывает, что временная сложность O (Fib N) - я никогда не видел этого раньше. Я видел это округлые до постоянных, линейных, N + M, квадратичных, полиномиальных или экспоненциальных сложностей, но есть ли другие алгоритмы O (FIB N) или другие интересные большие o обозначений, которые следует просматривать или учиться?
Решение
O(fib N)
Ничего странного или особенного - это точно так же, как экспоненциальная сложность - именно то, что преподаватель не потратил время, чтобы разобрать это. (Вы можете легко * связаться fib(N)
с участием phi^n
.)
Вы не должны верить мне, хотя - у вас будет лучшее объяснение на Math.stackexchange..
*: Я уточню, что я подразумеваю под «легко» - это означает, что доказательство доступно, например, в Эта статья Википедии (Благодаря предыдущему ответу, который первоначально дал ссылку на него).