Логика с нуля LOGIC · 05 · 02

Развёртывание рекуррент: линейная и квадратичная цена

Рекуррента считает работу рекурсии. T(n) = T(n-1) + 1 разворачивается в n+1 (линейный перебор), T(n) = T(n-1) + n разворачивается через Гаусса в n(n+1)/2 (квадрат). Разверни 3–4 шага, поймай закономерность, просуммируй, сверь на маленьком n.

LOGIC ◷ 12 min

Пакетный импортёр гладко проходит код-ревью: обработать первый элемент, отфильтровать его из списка, рекурсивно обработать остаток. На стейджинге он мгновенно прожёвывает 200 тестовых записей. В ночь запуска он встречает 100 000 настоящих — и прогресс-бар устраивается на выходные. Никто не написал ни одной медленной строки; каждый отдельный вызов работает честно и быстро. Убийца прячется в форме: каждый вызов заново сканирует всё оставшееся, поэтому вызовы делают n, потом n−1, потом n−2 шагов… и эти шаги складываются примерно в пять миллиардов. Рекуррента — это ценник рекурсии, а её развёртывание — навык читать ценник до кассы.

Цель

После этого урока ты можешь записать рекурренту для рекурсивной функции, развернуть её до замкнутой формы для линейного и квадратичного случаев, применить формулу Гаусса и проверить ответ счётчиком вызовов.

Обозначим T(n) число базовых шагов, которые функция выполняет на входе размера n. Поскольку рекурсивная функция — это «один слой моей работы плюс меньший себя», её стоимость подчиняется той же форме — рекурренте:

T(n) = T(меньшее) + (работа этого слоя)

Чтобы решить рекурренту, её нужно развернуть: подставить правую часть в саму себя несколько раз, поймать проступающую закономерность и просуммировать всё накопившееся.

Два хода всегда одни и те же, независимо от формы — записать уравнение из кода, потом разворачивать, пока закономерность не станет очевидной.

Рекурсивная сумма списка делает одно сложение и одно сравнение на вызов — константу, пусть 1 шаг — и рекурсит на списке короче на единицу:

T(n) = T(n-1) + 1,    T(0) = 1

Развернём:

T(n) = T(n-1) + 1
     = (T(n-2) + 1) + 1  = T(n-2) + 2
     = (T(n-3) + 1) + 2  = T(n-3) + 3
       …закономерность: T(n-k) + k
     = T(0) + n  =  n + 1        (берём k = n, чтобы дойти до базы)

Линейно: список в миллион стоит около миллиона шагов. Метод неизменен — разверни 3–4 шага, поймай закономерность, просуммируй, сверь на маленьком n вручную.

Проверка: T(2) должно быть 3 — и правда, sum([a, b]) делает три вызова: два элемента и один пустой список.

▸lesson.inset.note

Эта проверка заслуживает стать кодом. Формула предсказывает число вызовов, поэтому посчитайте вызовы в быстром скрипте — такая эмпирическая проверка дёшева и должна сопровождать каждую решённую рекурренту.

Теперь импортёр из пролога. Каждый вызов обрабатывает одну запись — но сначала заново сканирует все оставшиеся, чтобы отфильтровать список. Работа слоя не константа; она пропорциональна текущему размеру:

T(n) = T(n-1) + n

Развернём:

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
       …закономерность: T(0) + 1 + 2 + … + n

Итак, цена — сумма 1 + 2 + … + n. Гаусс спарил концы: 1 + 100 = 101, 2 + 99 = 101 — пятьдесят пар по 101, итого 5050. В общем виде n чисел образуют n/2 пар по n + 1:

1 + 2 + … + n  =  n(n + 1) / 2

Примерно n²/2 — квадрат. Числовое чутьё безжалостно: n = 200 стоит ~20 000 шагов (стейджинг пожимает плечами); n = 100 000 стоит ~5 000 000 000 шагов (ночь запуска умирает).

function process(items) {
  if (items.length === 0) return;
  handle(items[0]);
  const rest = items.filter((x) => x.id !== items[0].id); // n работы на слой
  process(rest);                                          // T(n-1)
}

Лечение — снова сделать работу слоя константной: идти по индексу вместо фильтрации — и рекуррента схлопывается обратно в T(n-1) + 1.

Пять ходов, каждый раз:

Выписать рекурренту из кода — сколько стоит один вызов и на чём он рекурсит?
Развернуть три-четыре шага механической подстановкой.
Поймать закономерность и записать k-й шаг.
Выбрать k так, чтобы попасть в базовый случай, и просуммировать накопившееся.
Сверить маленькое n вручную или счётчиком вызовов.

Пять минут арифметики — и сюрприз ночи запуска становится комментарием в ревью: этот filter делает импортёр квадратичным — 5·10⁹ шагов на проде.

▸Ещё практика

Ремесло чек-листом на скорости код-ревью: (1) выпишите рекурренту прямо из кода — сколько стоит один вызов и на чём он рекурсит; (2) механически разверните три-четыре шага; (3) поймайте закономерность и запишите k-й шаг; (4) подберите k так, чтобы попасть в базу, и просуммируйте накопившееся; (5) сверьте маленькое n вручную или счётчиком вызовов. Пять минут арифметики — и сюрприз ночи запуска становится комментарием в ревью: этот filter делает импортёр квадратичным — 5·10⁹ шагов на проде.

Те же пять ходов решают каждую рекурренту: выпишите уравнение стоимости из кода, подставьте его в себя несколько раз, запишите k-й шаг, подберите k до базового случая и просуммируйте остаток. Последняя клетка обязательна — маленькое n, сверенное вручную или счётчиком вызовов, ловит неверную закономерность до того, как она уедет в прод.

Разбор примера

Функция ниже рекурсивно суммирует список. T(3) = 3 + 1 = 4 — четыре вызова суммарно.

let calls = 0;
function sum(list) {
  calls++;
  if (list.length === 0) return 0;
  return list[0] + sum(list.slice(1));
}
sum([5, 2, 9]);
console.log(calls); // 4 — совпадает с T(3) = 3 + 1

Трассировка: sum([5,2,9]) → sum([2,9]) → sum([9]) → sum([]) — четыре вызова, база на четвёртом. Формула T(n) = n + 1 при n = 3 даёт ровно 4. Счётчик подтверждает арифметику.

Практика 0 / 5

Check yourself

Викторина

Функция обрабатывает один элемент, а затем рекурсивно обходит оставшийся список с фильтрацией (T(n)=T(n-1)+n). Как растёт её стоимость?

Итог

Рекуррента считает работу рекурсии: T(n) равно работе одного слоя плюс стоимости меньшего себя, которого он вызывает. Ремесло решения неизменно — разверните три-четыре шага подстановкой, поймайте закономерность k-го шага, подберите k до базового случая, просуммируйте накопившееся и сверьте маленькое n вручную или счётчиком вызовов в коде. Две формы покрывают самые частые ошибки. T(n) = T(n-1) + 1 разворачивается в n + 1: линейность, честный перебор. T(n) = T(n-1) + n — маляр, перекрашивающий забор: сумма 1 + 2 + … + n, которую спаривание концов по Гауссу сворачивает в n(n+1)/2 — квадрат, форма, которая порхает по 200 строкам стейджинга и сжигает пять миллиардов шагов на 100 000 продовых записей. Следующий урок охватывает формы с делением пополам и двумя вызовами — логарифм, n·log n и экспонента — и завершает карту.

Практика

Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.

вспомнитьприменитьуглубить0 из 5 завершено

Что-то непонятно?

Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.