Найти n-е число Фибоначчи итеративно за O(n) и O(1)
Реализуйте Fib(n), возвращающую n-е число Фибоначчи, причём Fib(0) == 0 и Fib(1) == 1. Требования: ИТЕРАТИВНО, O(n) по времени и O(1) памяти — храните только два последних значения, НЕ используйте наивную рекурсию (она экспоненциальна) и НЕ выделяйте массив всех n значений.
public static long Fib(int n)
{
// ваш код здесь
return 0;
}Допишите реализацию.
Держите два скользящих значения a = 0, b = 1. Цикл n раз: вычисляйте b как a + b и сдвигайте a к старому b кортежным обновлением (a, b) = (b, a + b). Верните a. Это O(n) по времени, O(1) памяти — без массива и без экспоненциальной рекурсии.
- ✗Использовать наивную двойную рекурсию — она экспоненциальна O(2^n), а не O(n)
- ✗Выделять массив всех n значений, тратя O(n) памяти, когда хватает O(1)
- ✗Ошибка на единицу в цикле, из-за которой
Fib(0)илиFib(1)даёт неверное начало
- →Почему наивная рекурсия экспоненциальна и как мемоизация это исправляет?
- →При каком
nFibпереполняетlong?
Задача
Вернуть n-е число Фибоначчи итеративно за O(n) и O(1).
public static long Fib(int n)
{
long a = 0, b = 1; // Fib(0), Fib(1)
for (int i = 0; i < n; i++)
(a, b) = (b, a + b); // сдвигаем пару вперёд
return a;
}Как это работает
Каждое число Фибоначчи — сумма двух предыдущих. Вместо хранения всей последовательности мы держим только пару (a, b) = два соседних числа, начиная с (Fib(0), Fib(1)) = (0, 1).
Каждая итерация сдвигает окно вперёд: новое a становится старым b, а новое b — суммой a + b. Кортежное обновление (a, b) = (b, a + b) делает оба присваивания одновременно, без временной переменной. После n шагов a содержит Fib(n).
Цикл выполняется n раз с константной работой на шаг — O(n) по времени и O(1) по памяти. Наивная рекурсия Fib(n-1) + Fib(n-2) была бы экспоненциальной O(2ⁿ), пересчитывая одни и те же значения.
