Экспоненциальное время O(2ⁿ) в TypeScript

Когда работа удваивается

O(2ⁿ) означает экспоненциальное время: один дополнительный элемент входных данных удваивает объём работы. Это тот класс роста, в котором алгоритмы перестают быть пригодными — и не для огромных входных данных, а уже для средних.

Экспоненциальная работа обычно возникает из ветвящейся рекурсии: функция вызывает саму себя дважды, и каждый из этих вызовов снова вызывает себя дважды. Вызовы образуют дерево, которое удваивается на каждом уровне.

Рекурсивное число Фибоначчи

Последовательность Фибоначчи начинается с 0 и 1, и каждое следующее число — это сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, …

Это определение напрямую переводится в рекурсивную функцию: fib(n) возвращает fib(n - 1) + fib(n - 2). Она короткая и правильная — и экспоненциальная, потому что каждый вызов порождает ещё два, и одни и те же значения вычисляются снова и снова. Один только fib(2) в более крупном вызове пересчитывается тысячи раз.

Числа Фибоначчи с рекурсией

Счётчик вне функции считает каждый вызов. Вычисление fib(10) = 55 требует 177 вызовов — для одного маленького числа. Дерево вызовов удваивается на каждом уровне.

Напишите программу на TypeScript с рекурсивной функцией fib (fib от n — это fib от n-1 плюс fib от n-2, а n меньше 2 возвращается как есть), которая увеличивает счётчик вызовов, объявленный вне её, при каждом вызове. Вычислите fib(10) и напечатайте результат и общее количество вызовов.

> Вывод: программа на TypeScript и захваченный вывод

Prompt

Напишите программу на TypeScript с рекурсивной функцией fib (fib от n — это fib от n-1 плюс fib от n-2, а n меньше 2 возвращается как есть), которая увеличивает счётчик вызовов, объявленный вне её, при каждом вызове. Вычислите fib(10) и напечатайте результат и общее количество вызовов.

Вывод: программа на TypeScript и захваченный вывод

let calls = 0

function fib(n: number): number {
  calls++
  if (n < 2) {
    return n
  }
  return fib(n - 1) + fib(n - 2)
}

console.log("fib(10) =", fib(10))
console.log("вызовов функции:", calls)

Почему происходит взрыв

Посмотрите на количество вызовов по мере роста n с шагом 5. Оно растёт не шагами — оно умножается. Каждое +1 к n даёт примерно ×1,6 вызовов; каждое +5 — больше чем ×10.

При n = 50 количество вызовов превысило бы 40 миллиардов. В этом и состоит экспоненциальная ловушка: код выглядит безобидно, а небольшие тесты завершаются мгновенно.

Считаем вызовы по мере роста n

От fib(5) до fib(25) входное значение растёт в 5 раз — а количество вызовов растёт более чем в 16 000 раз, с 15 до 242 785.

Напишите программу на TypeScript с рекурсивной функцией fib, которая считает свои вызовы в счётчике, объявленном вне её. Для n = 5, 10, 15, 20, 25 сбрасывайте счётчик, вызывайте fib(n) и печатайте по одной выровненной строке для каждого n с количеством вызовов, чтобы показать экспоненциальный рост.

> Вывод: программа на TypeScript и захваченный вывод

Prompt

Напишите программу на TypeScript с рекурсивной функцией fib, которая считает свои вызовы в счётчике, объявленном вне её. Для n = 5, 10, 15, 20, 25 сбрасывайте счётчик, вызывайте fib(n) и печатайте по одной выровненной строке для каждого n с количеством вызовов, чтобы показать экспоненциальный рост.

Вывод: программа на TypeScript и захваченный вывод

let calls = 0

function fib(n: number): number {
  calls++
  if (n < 2) {
    return n
  }
  return fib(n - 1) + fib(n - 2)
}

for (const n of [5, 10, 15, 20, 25]) {
  calls = 0
  fib(n)
  const label = String(n).padStart(2)
  console.log(`fib(${label}) -> ${String(calls).padStart(7)} вызовов`)
}

Решение: цикл

Проблема не в числах Фибоначчи — проблема в том, что одни и те же значения вычисляются снова и снова. Цикл, который идёт вверх от 0 и 1 и хранит всего два последних значения, вычисляет каждое число ровно один раз.

Это O(n) по времени и O(1) по памяти: 24 шага вместо 242 785 вызовов для fib(25). Тот же ответ, но другой класс роста — именно для этого и нужен анализ алгоритмов.

Числа Фибоначчи с циклом

Две переменные идут вверх по последовательности; каждый круг вычисляет одно новое число. fib(25) = 75025 за 24 шага — рекурсивной версии для того же ответа понадобилось 242 785 вызовов.

Напишите программу на TypeScript, которая вычисляет fib(25) с помощью цикла вместо рекурсии: храните два последних значения в двух переменных и идите вверх, начиная с 0 и 1, подсчитывая шаги цикла. Напечатайте результат и количество шагов.

> Вывод: программа на TypeScript и захваченный вывод

Prompt

Напишите программу на TypeScript, которая вычисляет fib(25) с помощью цикла вместо рекурсии: храните два последних значения в двух переменных и идите вверх, начиная с 0 и 1, подсчитывая шаги цикла. Напечатайте результат и количество шагов.

Вывод: программа на TypeScript и захваченный вывод

const n = 25
let steps = 0

// Храним только два последних значения и идём вверх по последовательности.
let a = 0
let b = 1
for (let i = 2; i <= n; i++) {
  const next = a + b
  a = b
  b = next
  steps++
}

console.log("fib(25) =", b)
console.log("шагов цикла:", steps)