Глава 2. Временная сложность¶

В соревновательном программировании эффективность алгоритмов критична. Почти всегда можно придумать решение, которое «в принципе работает», но слишком медленно. Настоящая сложность — найти быстрый алгоритм, который уложится в лимиты времени.

Что такое временная сложность¶

Временная сложность (time complexity) — это оценка того, сколько времени (сколько элементарных операций) потратит алгоритм на входе некоторого размера.

Мы описываем эффективность как функцию от размера входа.
Обычно размер входа обозначают n.
Если вход — массив чисел, то n — длина массива.
Если вход — строка, то n — длина строки.

Оценку записывают как O( … ) («О большое»), где в скобках стоит функция от n. Важно: это не точное число операций, а порядок роста.

2.1 Правила вычисления¶

Ниже — практические правила, которые помогают быстро оценивать сложность кода.

1) Циклы¶

Самая частая причина медленной программы — большое число проходов по данным.

Один цикл → обычно O(n)¶

Если цикл пробегает по входу один раз (или несколько раз, но пропорционально n), то сложность линейная.

Пример:

for (int i = 0; i < n; i++) {
    // O(1) работа
}

Здесь тело выполняется n раз → O(n).

Вложенные циклы → O(n^k)¶

Если есть k вложенных циклов, каждый делает примерно n шагов, то получаем O(n^k).

Пример:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1) работа
    }
}

Тело внутреннего цикла выполнится n * n = n^2 раз → O(n²).

Важно: если пределы циклов разные (например, один по n, другой по m), это уже правило про несколько переменных — см. ниже.

2) Порядок величины¶

Запись O(…) скрывает:

константные множители (например, 7n вместо n),
малые добавки (например, n + 100),
округления вроде floor/ceil.

Потому что при больших n важнее, как растёт функция, а не точное число.

Примеры линейных циклов (все дают O(n))¶

// 5n итераций → O(n)
for (int i = 0; i < 5*n; i++) {
    // ...
}

// n + 42 итерации → O(n)
for (int i = 0; i < n + 42; i++) {
    // ...
}

// шаг 3: примерно n/3 итераций → O(n)
for (int i = 0; i < n; i += 3) {
    // ...
}

Идея: во всех трёх случаях число итераций пропорционально n.

Пример квадратичного поведения¶

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

for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        // ...
    }
}

Внутренний цикл выполняется n-1, потом n-2, …, потом 1 раз. Сумма: (n-1) + (n-2) + ... + 1 = n(n-1)/2, то есть O(n²).

3) Фазы¶

Если алгоритм состоит из нескольких последовательных частей (фаз), то общая сложность обычно равна самой медленной фазе.

Причина: именно «узкое место» (bottleneck) определяет итоговое время.

Пример:

// Фаза 1: O(n)
for (int i = 0; i < n; i++) {
    // ...
}

// Фаза 2: O(n^2)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // ...
    }
}

// Фаза 3: O(n)
for (int i = 0; i < n; i++) {
    // ...
}

Итог: O(n) + O(n²) + O(n) = O(n²).

4) Несколько переменных¶

Иногда время зависит не от одного параметра.

Например, вход может быть матрицей n × m, или есть два независимых размера: число вершин n и число рёбер m.

Пример:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // ...
    }
}

Выполнений: n * m → сложность O(nm).

Как понимать O(nm) на практике¶

Если m ≈ n, то O(nm) превращается примерно в O(n²).
Если m маленькое (например, 26 букв алфавита), то O(nm) фактически почти линейное.

5) Рекурсия¶

Для рекурсивных функций удобно думать так:

Общая сложность = (число вызовов) × (стоимость одного вызова)

Конечно, стоимость одного вызова может сама включать циклы/вызовы — тогда анализ чуть сложнее, но принцип тот же.

Пример 1: линейная рекурсия → O(n)¶

void f(int n) {
    if (n == 0) return;
    f(n - 1);
}

Вызов f(n) порождает цепочку из n+1 вызовов (n, n-1, ..., 0). Каждый вызов делает O(1) работы, значит итог O(n).

Пример 2: «двойное ветвление» → O(2^n)¶

void g(int n) {
    if (n == 0) return;
    g(n - 1);
    g(n - 1);
}

Здесь почти каждый вызов порождает два новых. Число вызовов растёт как:

g(n) — 1 вызов
g(n-1) — 2 вызова
g(n-2) — 4 вызова
…
g(0) — 2^n вызовов

Суммарно: 1 + 2 + 4 + ... + 2^n = 2^(n+1) - 1, то есть O(2^n).

Практический вывод: наивная рекурсия с «раздвоением» почти всегда слишком медленная

Запомните: как быстро оценивать сложность¶

Найди самые «тяжёлые» циклы и глубину вложенности.
Упростись до порядка роста: отбрось константы и добавки.
Разбей код на фазы и возьми максимум.
Если есть несколько размеров входа — используй несколько переменных.
Для рекурсии оцени дерево вызовов: сколько узлов и сколько работы в узле.