Описание тега fibonacci

Последовательность Фибоначчи - это последовательность, определяемая

F(0) = 0
F(1) = 1
F(n + 2) = F(n) + F(n + 1).  

Первые несколько терминов - 0, 1, 1, 2, 3, 5 и 8.

Самый эффективный способ вычислить первые N значений - перебрать массив, используя приведенную выше формулу, что приведет к O(N) операции (O(N²)если подсчитываются цифровые или битовые операции). Рекурсивной реализации обычно следует избегать, поскольку онаO(φN) где φявляется золотым сечением и равно(1+sqrt(5))/2. Однако при использовании кеша для уже вычисленных значений это может быть так же быстро, как итеративная реализация.

Одним из эффективных методов вычисления отдельных чисел Фибоначчи является

Fib(n) = Round(  Power( 0.5*(1+Sqrt(5)), n ) / Sqrt(5)  );

Квадратный корень и мощность должны быть вычислены с достаточной точностью, грубо говоря, для Fib(n) требуется примерно 0,2*n десятичных цифр или примерно 0,7*n бит в целочисленном результате.

Другой метод основан на том, что матрица

( Fib[n+1] Fib[ n ] )
( Fib[ n ] Fib[n-1] )

n-я степень матрицы

( 1 1 ) который ( Fib[2] Fib[1] )
( 1 0 ) равно ( Fib[1] Fib[0] )

Это основа метода деления пополам и возведения в квадрат, который вычисляет Fib[N] в O(log(N)) операции, полностью в (большой) целочисленной арифметике.

Если учесть сложность умножения больших целых чисел, сложность возрастет до O( M(N)) операций с цифрами или битами, где M(d) - сложность умножения чисел длиной d в битах. Типичные методы имеют M(d)=O(d*log(d)) для умножения на основе БПФ, M(d)=O(d^w) с w=log₂(3) для Карацубы и меньшим w для Тоома-Кука. методы.