Практическое правило 10^8

Обычно онлайн-проверяющая система выполняет около 10^8 простых операций в секунду. Это Ваш бюджет на всю программу. 💡

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

Линейный проход O(n) при n = 10^6 — это всего миллион шагов, намного меньше бюджета. Решения с линейной сложностью почти всегда уверенно проходят проверку.

При n = 10^6 сортировка за O(n log n) требует примерно 2 · 10^7 шагов. Это всё ещё намного меньше бюджета одной секунды, поэтому сортировка редко становится узким местом.

Решение с O(n^2) достигает бюджета примерно при n = 10^4, когда требуется 10^8 шагов. После этого квадратичная сложность начинает приводить к превышению ограничения по времени.

Решение с O(n^3) подходит лишь примерно до n = 500. Возведение этого числа в куб даёт около 10^8 шагов — границу бюджета.

O(2^n) удваивается на каждом шаге, поэтому подходит только для очень малых n — примерно от 20 до 25. После этого количество операций резко превышает 10^8.

Python выполняет один шаг медленнее, поэтому для плотных циклов считайте бюджет скорее равным 10^7. Если ограничения близки к границе, оценивайте их с запасом.

Правило 10^8 считает простые шаги. Тяжёлая работа внутри цикла, например построение строк, добавляет постоянный множитель, который уменьшает Ваш реальный бюджет.

Ограничение по времени часто составляет 1 или 2 секунды. Ограничение в 2 секунды примерно удваивает Ваш бюджет и даёт немного больше запаса.

Сначала всегда подставляйте n в оценку сложности и сравнивайте результат с 10^8. Такая быстрая проверка здравого смысла спасает от написания заведомо неработающего решения.

Примените правило 10^8 на практике.

Теперь Вы умеете переводить количество операций во время: примерно 10^8 операций в секунду. Линейная сложность и n log n безопасны, квадратичная ограничена примерно n = 10^4, а оценку нужно делать до написания кода. ✅