Что такое big-O и зачем он на собеседовании

Учимся отвечать на главный вопрос интервьюера: «А какая сложность вашего решения?»

Big-O — это способ описать, как быстро растёт время работы (или память) алгоритма при росте размера входных данных, отбрасывая константы и младшие слагаемые.

Зачем это нужно

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

Как читать нотацию

Мы смотрим на главный источник роста и игнорируем остальное. Если алгоритм делает 3n + 100 операций, мы говорим O(n): константа 3 и слагаемое 100 не важны при больших n. Если делает n*n/2, это O(n^2).

Ключевые классы роста, от лучшего к худшему:

O(1)	константа: доступ к элементу массива по индексу
O(log n)	логарифм: бинарный поиск
O(n)	линейно: один проход по массиву
O(n log n)	хорошие сортировки
O(n^2)	квадрат: вложенные циклы по всем парам
O(2^n)	экспонента: перебор всех подмножеств

Считаем на практике

Посчитаем число операций для разных размеров входа и увидим, как взрывается рост. Цикл, вложенный в цикл, даёт квадрат.

def operations(n):
    linear = n
    quadratic = n * n
    log = 0
    x = n
    while x > 1:
        x = x // 2
        log += 1
    return linear, quadratic, log

for n in [10, 100, 1000]:
    lin, quad, lg = operations(n)
    print(n, "-> O(n):", lin, "O(n^2):", quad, "O(log n):", lg)

Вывод:

10 -> O(n): 10 O(n^2): 100 O(log n): 3
100 -> O(n): 100 O(n^2): 10000 O(log n): 6
1000 -> O(n): 1000 O(n^2): 1000000 O(log n): 9

Как работает под капотом

Big-O — это асимптотическая верхняя оценка. Формально f(n) = O(g(n)), если существуют константы c и n0, такие что f(n) <= c*g(n) для всех n >= n0. На практике это значит: при достаточно больших n кривая времени не превысит масштабированную g(n). Именно поэтому мы отбрасываем константы — они влияют на «крутизну», но не на класс роста. Есть и родственники: O — верхняя оценка, Omega — нижняя, Theta — точная (и сверху, и снизу).

Частые ошибки

Путать худший и средний случай. Быстрая сортировка в среднем O(n log n), но в худшем O(n^2).
Складывать сложности вложенных циклов вместо умножения. Вложенные циклы — это умножение, последовательные — сложение (берём больший).
Забывать про сложность по памяти. Рекурсия глубины n тратит O(n) стека, даже если «по времени всё хорошо».
Оставлять константы и думать, что O(2n) лучше O(n). Это одно и то же.

Итог

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