Как вычислить n-е число Фибоначчи?

Числа Фибоначчи определяются рекуррентно: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Это классическая задача, на которой удобно показать разницу между наивным и оптимизированным решением.

Наивная рекурсия

Прямая реализация формулы даёт экспоненциальную сложность O(2^n), потому что одни и те же значения пересчитываются многократно.

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}
// fib(40) уже заметно тормозит

Мемоизация

Кэшируем результаты, чтобы каждое значение считалось один раз. Сложность становится O(n) по времени и O(n) по памяти.

function fib(n, memo = {}) {
  if (n < 2) return n;
  if (memo[n] !== undefined) return memo[n];
  return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

Итеративный подход

Храним только два последних числа, получая O(n) по времени и O(1) по памяти. Это оптимальный вариант для большинства практических задач.

function fib(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }
  return a;
}

Быстрое удвоение и матрицы

Для очень больших n применяют матричное возведение в степень или формулы быстрого удвоения, дающие O(log n). Это полезно в криптографии и задачах с большими индексами.

Итог: для обычных задач используйте итеративный подход O(n) с O(1) памяти; мемоизацию — когда нужны промежуточные значения; матричный метод — когда n огромно и важна логарифмическая сложность.