Сложность: O(1), O(n), O(n log n)

Представьте плиточника, который выкладывает квадратный пол. В каждом ряду n плиток, рядов тоже n, поэтому весь пол — это n · n плиток. Комната со стороной 10 плиток требует 100 плиток, а со стороной 1000 — уже миллион. Сторона выросла в 100 раз, а работа — в 10 000 раз.

Программы растут так же. Две функции могут давать один и тот же ответ, но на большом векторе одна работает доли секунды, а другая — часы. Разницу видно, если посчитать шаги. Функция count_steps кладёт по одной «плитке» ++steps на каждую пару i и j: внешний цикл идёт по рядам, а внутренний — по плиткам в ряду.

#include <iostream>

int count_steps(int n) {
    int steps = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ++steps;
        }
    }
    return steps;
}

int main() {
    std::cout << count_steps(10) << ' ' << count_steps(1000) << '\n';  // 100 1000000
}

Входные данные выросли в 100 раз, а число шагов — в 10 000 раз, точно как у плиточника.

Здесь аналогия заканчивается: настоящие шаги программы не одинаковы по времени, как плитки. Сложность не говорит, сколько секунд займёт работа. Она говорит, во сколько раз работа вырастет, когда вырастут данные.

Запись O(…)

Сложность алгоритма показывает, как число шагов растёт вместе с размером входных данных n. Её записывают в O-нотации: count_steps делает n² шагов, и сложность этой функции — O(n²).

Постоянные множители и меньшие слагаемые отбрасывают:

• 3n + 5 шагов — это O(n);
• n²/2 шагов — это O(n²).

При больших n они почти не меняют картину роста.

Обычно сложность указывают для худшего случая — входа, на котором алгоритм делает больше всего шагов. Поиск, который останавливается на найденном элементе, в худшем случае ничего не находит и проверяет все n элементов. Поэтому его сложность — O(n), хотя иногда он заканчивается на первом шаге.

В таблице ниже встречается log n — это сколько раз n можно поделить пополам, пока не останется 1. Для миллиона это около 20.

Оценка по коду

Сложность можно прочитать прямо по циклам:

• один цикл по n элементам — это O(n);
• вложенные циклы перемножают числа шагов: n раз по n — O(n²);
• циклы, которые идут друг за другом, складываются, и остаётся больший: O(n) + O(n²) — это O(n²);
• цикл, который на каждом шаге ищет ключ в std::map, перемножает сложности: n раз по log n — O(n log n);
• цикл, который на каждом шаге делит n пополам, делает около log₂ n шагов — это O(log n).

Внутренний цикл часто начинают с i + 1, чтобы не сравнивать одну пару дважды. Плиточник кладёт тогда только половину квадрата, но всего это n(n−1)/2 шагов, и сложность остаётся O(n²). Вопрос «какая сложность у этого кода?» часто задают на собеседовании.

Частая ошибка

Элементы вектора обрабатывают по одному, каждый раз удаляя первый:

std::vector<int> v{3, 1, 2};
while (!v.empty()) {
    std::cout << v[0] << ' ';
    v.erase(v.begin());  // ✗
}

Программа выводит верный результат, но на большом векторе работает медленно. Цикл выглядит как O(n), однако erase сдвигает все оставшиеся элементы на одно место влево. Для n элементов это n − 1, n − 2, … сдвигов, всего O(n²). Обойдите вектор циклом по диапазону: это O(n), и удалять ничего не нужно.

Главное

• Сложность показывает, во сколько раз вырастет работа, когда вырастут данные.
• Множители и меньшие слагаемые отбрасывают, а сложность указывают для худшего случая.
• Вложенные циклы перемножают шаги, последовательные — складываются.
• erase из начала вектора внутри цикла превращает O(n) в O(n²).