Что такое O-нотация? Оцените сложность примеров кода и объясните, почему O(n log n) — практический предел для сортировки сравнениями.

Основной ответ

O(f(n)) означает: начиная с некоторого n, число операций ограничено c * f(n). Поэтому O(3n + 10) = O(n): константы и младшие члены не влияют на характер роста. Практические правила: последовательные блоки складываются и доминирует больший; вложенные циклы перемножаются (двойной цикл по n — O(n^2)); сокращение задачи вдвое на шаге — O(log n); «для каждого из n делаем log n» — O(n log n). Амортизированная сложность усредняет редкие дорогие операции — например, append в динамический массив в среднем O(1). Сортировка сравнениями не может быть быстрее O(n log n): n! перестановок требуют log(n!) ≈ n log n бинарных сравнений, чтобы различить их. Память анализируется теми же правилами, и типичный приём интервью — обменять O(n) памяти на ускорение с O(n^2) до O(n).

Ключевые моменты

• Асимптотика, не секундомер. O(n) с огромной константой может проигрывать O(n^2) на малых n; нотация — о характере роста, не о скорости конкретного кода.
• Правила композиции. Сложение для последовательных блоков, умножение для вложенных, логарифм для деления пополам — этим разбирается почти любой код.
• Нижняя граница сортировки. Дерево решений из сравнений должно иметь n! листьев, значит глубина не меньше log2(n!) = O(n log n); counting/radix sort обходят границу, потому что не сравнивают.
• Скрытые сложности. Операции вроде среза списка, конкатенации строк или 'in' по списку — O(n), и их легко не заметить внутри цикла.

Практический контекст

Сложность спрашивают после каждой решённой задачи, поэтому называйте её сами, не дожидаясь вопроса, и по времени, и по памяти. Интервьюер любит ловушки: строковая конкатенация в цикле (O(n^2)), 'x in list' внутри цикла, скрытая сортировка. Уточняйте, о каком случае речь — худшем, среднем или амортизированном: для hash map и quicksort разница принципиальна.

Пример кода

def has_dup_quadratic(a):
    # O(n^2) времени, O(1) памяти: все пары
    n = len(a)
    return any(a[i] == a[j] for i in range(n) for j in range(i + 1, n))

def has_dup_linear(a):
    # O(n) времени, O(n) памяти: обмен памяти на время
    return len(set(a)) < len(a)

def halves(n):
    # O(log n): деление пополам на каждом шаге
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

assert has_dup_quadratic([1, 2, 3, 2]) and has_dup_linear([1, 2, 3, 2])
assert not has_dup_quadratic([1, 2, 3]) and not has_dup_linear([1, 2, 3])
assert halves(1024) == 10

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

• Оценивают только время и забывают память, включая стек рекурсии
• Не замечают O(n)-операций внутри цикла: 'in' по списку, срезы, конкатенация строк
• Путают средний и худший случай — например, называют поиск в хэш-таблице безусловным O(1)