Ограничения как бюджет решения

До написания кода полезно спросить не «какой алгоритм я помню?», а «сколько действий и памяти вообще допускает этот вход?». Ограничения не называют готовое решение, но быстро отсекают идеи, которые не успеют завершиться.

Как ограничения задают выбор идеи

Представим задачу: по массиву длины n нужно проверить некоторое свойство. У нас есть три корректные идеи: перебрать все подмножества, проверить все пары или обработать каждый элемент с поиском в структуре данных. До деталей реализации надо понять, какой порядок роста совместим с n.

Сколько кандидатов создаёт прямой перебор

Самая прямолинейная идея может рассмотреть все 2^n подмножеств. Для n = 20 это около миллиона вариантов — иногда приемлемо. Для n = 60 вариантов уже больше 10^18, поэтому такой перебор практически невозможен.

Если нужны только пары, их число равно n(n - 1) / 2. При n = 5_000 это примерно 12,5 миллиона пар, а при n = 200_000 — почти 20 миллиардов.

Почему рост важнее количества циклов

Важно не само наличие цикла, а число выполнений его тела. Два вложенных цикла по n дают квадратичный рост: увеличение входа в 10 раз увеличивает работу примерно в 100 раз. Экспоненциальный перебор растёт ещё быстрее.

Переводим размер входа в бюджет

Размер входа можно превратить в грубый бюджет порядка роста:

• малое n иногда допускает экспоненту;
• несколько тысяч элементов иногда допускают O(n²) с очень простым телом цикла;
• сотни тысяч элементов обычно требуют O(n log n) или ожидаемого O(n);
• большая таблица состояний может не поместиться в память даже при приемлемом времени.

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

Пять шагов до написания кода

1. Выписать максимальные размеры всех измерений входа, а не только пример.
2. Для каждой идеи посчитать, сколько раз выполняется основная операция: n, n log n, n², 2^n и так далее.
3. Отдельно оценить память: число хранимых элементов умножить на примерный размер элемента.
4. Учесть число тестов: сто массивов по 10^5 — не то же самое, что один такой массив.
5. Оставить самые простые идеи, которые укладываются с запасом, и только затем доказывать их корректность.

Какие ограничения легко прочитать неверно

• n = 0 или n = 1: многие задачи решаются без основного цикла.
• Несколько параметров, например n и m: два цикла могут давать O(nm), а не O(n²).
• Много наборов входных данных: оценивать нужно сумму размеров или сумму работ.
• Огромные элементы: массив из 10^7 целых и массив из 10^7 длинных строк требуют разной памяти.
• Ранний выход улучшает отдельные случаи, но не всегда меняет худшую оценку.

Когда сначала считать бюджет

Сначала оценивай бюджет, если в условии есть большие ограничения, несколько вложенных размеров, много запросов или фраза «для каждого подмассива/пары/подмножества». Это сигнал посчитать число кандидатов до реализации.

Почему таблица порогов не заменяет анализ

Не выбирай алгоритм только по таблице порогов. Два алгоритма с одинаковым O(n) могут сильно отличаться константами и памятью. Для маленького входа простой квадратичный код иногда безопаснее сложной оптимизации, а ограничения сами по себе не доказывают корректность быстрой идеи.

Проверяем квадратичную оценку

Вопрос. Почему O(n²) для n = 2_000 нельзя автоматически считать допустимым?

Ответ. Четыре миллиона итераций выглядят разумно только при дешёвом теле цикла и небольшом числе тестов. Если каждая итерация сравнивает длинные строки или таких тестов сто, фактическая работа становится намного больше.

Проверяем стоимость сортировки

Вопрос. Массив содержит 200_000 элементов. Достаточно ли фразы «использую сортировку» для оценки решения?

Ответ. Нет. Нужно учесть O(n log n) самой сортировки, дополнительную память конкретной реализации и работу после неё. Если после сортировки остаётся полный перебор пар, итог всё ещё O(n²).

Сопоставляем ограничения и классы идей

Для каждого ограничения предложи максимально простой реалистичный класс идей: n ≤ 18, n ≤ 3_000, n ≤ 300_000. Затем добавь условие «50 тестов максимального размера» и пересмотри ответ. Подсказка: сначала оцени число вариантов для 2^n, n² и n log n, а затем умножь на число тестов.

Сначала бюджет, затем доказательство

Ограничения — первый фильтр решения: посчитай кандидаты и память, отбрось заведомо дорогие идеи и только после этого переходи к доказательству и коду.