Числа Фибоначчи в Java - Вопросы
Всего: 5 вопросов
1. Как проще всего вычислить n-е число Фибоначчи в Java?
Как проще всего вычислить n-е число Фибоначчи в Java?
Проще и быстрее всего — циклом for: хранить два последних числа и на каждой итерации складывать их, сдвигая «окно» вперёд. Сложность O(n) по времени и O(1) по памяти — достаточно трёх переменных, массив не нужен. Рекурсию применяют для наглядности, но без мемоизации она слишком медленная.
2. Почему чистый рекурсивный алгоритм Фибоначчи такой медленный?
Почему чистый рекурсивный алгоритм Фибоначчи такой медленный?
Потому что одни и те же значения пересчитываются снова и снова: дерево вызовов растёт экспоненциально, сложность O(2^n). Например, при вычислении recursive(5) значение F(2) считается три раза, а F(1) — пять раз. Уже при n = 45–50 программа заметно тормозит, а при n = 250 практически зависает.
3. До какого числа Фибоначчи хватает типа long и что делать дальше?
До какого числа Фибоначчи хватает типа long и что делать дальше?
F(92) = 7540113804746346429 — это последнее число ряда, помещающееся в long. Начиная с F(93) происходит переполнение, и результат становится неверным (в том числе отрицательным) без выброса исключения. Для больших n используйте BigInteger — он поддерживает целые числа произвольной длины.
4. Что такое мемоизация и как она помогает рекурсивному алгоритму Фибоначчи?
Что такое мемоизация и как она помогает рекурсивному алгоритму Фибоначчи?
Мемоизация — это кеширование уже посчитанных значений (например, в массиве или HashMap), чтобы не вычислять их заново. Экспоненциальная медлительность — не свойство рекурсии как таковой, а следствие повторных вычислений. С мемоизацией рекурсивный алгоритм тоже становится линейным, O(n), но требует O(n) дополнительной памяти.
5. Что лучше для вычисления чисел Фибоначчи — цикл или рекурсия — и почему?
Что лучше для вычисления чисел Фибоначчи — цикл или рекурсия — и почему?
В рабочем коде почти всегда цикл for: он даёт O(n) по времени и O(1) по памяти, а ответ выдаёт мгновенно. Чистая рекурсия читается «как формула», но работает за O(2^n) и при n = 45 уже думает несколько секунд. Компромисс — рекурсия с мемоизацией: сохраняет читаемость и работает за O(n).