Big O: время и память

Big O описывает верхнюю асимптотическую границу роста затрат при росте размера входа $n$, отбрасывая постоянные множители и младшие члены. Обычно отдельно говорят о времени и дополнительной памяти: быстрый поиск в hash map может требовать памяти, а сортировка на месте — менять входной массив.

Зачем это на интервью

Нужно уметь выбрать структуру данных под операцию и честно назвать её цену. Интервьюер ожидает не только «$O(1)$», но и условия: средний или худший случай, что считается входом, какая память занята и как решение ведёт себя при реальных данных.

Минимум для E4

• Определять $n$ и считать вложенные проходы, а не количество строк кода.
• Различать $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$ и $O(n^2)$.
• Указывать дополнительную память отдельно от памяти входа.
• Называть средний и худший случай, если они различаются.

Один цикл по массиву — $O(n)$; два последовательных цикла также $O(n)$, потому что $2n$ асимптотически растёт как $n$. Два вложенных прохода по независимым диапазонам дают произведение: $O(nm)$, а при $m=n$ — $O(n^2)$. Бинарный поиск требует отсортированного массива и делает $O(\log n)$ сравнений.

Углубление для E5/Senior

Асимптотика — модель, а не latency budget. Для E5 важно связать её с распределением входов и ресурсами: hash table даёт ожидаемое $O(1)$ при корректном распределении хешей, но resize и коллизии меняют наблюдаемую стоимость; сортировка может быть $O(n\log n)$, но лишняя копия увеличит peak memory и давление на GC. При выборе API также считают стоимость на границе: сериализация, сетевой round trip и N+1 запросов способны доминировать над сложностью локального алгоритма.

Сложность описывают для конкретной операции. map не делает весь сервис $O(1)$: построение индекса, обработка каждого ключа и объём данных сохраняют зависимость от $n$. Для неизвестного масштаба полезно записать модель, затем проверить её benchmark-ом на малом, типичном и предельном входе.

Ключевые понятия

• Входной размер $n$ — параметр, от которого растут затраты; для графа часто нужны $V$ вершин и $E$ рёбер.
• Временная сложность — число базовых операций в модели; это не точные наносекунды.
• Дополнительная память — память сверх входа и результата, если явно не оговорено другое.
• Худший случай — верхняя граница на всех допустимых входах; средний/ожидаемый требует модели распределения или вероятности.
• In-place — алгоритм использует ограниченную дополнительную память, но может изменять входные данные.
• Асимптотическая нотация — $O$ задаёт верхнюю границу; $\Theta$ — тесную границу порядка роста, когда она доказана.

Типовые вопросы

1. Почему два последовательных цикла — не $O(n^2)$?
   • Они выполняют примерно $n+n=2n$ шагов; постоянный множитель отбрасывается, поэтому $O(n)$.
2. Какова сложность поиска в hash map?
   • Обычно ожидаемое $O(1)$ на операцию, но это зависит от хеширования и коэффициента заполнения; худший случай может быть хуже.
3. Почему binary search не всегда подходит?
   • Он требует отсортированной коллекции и случайного доступа; надо учесть стоимость сортировки и обновлений.
4. Что значит $O(nm)$?
   • Есть два независимых размера: например, перебор $n$ пользователей и $m$ прав каждого. Нельзя без основания заменить на $O(n^2)$.
5. Может ли $O(n^2)$ быть приемлемым?
   • Да, при малом ограниченном $n$ или редкой фоновой операции; решение обосновывают лимитом, измерением и budget-ом.
6. Почему $O(1)$ не означает мгновенно?
   • Константа может включать кэш-промах, аллокацию, lock или системный вызов; асимптотика не измеряет их.

Практика

• Оцените время и дополнительную память для deduplication массива из $n$ строк через вложенный поиск и через map[string]struct{}. Готово: для обоих вариантов указаны средний и худший случай, судьба порядка элементов и используемая дополнительная память.
• Реализуйте поиск пары с заданной суммой: квадратичный проход и вариант с hash map. Готово: тесты покрывают пустой, повторяющийся и большой вход; benchmark сравнивает одинаковые данные и показывает ns/op, B/op, allocs/op.
• Разберите путь списка ID в SQL. Готово: обозначены размер списка, число round trip, риск N+1 и хотя бы один способ измерить реальную стоимость.

Частые ошибки и ловушки

• Называть сложность без определения $n$ и без различения среднего и худшего случая.
• Забывать память на копию результата, индекс или рекурсивный стек.
• Считать, что вложенный цикл всегда $O(n^2)$: диапазоны могут быть разными или внутренний указатель двигаться монотонно.
• Оптимизировать локальный $O(n)$ код, когда узким местом является сеть или база данных.
• Сравнивать benchmark-ы на разных входах либо без защиты результата от оптимизации компилятором.

Связанные темы

Производительность и память · Амортизированная сложность · Локальность данных · Алгоритмы и структуры данных

Источники

• Thomas H. Cormen et al., Introduction to Algorithms, главы об асимптотическом анализе.
• Robert Sedgewick and Kevin Wayne, Algorithms, разделы об анализе алгоритмов.
• Go project, The Go Programming Language Specification, разделы о map и slice.
• Go project, документация пакета testing, раздел Benchmarks.