Обзор сложности алгоритмов: Big O на практике для C++ разработчика

Введение

Все предыдущие циклы статей писали код, работающий корректно — но не всегда явно анализировали, насколько быстро этот код работает при росте объёма данных. В этой статье разберём нотацию Big O как практический инструмент оценки алгоритмов, без углубления в строгую математическую теорию, но с прямой привязкой к реальным решениям в C++/Qt-коде.

Концепция

Big O описывает, как растёт время выполнения (или потребление памяти) алгоритма по мере роста размера входных данных n, абстрагируясь от конкретных констант (тип процессора, оптимизации компилятора) и фокусируясь на принципиальном характере роста — O(1) (константное время, не зависящее от n), O(log n) (логарифмический рост, как у бинарного поиска), O(n) (линейный рост, один проход по данным), O(n log n) (типичный для эффективных сортировок), O(n²) (квадратичный рост, типичный для наивных, вложенных циклов) и хуже. Практическая ценность этой нотации — для небольших n разница между алгоритмами часто незаметна, но при росте объёма данных алгоритм с худшей сложностью может стать неприемлемо медленным, тогда как алгоритм с лучшей сложностью продолжит работать приемлемо быстро.

Пример кода

// O(n) — поиск элемента линейным проходом по неотсортированному вектору
bool containsLinear(const QVector<int> &data, int target)
{
    for (int value : data) { // один проход — каждый элемент проверяется ровно один раз
        if (value == target) return true;
    }
    return false;
}

// O(n²) — наивная проверка наличия дубликатов через вложенные циклы
bool hasDuplicatesNaive(const QVector<int> &data)
{
    for (int i = 0; i < data.size(); ++i) {
        for (int j = i + 1; j < data.size(); ++j) { // для КАЖДОГО элемента — проверка против ВСЕХ остальных
            if (data[i] == data[j]) return true;
        }
    }
    return false;
}

// O(n) — та же задача, но через хеш-множество — кардинально другая сложность
bool hasDuplicatesHashSet(const QVector<int> &data)
{
    QSet<int> seen;
    for (int value : data) {
        if (seen.contains(value)) return true; // O(1) проверка в среднем случае
        seen.insert(value);
    }
    return false;
}

Практическое сравнение при росте n (условные единицы времени, не точные измерения):

n = 1000:    O(n) ≈ 1000 шагов      O(n²) ≈ 1 000 000 шагов
n = 10000:   O(n) ≈ 10000 шагов     O(n²) ≈ 100 000 000 шагов
n = 100000:  O(n) ≈ 100000 шагов    O(n²) ≈ 10 000 000 000 шагов

При увеличении n в 10 раз — O(n) растёт в 10 раз, O(n²) растёт в 100 раз

Пояснения к коду

hasDuplicatesNaive и hasDuplicatesHashSet решают одну и ту же задачу с принципиально разной сложностью — наивная версия проверяет каждый элемент против каждого другого (квадратичный рост числа операций), тогда как версия с QSet тратит на каждый элемент в среднем константное время на проверку и вставку, превращая общую сложность в линейную; для небольшого вектора (десятки элементов) разница практически не ощутима, но для вектора из сотен тысяч элементов наивная версия может выполняться заметно дольше — секунды или минуты против миллисекунд. Таблица сравнения роста показывает суть практической ценности Big O — она не даёт точное время в секундах (которое зависит от конкретного оборудования), но даёт понимание, как радикально по-разному масштабируются разные подходы при увеличении объёма данных.

Подводные камни

Преждевременная оптимизация сложности алгоритма для данных, которые заведомо никогда не будут большими — если известно, что обрабатываемый список данных содержит максимум несколько десятков элементов и эта характеристика не изменится в будущем, переход от простого, понятного O(n²)-решения к более сложному O(n)-решению может не дать измеримой практической выгоды, но добавит сложности коду; анализ Big O важен именно там, где объём данных действительно может расти, а не как универсальное правило для абсолютно любого кода.
Игнорирование констант и скрытых издержек, не отражённых в нотации Big O — алгоритм с формально лучшей асимптотической сложностью может на практике быть медленнее для конкретного, не очень большого n из-за более высоких «накладных расходов на операцию» (например, хеширование в QSet дороже простого сравнения целых чисел) — Big O описывает поведение при n, устремляющемся к большим значениям, а не гарантирует превосходство для любого конкретного, в том числе малого n.
Путаница между сложностью по времени и сложностью по памяти — оптимизация одной часто требует компромисса с другой (например, hasDuplicatesHashSet тратит дополнительную память на QSet для достижения лучшей временной сложности по сравнению с hasDuplicatesNaive, не требующей дополнительной памяти вовсе), и разбор алгоритма должен явно учитывать оба измерения сложности, особенно для embedded-контекста (STM32-цикла) с жёстко ограниченной доступной памятью.
Анализ сложности только для «среднего» случая без учёта худшего случая — некоторые структуры данных (хеш-таблицы) дают отличную среднюю сложность, но имеют существенно худшую сложность в редких, но возможных худших случаях (массовые коллизии хешей), и для систем с жёсткими требованиями к предсказуемости времени выполнения (real-time embedded системы, STM32-цикл) недостаточно знать только усреднённое поведение алгоритма — нужно явно понимать и его гарантированный худший случай.