Что такое ряд Фибоначчи?
Последовательность Фибоначчи — это последовательность, в которой следующий член равен сумме двух предыдущих. Первые два члена последовательности Фибоначчи — это 0, за которым следует 1.
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 ....
С точки зрения математики, последовательность Fn чисел Фибоначчи определяется рекурсивным соотношением
Fn = Fn-1 + Fn-2
где
F0 = 0 , F1 = 1
Мы рассмотрим три способа написания программы для создания ряда Фибоначчи:
- Ряд Фибоначчи с использованием рекурсии
- Ряд Фибоначчи с использованием итерационного метода
- Ряд Фибоначчи с использованием матричной экспоненции
(1) Рекурсивный метод :
Простой метод, который является прямой рекурсивной реализацией математического рекуррентного соотношения, приведен выше.
//pseudo code
RFib(n)
{
if n=0 return 0;
else if n=1 return 1;
else return (RFib(n-1)+RFib(n-2));
}
Временная сложность: T(n) = T(n-1) + T(n-2), что является экспоненциальным.
Дополнительное пространство: O(n), если учитывать размер стека вызовов функций, иначе O(1).
Запуск Replit
(2) Итеративный метод :
Мы можем оптимизировать пространство, используемое в рекурсивном методе, сохраняя только два предыдущих числа, потому что это все, что нам нужно для получения следующего числа Фибоначчи в серии.
//pseudo code
IFib(n)
if n=0 return 0;
else if n=1 return 1;
else { a <= 0; b<=1;
for(i=2 to n) do
{ temp <= b;
b<= a+b;
a <= temp;
}
return b;
Временная сложность: O(n)
Дополнительное пространство: O(1)
Запустить Replit
(3) Экспоненциализация матрицы :
Пусть n > 1
Временная сложность : O(log(n))
Дополнительное место : O(log(n)), если учитывать размер стека вызовов функций, иначе O(1).
Запуск Replit
Спасибо за чтение