Вычислите n-е число Фибоначчи за O(n) времени и O(1) памяти
Реализуйте fib(n), возвращающую n-е число Фибоначчи (fib(0) = 0, fib(1) = 1). Требования: O(n) по времени и O(1) доп. памяти — итеративно, без наивной двойной рекурсии (экспоненциальна) и без хранения всей последовательности. Обработайте базовый случай n < 2, вернув n.
func fib(n int) int {
// ваш код здесь
return 0
}Допишите реализацию.
Верните n для n < 2, затем держите два скользящих значения a, b := 0, 1 и обновляйте a, b = b, a+b в цикле от 2 до n, возвращая b. Это O(n) по времени и O(1) по памяти — гораздо лучше наивной рекурсии, экспоненциальной по сложности. Мемоизированная рекурсия кеширует в map[int]int.
- ✗Использовать наивную двойную рекурсию, экспоненциальную по времени
- ✗Хранить всю последовательность, когда хватает двух скользящих переменных
- ✗Разбивать
a, b = b, a+bна два оператора, портя обновление
- →Почему наивная рекурсия
fib(n-1) + fib(n-2)работает за экспоненциальное время? - →Как параллельное присваивание
a, b = b, a+bизбавляет от временной переменной?
Задача
Вычислить n-е число Фибоначчи за O(n) времени и O(1) памяти.
func fib(n int) int {
if n < 2 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}Почему итеративно
Наивная рекурсия fib(n-1) + fib(n-2) пересчитывает одни и те же подзадачи многократно, давая экспоненциальную сложность (≈ O(φⁿ)).
Итеративная версия хранит лишь два последних значения. На каждом шаге параллельное присваивание a, b = b, a+b вычисляет правую часть до записи, поэтому временная переменная не нужна. Итог — O(n) по времени, O(1) по памяти.
⚠️ Если просят мемоизировать рекурсию, используйте кеш map[int]int, чтобы каждое fib(k) считалось один раз.
