Сложность работы контейнеров: скрытый O(N²)

1. Введение

Когда вы только начинаете программировать, логика обычно такая: «Главное — чтобы компилировалось и не падало». Это нормальный этап. Но довольно быстро появляются программы, которые не падают… они просто думают слишком долго. И самое неприятное: внешне код может выглядеть невинно — один цикл, пара проверок, вроде всё «по‑человечески».

Сложность по Big‑O — это способ прикинуть, как будет расти время работы, если данных станет больше. Сегодня мы будем делать это без формальных доказательств и матана: только «сколько раз мы делаем полный проход по контейнеру» и почему вложенные проходы превращают программу в сонный режим.

Big‑O «на пальцах»: считаем проходы по контейнеру

Давайте договоримся о «модели дня». Пусть N — количество элементов в контейнере (v.size()). Один полный проход по контейнеру — это когда мы потенциально заглядываем в каждый элемент один раз (или почти один раз).

Если мы делаем один такой проход, это похоже на O(N). Если делаем два прохода подряд — всё ещё O(N) (просто чуть дольше, но растёт линейно). А вот если внутри одного прохода мы запускаем ещё один полный проход, то получается примерно N * N действий, то есть O(N²).

Интересный факт из мира стандартной библиотеки: даже в стандарте C++ есть «договорённость о записи» сложности, например писать N log N, а не N log(N) — чтобы было единообразно в документации.

Небольшая табличка, чтобы мозг цеплялся глазами:

2. Линейная сложность: O(N) и «2N всё ещё O(N)»

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

Давайте продолжим наше маленькое учебное приложение. Пусть это будет «мини‑журнал тренировок»: у нас есть оценки/баллы за тренировки (или за тесты — смысл не важен, важно, что это числа), и мы хотим посчитать статистику.

Пример: сумма за один проход

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 8, 15};

    int sum = 0;
    for (int x : scores) {
        sum += x;
    }

    std::cout << "sum=" << sum << '\n'; // sum=45
}

Здесь мы «трогаем» каждый элемент ровно один раз — это классический O(N).

Пример: максимум за один проход

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 8, 15};

    int best = scores[0];
    for (std::size_t i = 1; i < scores.size(); ++i) {
        if (scores[i] > best) best = scores[i];
    }

    std::cout << "best=" << best << '\n'; // best=15
}

Опять один проход. Даже если данных будет в 100 раз больше, время вырастет примерно в 100 раз. Это обычно нормально.

Два последовательных прохода — это не O(N²)

Очень частая ошибка новичка — думать, что «если я сделал два цикла, то это сразу O(N²)». Нет. O(N²) появляется, когда циклы вложенные, а не стоящие рядом.

Два последовательных прохода — это примерно N + N = 2N, а в Big‑O константы выкидываются. То есть остаётся O(N). Это не означает, что константы не важны вообще, просто сегодня мы смотрим именно на форму роста.

Пример: сначала сумма, потом печать (2 прохода, но O(N))

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 8, 15};

    int sum = 0;
    for (int x : scores) sum += x;

    for (int x : scores) {
        std::cout << x << ' ';
    }
    std::cout << "\n"; // 10 12 8 15
}

Здесь два прохода, но не «катастрофа». Иногда так даже читабельнее, чем пытаться втиснуть всё в один цикл и превратить код в «комбайн».

4. Квадратичность: явная O(N²) и «скрытый O(N²)»

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

Важно другое: вы должны узнавать этот паттерн и понимать цену.

Пример: считаем количество равных пар (явная O(N²))

#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 10, 15};

    int equalPairs = 0;
    for (std::size_t i = 0; i < scores.size(); ++i) {
        for (std::size_t j = i + 1; j < scores.size(); ++j) {
            if (scores[i] == scores[j]) ++equalPairs;
        }
    }

    std::cout << "equalPairs=" << equalPairs << '\n'; // equalPairs=1
}

Почему это O(N²)? Потому что для каждого i мы пробегаем много j. При N = 4 это выглядит мелко и мило. При N = 10000 — внезапно «почему мой ноутбук улетел в космос».

«Скрытый O(N²)»: второй проход спрятан внутри логики

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

Снаружи выглядит как один цикл. Внутри оказывается, что на каждой итерации вы снова проходите весь контейнер. И это почти всегда главный источник неожиданно медленных программ у новичков.

Пример: для каждого значения посчитать, сколько раз оно встречается (скрытый O(N²))

#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 10, 15, 10};

    for (std::size_t i = 0; i < scores.size(); ++i) {
        int cnt = 0;
        for (std::size_t j = 0; j < scores.size(); ++j) {
            if (scores[j] == scores[i]) ++cnt;
        }
        std::cout << scores[i] << " -> " << cnt << '\n';
    }
}

Это тот же O(N²), но психологически он часто воспринимается как «ну я же просто печатаю отчёт». Вот тут и ловушка: «просто отчёт» может быть очень дорогим, если он для каждого элемента пересчитывает что-то с нуля.

Чтобы закрепить визуально, вот маленькая блок‑схема идеи:

flowchart TD
    A[Берём элемент i] --> B[Счётчик = 0]
    B --> C[Проходим весь контейнер j=0..N-1]
    C --> D{"scores[j] == scores[i]?"}
    D -->|да| E[увеличить счётчик]
    D -->|нет| C
    E --> C
    C --> F[Печатаем результат для i]
    F --> A

Если вы видите «для каждого i мы делаем полный проход j», мозг должен автоматически шепнуть: «пахнет N²».

Пример: «проверим, был ли элемент раньше» (скрытая квадратичность через поиск)

Вот ещё один очень типичный сценарий. Мы хотим выяснить, встречался ли элемент ранее, чтобы печатать только «первые появления». Логика нормальная. Реализация без дополнительных структур данных обычно выглядит так:

#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 10, 15, 12};

    for (std::size_t i = 0; i < scores.size(); ++i) {
        bool seenBefore = false;
        for (std::size_t j = 0; j < i; ++j) {
            if (scores[j] == scores[i]) {
                seenBefore = true;
                break;
            }
        }

        if (!seenBefore) {
            std::cout << "first time: " << scores[i] << '\n';
        }
    }
}

Здесь внутренний цикл идёт не до N, а до i, но по порядку роста это всё равно квадратично (примерно «треугольник» сравнений). И да: break помогает «в среднем», но худший случай (все элементы разные) остаётся квадратичным.

5. Как отличать O(N) от «скрытого O(N²)» по коду

Когда вы читаете код, полезно выработать привычку: не просто понимать «что делает», а ещё и задавать себе вопрос «сколько раз это делается».

Хорошая мысленная техника: берём участок кода и ищем, есть ли внутри него полный проход по контейнеру. Если внутри одного полного прохода вы находите ещё один полный проход по тому же контейнеру (или по контейнеру такого же размера), это почти наверняка O(N²).

Ещё одна техника попроще: представьте, что scores.size() стало равно 100000. Сколько раз выполнится строка в самом «глубоком месте»? Если вы видите, что она выполнится примерно 10^10 раз — вы только что нашли причину будущей печали.

Небольшая подсказка‑таблица «что настораживает»:

6. Рефакторинг: убираем лишние проходы, когда они не нужны

Важно уточнение: убрать O(N²) можно не всегда, потому что иногда задача реально «каждый с каждым». Но очень часто квадратичность появляется просто потому, что мы пере‑считываем одно и то же.

Классический пример: вы хотите для каждого элемента вывести «сколько процентов от общей суммы он составляет». Наивный вариант — внутри цикла каждый раз считать сумму заново. Это и есть скрытый O(N²).

Плохой вариант: сумма пересчитывается N раз

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 8, 15};

    for (int x : scores) {
        int sum = 0;
        for (int y : scores) sum += y; // полный проход каждый раз

        std::cout << x << "/" << sum << '\n'; // 10/45, 12/45, ...
    }
}

Логика верная. Скорость — нет.

Хороший вариант: сумма считается один раз

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores{10, 12, 8, 15};

    int sum = 0;
    for (int y : scores) sum += y;

    for (int x : scores) {
        std::cout << x << "/" << sum << '\n'; // 10/45 ...
    }
}

Здесь два прохода, но это O(N), и вы перестали делать лишнюю работу.

Похожая идея работает и для других «глобальных величин» контейнера: максимум, минимум, количество элементов, количество положительных и так далее. Если вы каждый раз заново считаете «что-то по всему контейнеру» внутри цикла по контейнеру — вы почти гарантированно устроили себе N².

7. Типичные ошибки

Ошибка №1: путать два последовательных цикла и вложенные циклы.
Если один цикл закончился, и потом начался другой — это обычно O(N). Квадратичность появляется, когда второй полный проход находится внутри первого и выполняется много раз. Полезно буквально пальцем вести по коду: «этот проход происходит N раз или один раз?».

Ошибка №2: незаметно пересчитывать общую статистику внутри цикла по элементам.
Самый частый скрытый O(N²) — это когда вы для каждого элемента снова считаете сумму, максимум или количество чего-то по всему контейнеру. Исправляется простым приёмом: сначала посчитать общую величину один раз, потом использовать её в выводе/проверках.

Ошибка №3: считать, что break «лечит» квадратичность.
break действительно может ускорить средний случай, когда нужное находится быстро. Но худший случай часто остаётся O(N²). Если вы обрабатываете данные, где худший случай реалистичен (например, все элементы различны), то break не спасает и проблему нужно видеть заранее.

Ошибка №4: не замечать, что поиск — это тоже цикл.
Даже если вы не написали второй цикл явно, но внутри внешнего обхода делаете ручной поиск по контейнеру, вы фактически сделали вложенный проход. Полезно мысленно заменять «поиск» на «внутренний цикл» — и сразу становится видно, почему программа может тормозить.

Ошибка №5: пытаться оптимизировать раньше времени, но не уметь оценивать форму роста.
Иногда новички начинают бороться за микроскопические улучшения (например, переставить строки местами), игнорируя главного монстра: лишний полный проход внутри другого полного прохода. Сначала ищем форму (O(N) или O(N²)), и только потом думаем о мелких улучшениях.