Рекурсия: различия между версиями

2 байта добавлено ,  9 лет назад
Конечно, пока числа не выходят за пределы машинной точности (на компьютерах с 32-битной архитектурой это означает «меньше <math>2^{32}</math>»), сложение выполняется за фиксированое число тактов. Но, начиная с <math>F(48)</math>, уже нельзя использовать элементарные 32-битные целочисленные типы и нужно использовать 64-битные или писать «свою» ''длинную арифметику'', то есть представлять числа в виде массивов цифр в некоторой системе счисления (обычно используют систему с основанием 10000) и писать процедуры сложения таких чисел «столбиком». Например, число десятичных знаков в 1000-м числе Фибоначчи равно 209, и для сложения <math>F(1001) = F(1000) + F(999)</math> «столбиком» в десятичной системе счисления потребуется примерно 209 элементарных операций. Определение сложности задачи вычисления <math>F(n)</math> при больших <math>n</math> довольно трудная задача.
 
Указанный пошаговый алгоритм вычисления чисел Фибоначчи с учётом затрат на сложения длинных чисел является квадатичнымквадратичным по <math>n</math> (при увеличении <math>n</math> в <math>k</math> раз время вычисления <math>F(n)</math> увеличивается в <math>k^2</math> раз), а не линейным как многие считают. Числа Фибоначчи в принципе нельзя подсчитать быстрее, чем за линейное время, так как, чтобы вывести цифры числа Фибоначчи <math>F(n)</math>, уже требуется линейное по <math>n</math> время.
 
Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке [[w:Mathematica|Mathematica]] (см. http://www.wolfram.com):
Анонимный участник