Время выполнения рекурсивной серии фибоначчи

-3

Серия Fibonacci медленна из-за пересчета. Что это значит для рекурсивного подхода? Нужно больше объяснений в контексте времени работы.Время выполнения рекурсивной серии фибоначчи

источник

2015-10-30 thedheeraz

Не реализуйте алгоритм рекурсивно. Вы можете сделать это итеративно. Он учит вас, что реализация алгоритмов имеет значение. –

Некоторые реализации фибоначчи медленны, а некоторые нет. Измерения помогут определить, не слишком ли вы слишком медленны. Исходный код также обеспечит качественный комментарий. –

Я голосую, чтобы закрыть этот вопрос как не по теме, потому что OP неохотно использует поисковую систему для такой общей проблемы. –

Время работы итерационного подхода O (n), где n - количество элементов в вашей последовательности.

Время работы для рекурсивного подхода O (2^n).

fib(int n){ 
     if(n==1 || n==2) return n;  
     else return fib(n-2) + fib(n-1) 
    }

Вы можете видеть, как это разбивается на дерево с экспоненциальными количествами элементов.

источник

2015-10-30 12:38:05

стек вызовов для n = 64 был бы высотой ~ 2^64, прежде чем ударить по базовому футляру и решить проблему сбрасывания стека. –

Время выполнения рекурсивной серии фибоначчи

ответ

Смежные вопросы