Big O: как оценивать сложность

Сравните идеи до написания кода: посчитайте, как растёт работа с размером входа, и проверьте, сколько памяти требует состояние.

Что измеряет Big O

Big O описывает верхнюю асимптотическую границу роста работы алгоритма при увеличении входа. Сначала определите, что значит n: длина массива, число вершин, длина строки или число запросов. Затем посчитайте основные операции. Для 3n + 12 достаточно O(n): постоянный множитель и добавка не меняют порядок роста.

Это не число секунд и не доказательство корректности. Запись O(n²) для линейного алгоритма формально тоже даёт верхнюю границу, но слишком грубую. Обычно ищут содержательную оценку; если нужен именно точный порядок роста сверху и снизу, используют Θ (тета).

Почему мы смотрим на рост? Решение, которое быстро работает на десяти элементах, может оказаться непригодным на ста тысячах. Когда вход увеличивается в десять раз, линейная работа растёт примерно в десять раз, а квадратичная — в сто. Так можно сравнивать идеи ещё до кода и измерений.

Основные классы сложности

В таблице операции с индексами и числами фиксированной разрядности считаются постоянными. Стоимость сравнения длинных строк и арифметики больших чисел нужно учитывать отдельно.

Рост	Что происходит	Пример	Важное условие
`O(1)`	Объём работы не растёт с `n`	Чтение элемента массива по индексу	Индекс корректен; весь массив уже хранится
`O(log n)`	Остающееся пространство уменьшается в постоянное число раз	Бинарный поиск	Вход упорядочен, доступ к середине стоит `O(1)`
`O(n)`	Каждый элемент обрабатывается ограниченное число раз	Поиск максимума одним проходом	Сравнение и обновление состояния стоят `O(1)`
`O(n log n)`	Для всех элементов нужна логарифмическая работа или уровни разбиения	Merge sort	Сравнение элементов стоит `O(1)`
`O(n²)`	Перебираются пары элементов	Проверка всех пар на дубликаты	Работа с одной парой постоянна
`O(2ⁿ)`	Рассматриваются все подмножества	Перебор масок	Оценка числа масок; просмотр всех битов каждой добавит множитель `n`
`O(n!)`	Рассматриваются все перестановки	Полный перебор порядков	Оценка числа кандидатов; построение каждого ответа тоже стоит времени

Постоянное время. O(1) не означает одну инструкцию. Десять проверок без зависимости от n всё ещё дают постоянный порядок.

Логарифмическое время. При делении диапазона пополам остаётся около log₂ n шагов: для миллиона элементов — примерно двадцать. Основание логарифма меняет постоянный множитель, а не класс Big O. Сортировка несортированного массива перед единственным поиском — отдельная стоимость.

Линейное время. Два последовательных прохода дают 2n действий, то есть O(n). Вложенный цикл тоже может оставаться линейным: если два указателя никогда не идут назад, число всех сдвигов ограничено длиной массива. Нужно считать суммарную работу, а не отступы кода.

Квадратичное время. Проверка пар с i < j выполняется n(n − 1)/2 раз. Половина не меняет O(n²). Если же внутри каждой пары заново просматривать весь массив, получится уже O(n³).

Экспонента и факториал. При n = 20 существует 1 048 576 подмножеств; при n = 10 — 3 628 800 перестановок. Даже небольшое увеличение n существенно меняет перебор. Если задача требует вывести все варианты, учитывайте также общий размер вывода.

Как размер входа помогает отсеять идею

Ниже значения функций роста, а не прогноз времени выполнения. n log₂ n округлено; одно «действие» может стоить очень по-разному.

Размер входа `n`	`n`	`n log₂ n`, примерно	`n²`
1 000	1 000	10 000	1 000 000
100 000	100 000	1 660 000	10 000 000 000

Если n около двадцати, перебор подмножеств иногда разумен. На нескольких тысячах элементов простой квадратичный алгоритм иногда укладывается в лимиты. На сотнях тысяч сначала рассматривайте линейные идеи или сортировку. Это фильтр, а не универсальная таблица «допустимых секунд»: проверьте язык, число тестов, лимиты памяти, работу внутри цикла и ограничения по сумме размеров входов.

Попробуйте сами: для поиска пары на n = 100 000 полный перебор проверит почти пять миллиардов пар. После сортировки встречные указатели проверят не больше n − 1 текущих пар, но итоговая оценка включает сортировку. Подробное доказательство есть в уроке о двух указателях.

Время и память оцениваются отдельно

Поиск дубликата перебором использует O(1) дополнительной памяти, но O(n²) времени. Множество даёт ожидаемое O(n) времени ценой O(n) памяти. Ускорение не бесплатно: выбирайте решение по обоим ограничениям.

Различайте память входа, ответа и дополнительного состояния. Массив уже передан в функцию — это вход; его копия — дополнительная память. Стек рекурсивных вызовов тоже занимает память. Таблица из n × m ячеек требует O(nm) элементов, а реальное число байтов зависит от языка и представления. Python-объекты и контейнеры имеют накладные расходы: одинаковая Big O не означает одинаковый размер в байтах.

Стоимость операций структур данных

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

Структура	Операция	Оценка	Оговорка
Динамический массив (C++ `std::vector`, Python `list`)	Доступ по индексу	`O(1)`	Поиск значения требует прохода `O(n)`
Динамический массив	Добавление в конец	Амортизированно `O(1)`	Отдельное расширение может стоить `O(n)`
Динамический массив	Вставка или удаление внутри	`O(n)`	Последующие элементы нужно сдвинуть
Хеш-таблица	Поиск, вставка, удаление	Поиск и удаление ожидаемо `O(1)`, вставка ожидаемо амортизированно `O(1)`	Отдельная операция может стоить `O(n)` из-за коллизий или расширения; это не гарантия worst case
Стек на динамическом массиве	Чтение вершины, удаление с конца	`O(1)`	Добавление амортизированно `O(1)`
Очередь на деке	Добавление и удаление на концах	`O(1)`	Метод `pop(0)` у Python `list` сдвигает элементы за `O(n)`
Двоичная куча	Чтение экстремума	`O(1)`	Куча не хранит весь набор отсортированным
Двоичная куча	Вставка, удаление экстремума	Просеивание `O(log n)`	Рост массива может добавить отдельное `O(n)`; вставка амортизированно `O(log n)`
Двоичная куча	Построение из всех элементов	`O(n)`	Последовательные вставки дают верхнюю оценку `O(n log n)`

В C++ используйте контракт выбранного STL-контейнера, в Python — соответствующий контейнер, а не похожее имя. Для очереди подходит collections.deque; для min-heap — heapq. Справочник структур данных помогает уточнить модель перед реализацией.

Худший, средний и амортизированный случай

Худший случай рассматривает наиболее дорогой вход заданного размера. Ранний выход из линейного поиска даёт O(1) на первом элементе, но не меняет worst case O(n).

Средний или ожидаемый случай требует допущений о входе либо случайности. Поиск в хеш-таблице обычно оценивают как ожидаемый постоянный; при плохих коллизиях эта оценка не даёт гарантии для каждого входа.

Амортизированная оценка считает стоимость серии операций, а не случайный вход. Динамический массив иногда копирует элементы при расширении, но при обычном геометрическом росте суммарная стоимость серии добавлений остаётся линейной. Это другой аргумент, чем вероятностная оценка хеширования.

Ошибки, которые меняют итоговую оценку

Игнорировать подготовку. Линейный проход после сортировки не делает всё решение O(n).
Путать размеры. Для двух массивов длины n и m полный перебор пар — O(nm).
Считать библиотечный вызов бесплатным. Срез, копирование, сравнение строк и поиск в списке могут добавлять работу внутри внешнего цикла.
Забывать рекурсию и ответ при оценке памяти.
Принимать Big O за точный замер. Сравнивать константы можно измерением на репрезентативных входах, но несколько быстрых примеров не доказывают худшую оценку.

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

Продолжить курс

Начните с оценки бюджета по ограничениям, затем разберите переход от перебора к множеству и стоимость контейнеров C++ и Python. Следующий шаг — выбирать паттерн по свойствам задачи, а весь порядок тем находится в курсе AlgoDS.

Для сверки определений: материалы MIT об асимптотике, документация Python о контейнерах и heapq.