На экзамене просят «оценить сложность», на автопроверке решение получает Time Limit Exceeded, хотя на примере из условия отработало мгновенно. Обе ситуации про одно: как растёт время работы, когда растут входные данные. Ниже разберём, как считать операции, что на самом деле значит O(n), где прячутся лишние циклы и как до отправки прикинуть, уложится ли решение в секунду. Время в примерах замерено на нашем компьютере (gcc 12 с -O2, Python 3.12), у вас цифры будут другими, а соотношения те же.
Считаем операции
Сумма массива из n чисел:
long long sum = 0;
for (int i = 0; i < n; i++)
sum += a[i];
Тело цикла выполняется n раз. Вдвое больше чисел, вдвое больше работы. Такой рост называют линейным и пишут O(n).
Проверка, есть ли в массиве одинаковые числа, «в лоб»:
int has_dup_slow(const int *a, int n) {
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] == a[j])
return 1;
return 0;
}
Если повторов нет, сравниваются все пары: (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Для n = 1000 это около полумиллиона сравнений, для n = 100 000 уже пять миллиардов. Рост квадратичный, O(n²).
Что значит O(...)
Запись O(g(n)) говорит, что при больших n число операций растёт не быстрее, чем g(n), умноженное на какую-то константу. Важна только скорость роста, а не точное число операций.

Поэтому при оценке:
- константы отбрасывают: 3n и n/2 это O(n);
- младшие слагаемые отбрасывают: n²/2 + n/2 это O(n²), при больших n второе слагаемое ничего не решает;
- основание логарифма не пишут: log₂ n и log₁₀ n отличаются в константу раз.
Чтобы почувствовать разницу между классами, посмотрите, сколько операций они дают:
| Сложность | n = 10 | n = 1000 | n = 10⁶ | Пример |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | элемент массива по индексу |
| O(log n) | 3 | 10 | 20 | бинарный поиск |
| O(n) | 10 | 1000 | 10⁶ | один проход по массиву |
| O(n log n) | 33 | 10⁴ | 2·10⁷ | хорошая сортировка |
| O(n²) | 100 | 10⁶ | 10¹² | все пары |
| O(2ⁿ) | 1024 | ≈10³⁰¹ | все подмножества |
На n = 10 всё мгновенно, поэтому на примере из условия медленное решение не отличить от быстрого. Разница видна только на больших тестах.
Замер того же поиска повторов: вариант O(n²) против сортировки с проверкой соседей, O(n log n).
n = 100000: O(n^2) 0, 1.764 s; O(n log n) 0, 0.0026 s
n = 200000: O(n^2) 0, 7.087 s; O(n log n) 0, 0.0054 s
Удвоили n, квадратичный вариант стал медленнее в 4 раза, а второй примерно в 2. На n = 200 000 разница больше чем в тысячу раз.
Правила для циклов
- Циклы друг за другом складываются: O(n) + O(n²) = O(n²), остаётся самый тяжёлый.
- Вложенные циклы перемножаются: внешний на n, внутренний на m, итого O(n·m).
- Внутренний цикл от i до n всё равно даёт O(n²): в среднем он проходит половину, а половина это константа.
- Цикл с постоянным числом шагов не меняет оценку:
for (j = 0; j < 26; j++)внутри цикла по n даёт O(26n) = O(n). - Переменная делится или умножается на 2:
for (i = n; i > 0; i /= 2)делает около log₂ n шагов, это O(log n).
Константы в O не видны, но на практике они важны. O(n) с телом из ста операций может работать дольше, чем O(n log n) с одной операцией, пока n небольшое.
Логарифм: бинарный поиск
В отсортированном массиве искомое число можно найти, каждый раз отбрасывая половину:
int binary_search(const int *a, int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x)
return mid;
if (a[mid] < x)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
После k шагов остаётся n / 2ᵏ элементов. Поиск кончается, когда остался один: n / 2ᵏ = 1, отсюда k = log₂ n. Для миллиона элементов это 20 шагов, ведь 2²⁰ = 1 048 576. Со счётчиком наш поиск в массиве из 10⁶ чисел сделал ровно 20 шагов и когда нашёл число, и когда его не было. Запись lo + (hi - lo) / 2 вместо (lo + hi) / 2 защищает от переполнения int при больших индексах.
Логарифм появляется везде, где задача на каждом шаге делится пополам: бинарный поиск, быстрое возведение в степень, сбалансированные деревья, а в сортировке слиянием log n уровней деления.
Скрытые циклы
Самые обидные O(n²) получаются, когда второй цикл не виден в коде.
strlen в условии цикла.
for (size_t i = 0; i < strlen(s); i++)
if (s[i] == ' ')
cnt++;
strlen сама проходит строку до конца, и вызывается она на каждой итерации. Строка из миллиона символов при сборке с -O0 обрабатывалась у нас 13,5 с, а с длиной, посчитанной один раз до цикла, 0,002 с. С -O2 gcc сам вынес strlen из цикла, но рассчитывать на это не стоит: посчитайте длину заранее.
in для списка в Python. Проверка x in data для списка просматривает его целиком, это O(n). 10 000 таких проверок по списку из 100 000 чисел заняли 5,17 с. Те же проверки по множеству set(data) в среднем O(1) и заняли 0,0002 с.
Ещё примеры: list.pop(0) и list.insert(0, x) сдвигают весь список, это O(n). Для очереди в Python есть collections.deque. Срез a[i:j] копирует элементы. Сложение строк s = s + c в цикле в C++ копирует строку каждый раз, лучше s += c.
Сложность сортировок
| Сортировка | Худший случай | В среднем | Память |
|---|---|---|---|
| пузырьком, вставками, выбором | O(n²) | O(n²) | O(1) |
| слиянием | O(n log n) | O(n log n) | O(n) |
| быстрая (quicksort) | O(n²) | O(n log n) | O(log n) на стек в среднем |
| пирамидальная (heapsort) | O(n log n) | O(n log n) | O(1) |
| подсчётом | O(n + k) | O(n + k) | O(k), k это диапазон значений |
Сортировка сравнениями не может быть быстрее O(n log n) в худшем случае, поэтому O(n log n) считают нормой. Сортировка подсчётом обходит эту границу, потому что не сравнивает элементы, но годится только для небольшого диапазона целых чисел.
В реальном коде пишите стандартную сортировку. std::sort в C++ начиная с C++11 обязан укладываться в O(n log n) сравнений в худшем случае (cppreference). В Python sorted() и list.sort() тоже работают за O(n log n).
Память тоже считают
Оценка памяти устроена так же. Сумма массива требует O(1) дополнительной памяти, сортировка слиянием O(n), таблица n × n занимает O(n²).
Перевести в байты просто: int занимает 4 байта, long long и double 8. Матрица int 10 000 × 10 000 это 10⁸ × 4 байта = 400 МБ, при лимите в 256 МБ она не поместится, даже если по времени всё хорошо. В Python числа занимают больше: список из миллиона целых у нас занял около 40 МБ против 4 МБ для массива int в C.
Рекурсия тоже расходует память: глубина n значит n кадров в стеке, то есть O(n) памяти, даже если в функции нет ни одного массива.
Уложится ли решение в лимит времени
Точное время заранее не узнать, но порядок прикинуть можно. Для оценки обычно берут, что C и C++ успевают порядка 10⁸ простых операций в секунду с запасом. Это ориентир с запасом, а не закон. Самый простой цикл сравнений из примера выше у нас делал около 3·10⁹ итераций в секунду, но в реальном решении есть операции тяжелее: деление, обращения к памяти вразброс, вызовы функций. В Python простой цикл for i in range(10**7): s += i у нас выполнился за 0,58 с, то есть около 2·10⁷ итераций в секунду. Встроенные функции вроде sum, sorted и in для set работают внутри интерпретатора на C и намного быстрее ручных циклов.
Отсюда ориентиры для лимита в 1 секунду на C++:
| n до | Подходит | Пример |
|---|---|---|
| 10–11 | O(n!) | перебор перестановок |
| 20–25 | O(2ⁿ) | перебор подмножеств |
| 500 | O(n³) | три вложенных цикла |
| 5000 | O(n²) | все пары |
| 10⁶ | O(n log n) | сортировка, бинарный поиск для каждого элемента |
| 10⁸ | O(n) | один простой проход |
Пример расчёта. В условии n ≤ 2·10⁵. Решение O(n²): (2·10⁵)² = 4·10¹⁰ операций, это сотни секунд даже на C. Решение O(n log n): 2·10⁵ × 18 ≈ 3,6·10⁶, это миллисекунды. Ограничения в условии часто подсказывают, какую сложность ждут: n ≤ 5000 намекает на O(n²), n ≤ 10⁵ и больше требует O(n log n) или O(n).
Как оценить свой код: порядок действий
- Найдите, от каких величин зависит работа: длина массива n, число запросов q, размер строки.
- Для каждого цикла определите, сколько раз он выполняется, и перемножьте вложенные.
- Проверьте вызовы внутри циклов:
strlen,inдля списка,pop(0), копирование строк и срезов, сортировку. - Для рекурсии оцените число вызовов и глубину. Если вызов порождает два новых, как в наивном Фибоначчи, рост экспоненциальный.
- Подставьте максимальные значения из условия и сравните с ориентиром в 10⁸ операций в секунду.
- Если не уверены, замерьте: сгенерируйте тест максимального размера и запустите
time ./prog < big.txt.
Как с этим помогает Tilpi
В чате задания Tilpi разбирает тему по шагам и объясняет код: можно показать своё решение и попросить оценить его сложность и найти место, где прячется лишний цикл. Если к заданию приложена лекция по алгоритмам, ответ опирается на неё и ссылается на страницу. Исполнитель запускает код в отдельной изолированной машине, пишет и прогоняет тесты, так что решение можно проверить на большом входе. Чат по своим файлам работает бесплатно с подтверждённой почтой в пределах лимитов, исполнитель на уровне «Быстрая» входит в тариф «Лайт», все уровни открыты с тарифа «Плюс».
