2.2 Классы сложности¶

В предыдущем разделе мы научились оценивать временную сложность алгоритмов. Теперь систематизируем основные классы сложности и разберём, что они означают на практике.

Ниже приведены наиболее распространённые оценки времени работы алгоритмов.

O(1) — константная сложность¶

Алгоритм работает за фиксированное время, независимо от размера входных данных.

Пример: вычисление значения по формуле.

int sum_first_n(int n) {
    return n*(n+1)/2;
}

Сколько бы ни было n, выполняется одно и то же количество операций.

O(log n) — логарифмическая сложность¶

Такие алгоритмы на каждом шаге уменьшают размер задачи в несколько раз (обычно в 2 раза).

Интуиция: Сколько раз нужно делить n на 2, чтобы получить 1? Ответ — log₂ n.

Пример: бинарный поиск.

Если массив отсортирован, на каждом шаге мы отбрасываем половину элементов.

while (l <= r) {
    int m = (l + r) / 2;
    if (a[m] == x) return true;
    if (a[m] < x) l = m + 1;
    else r = m - 1;
}

Количество шагов ≈ log₂ n.

O(√n) — корневая сложность¶

Медленнее логарифмической, но быстрее линейной.

Иногда возникает при переборе делителей числа:

for (int i = 1; i*i <= n; i++) {
    if (n % i == 0) {
        // i и n/i — делители
    }
}

Мы перебираем только до √n, потому что делители идут парами.

Корень — своего рода «середина» между константой и линейным ростом.

O(n) — линейная сложность¶

Алгоритм проходит по входным данным один раз.

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

Если нужно прочитать весь массив — быстрее быть не может.

O(n log n)¶

Часто встречается в задачах, где:

используется сортировка,
либо выполняется n операций по log n.

Пример 1 — сортировка¶

Эффективные алгоритмы сортировки работают за O(n log n).

Пример 2 — работа со структурами данных¶

multiset<int> s;

for (int i = 0; i < n; i++) {
    s.insert(a[i]);  // O(log n)
}

Каждая вставка — log n, всего n вставок.

O(n²) — квадратичная сложность¶

Обычно это два вложенных цикла:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // операция
    }
}

Можно перебрать все пары элементов за O(n²).

⚠️ При n = 10⁵ такой алгоритм уже будет медленным, обычно.

O(n³) — кубическая сложность¶

Три вложенных цикла.

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            // операция

Перебор всех троек элементов.

Работает только при n ≤ 500, как правило.

O(2ⁿ) — экспоненциальная сложность¶

Часто означает перебор всех подмножеств множества из n элементов.

Количество подмножеств:

2ⁿ

Например, для множества {1,2,3}:

∅
{1}
{2}
{3}
{1,2}
{1,3}
{2,3}
{1,2,3}

Всего 8 = 2³.

for (int mask = 0; mask < (1<<n); mask++) {
    // перебор подмножества
}

Работает примерно до n ≤ 20.

O(n!) — факториальная сложность¶

Обычно означает перебор всех перестановок.

Количество перестановок из n элементов:

n!

Для n = 10:

10! = 3 628 800

Для n = 20:

20! ≈ 2.4 × 10¹⁸

do {
    // обработка перестановки
} while (next_permutation(p.begin(), p.end()));

Практически применимо только до n ≤ 10.

Полиномиальные алгоритмы¶

Алгоритм называется полиномиальным, если его сложность:

O(n^k)

где k — константа.

Сюда входят:

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(n³)

Не входят:

O(2ⁿ)
O(n!)

NP-трудные задачи¶

Существуют задачи, для которых неизвестно полиномиального алгоритма.

Такие задачи называются NP-трудными.

Это означает:

мы умеем проверять решение быстро,
но не умеем находить его быстро.

В контестах такие задачи либо:

имеют маленькие ограничения,
либо требуют специальных приёмов (битовые маски, meet-in-the-middle и т.д.),
либо допускают приближённые решения.

Итоговая иерархия сложности (от быстрой к медленной)¶

O(1)
O(log n)
O(√n)
O(n)
O(n log n)
O(n²)
O(n³)
O(2ⁿ)
O(n!)

Главное правило для олимпиадника¶

Перед тем как писать код:

Посмотрите на ограничения.
Оцените допустимую сложность.
Подберите подходящий класс алгоритма.

Например:

n ≤ 10 → можно пробовать n!
n ≤ 20 → допустимо 2ⁿ
n ≤ 500 → возможно n³
n ≤ 10⁵ → нужно n или n log n
n ≤ 10⁶ → почти всегда O(n)

Умение быстро сопоставлять ограничения и класс сложности — один из ключевых навыков в спортивном программировании.