Оценка сложности: зайдёт ли решение

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

Что означает O большое

Запись $O(n)$ значит, что программа делает не больше чем $c \cdot n$ операций для какой-то константы $c$. Десять проходов по массиву — это $O(n)$, потому что $c = 10$. Проход по половине массива — тоже $O(n)$, просто $c = \tfrac{1}{2}$.

Слова «не больше» здесь важнее, чем кажется. Вот вопрос, на котором ошибается почти вся аудитория:

for (int i = 0; i < n; i++) sum += a[i];

Правда ли, что этот код работает за $O(n^2)$? Правда. Он делает не больше $n^2$ операций — определение выполнено. Просто оценка бесполезно слабая. Когда вы считаете асимптотику, легко насчитать лишнего и получить формально верный, но ничего не значащий ответ.

Не только O

Раз $O$ — это «не больше», должны быть и другие обозначения, и они есть:

• $O(f)$ — не больше: верхняя оценка;
• $\Omega(f)$ — не меньше: нижняя оценка;
• $\Theta(f)$ — и то и другое: оценка точная.

Строго говоря, про сортировку слиянием правильно сказать $\Theta(n \log n)$: она не только не медленнее, но и не быстрее. Про сортировку вставками — $O(n^2)$ и $\Omega(n)$: верхняя и нижняя оценки у неё разные, потому что время зависит от входа.

В разговоре почти всегда говорят $O$, подразумевая $\Theta$, и это нормально. Но когда речь заходит о доказательстве, что быстрее нельзя, нужен именно $\Omega$ — иначе утверждение не имеет смысла.

Сколько операций в секунду

Точного числа нет: оно зависит от процессора, от нагрузки, от того, какие именно операции вы делаете. Сложение и умножение стоят по-разному, деление и взятие по модулю — заметно дороже, промах мимо кеша дороже всего.

Рабочая оценка для C++ — примерно $3 \cdot 10^8$ операций в секунду. Если прикидка получилась близкой к границе, попробуйте поделить не на $3 \cdot 10^8$, а на $5 \cdot 10^8$: когда операции простые, столько тоже бывает.

Как этим пользоваться. Пусть в задаче $n \le 2 \cdot 10^4$, а решение работает за $O(n^2)$. Подставляем: $4 \cdot 10^8$ операций. Делим на $3 \cdot 10^8$ — получаем примерно 1,3 секунды. При ограничении в секунду это «скорее не зайдёт, но попробовать можно».

Думайте вероятностями, а не порогом

Прикидка не даёт ответа «да» или «нет». Она даёт шансы:

Прикинутое число операций	Шанс уложиться
$10^7$	практически наверняка
$10^8$	около 90%
$10^9$	около 20%
$10^{10}$	практически никогда

Разброс берётся из того, чего вы про свой код не знаете: сколько там делений, как ложатся данные в кеш, сколько раз вы на самом деле проходите по массиву. Со временем это чувство приходит: «здесь у меня константа большая, значит будем считать по $10^8$».

Память — тоже ресурс

Ограничение по памяти в условии стоит рядом с ограничением по времени, и про него забывают чаще.

Прикидка такая же простая: один int — 4 байта, long long — 8. Массив из $10^7$ чисел типа int займёт 40 мегабайт; при лимите в 256 таких массивов можно завести шесть, а не шестьдесят.

В Python всё дороже: список из $10^7$ чисел — это не 40 мегабайт, а сотни, потому что каждый элемент там полноценный объект. Если память поджимает, спасают array из стандартной библиотеки или bytearray.

Отдельно стоит помнить про рекурсию: каждый вложенный вызов занимает место на стеке. Глубина $10^6$ в C++ обычно кончается падением, а в Python — исключением уже на тысяче.

Амортизация: «в среднем по всей работе»

Иногда одна операция дорогая, но дорогой она бывает редко, и в сумме всё дёшево.

Классический пример — push_back в вектор. Когда место кончается, вектор выделяет вдвое больше памяти и копирует всё туда: одна такая операция стоит $O(n)$. Но происходит это после удвоений, то есть на $n$ добавлений приходится $n/2 + n/4 + \ldots < n$ копирований. Значит, в среднем на операцию — константа.

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

На амортизации стоят два указателя и стек из статей про линейные алгоритмы: внутренний цикл там может сделать много шагов на одной итерации, но за всё время — не больше $n$.

Ограничения подсказывают ответ

Автор задачи выбирает $n$ не случайно — он выбирает его так, чтобы прошло задуманное решение и не прошло наивное. Поэтому по ограничению часто видно, чего от вас хотят:

Ограничение на $n$	Ожидаемая асимптотика
$10^{18}$, $10^9$	$O(1)$ или $O(\log n)$
$10^7$	$O(n)$
$10^6$	$O(n \log n)$
$10^3 \ldots 10^4$	$O(n^2)$
$25$	$O(2^n)$
$10$	$O(n!)$

Правило не железное, но срабатывает часто. Если $n$ до миллиарда, а вы придумали решение за $O(n)$ — вы придумали не то решение.

Логарифм — это очень мало

Логарифм по основанию 2 от числа — это степень, в которую надо возвести двойку, чтобы получить это число: $\log_2 16 = 4$.

Главное про него — насколько он мал. $\log_2 10^9$ — это меньше 30. Миллиард элементов, тридцать шагов. Именно поэтому множитель $\log n$ в асимптотике почти ничего не стоит, а $n \log n$ живёт при $n$ до миллиона.

И ещё: основание логарифма в асимптотике не важно. Если каждый шаг уменьшает данные в 1,1 раза, то восьми шагов хватает, чтобы они уменьшились вдвое ($1{,}1^8 \approx 2{,}14$) — значит $\log_{1{,}1} n$ отличается от $\log_2 n$ не больше чем в восемь раз, то есть на константу, а константы $O$ большое не различает.

Быстрый ввод в C++

Поток cin по умолчанию синхронизирован с scanf и связан с cout. Обе связи стоят времени, и на больших входах именно они съедают лимит. Две строки в начале main их снимают:

ios::sync_with_stdio(false);
cin.tie(nullptr);

После этого пользоваться можно только cin и cout: смешивать их с scanf и printf уже нельзя, порядок вывода перестанет быть предсказуемым. В интерактивных задачах cin.tie(nullptr) тоже вредит — там вывод должен уходить сразу.

Ещё одна привычка: функция pow в олимпиадном коде не нужна. Она работает с вещественными числами, медленная и умеет ошибаться в последнем разряде. Целую степень двойки дают сдвиг 1 << k или обычное умножение.