Как рассчитать время рекурсивного вычисления n-го числа Фибоначчи?
Как узнать, сколько времени требуется для вычисления n-го числа Фибоначчи на текущей машине? Например, на текущей машине 30-й элемент рассчитывается за 67 мс, а 40-й - за 554 мс. Как рассчитать время для 99-го элемента?
int fib(int n)
{
if( n <= 2)
return 1
else
return fib(n-1) + fib(n-2)
}
ОБНОВИТЬ
Фибоначчи, Nth против мс (время, которое текущий компьютер вычисляет для вычисления n-го элемента Фибоначчи, время в мс) http://pastebin.com/PGnd54Hq
Matlab: код http://pastebin.com/L9CH53Pf
Как узнать время для N-го элемента?
5 ответов
Я бы измерил время для диапазона значений и составил бы таблицу:
n | time
а затем использовать matlab
чтобы соответствовать экспоненциальной функции.
- Подогнать экспоненциальную кривую через точки данных в Matlab
- экспоненциальная форма, без стартером предугадывать
- Построение экспоненциальных кривых
имейте в виду, что нотация big-O асимптотична и справедлива для большого числа элементов.
Вы должны попытаться написать код для него. используя встроенную функцию подпрограммы Фибоначчи, получите время использования ctime и сохраните значения в двух массивах. и после этого анализируя результаты с помощью matlab
или `питон.
пожалуйста, опубликуйте свои результаты...
Легко доказать, что число рекурсивных вызовов функции также следует последовательности Фибоначчи. Как если бы F0=0
а также F1=1
ваши базовые случаи тогда F2
требуется 2 вызова функции и F3
понадобится 3 и так далее.
Это оправдывает использование экспоненциальной функции, чтобы соответствовать вашему времени, как предложено @0x90.
Видимо, вы запускаете реализацию наивного алгоритма для вычисления последовательности Фибоначчи. Этот алгоритм имеет экспоненциальную сложность: вычислительная сложность последовательности Фибоначчи (~ θ(1.6
n
)
). Таким образом, время работы вашей программы на вашем компьютере будет примерно k*1.6
n
, Зная результат функции (время выполнения вашей программы) для одного n
Вы должны быть в состоянии рассчитать константу k
и, таким образом, рассчитать приблизительное время для разных n
,
Производительность определяется не только количеством вызовов функций и количеством вычислений внутри каждого вызова, но и тем, что вы платите - по времени - за то, что все больше и больше стекаете в стек из-за рекурсивного алгоритма. Я не знаю, как происходит это стекание, но, вероятно, оно начинает расти быстрее после определенного порога. Итак, вам нужно выяснить, где этот порог срабатывает и подходит (экспоненциально или как-то еще) как ниже, так и выше (и, возможно, существуют более похожие ограничения производительности, когда вы начинаете создавать рекурсивный стек).
Очевидно - хотя это и не вопрос - числа Фибоначчи не должны вычисляться рекурсивным способом, даже если это математически элегантно и требует самого простого кода.
[ДОБАВЛЕНО / ИЗМЕНЕНО] Я заметил, что вы добавили график измерения времени. Чтобы лучше понять, я предлагаю использовать шкалу LOGARITHMIC по вертикали (раз). Это более четко покажет, является ли весь граф "чисто" экспоненциальным - прямая линия на логарифмическом графике - или это скорее последовательность (разных) экспонент или еще что-то еще. Возможно, экспоненциальная часть начинается "где-то" или превращается в другую экспоненциальную.
Из указанного кода каждый звонок совершает 2 звонка. Таким образом, простой ответ на этот вопрос заключается в том, что количество вызовов удваивается для каждого n, поэтому количество вызовов составляет 2^(n-1). Например, если вы вычисляете fib( 10), то количество вызовов будет 2^9 = 512. Таким образом, если для его создания понадобится 1 секунда, для всех вызовов fib (10) потребуется 512 секунд.).