Вопросы про сложность алгоритмов на собеседовании

Коротко

Вопрос «какая здесь сложность?» задают почти на каждом собеседовании. Ошибаются на нём чаще, чем кажется, — обычно из-за скрытых операций внутри цикла.

Как считать сложность реального кода

Правило 1: складываем последовательное, умножаем вложенное

for x in a:      # O(n)
    ...
for y in b:      # O(m)
    ...
# итого O(n + m)

for x in a:      # O(n)
    for y in b:  # O(m)
        ...
# итого O(n · m)

Правило 2: отбрасываем константы и младшие члены

O(3n² + 5n + 100) = O(n²). Константы важны на практике, но в асимптотике их не пишут.

Правило 3: считайте каждую строку, а не решение целиком

Здесь и кроется главная ловушка.

Скрытые операции: главный источник ошибок

Многие операции выглядят дешёвыми, но таковыми не являются.

Python

# O(n), а не O(1)
if x in my_list:              # линейный поиск по списку
s = s + 'a'                   # создание новой строки
sub = arr[1:100]              # срез копирует
arr.insert(0, x)              # сдвиг всех элементов
arr.pop(0)                    # тоже сдвиг
max(arr)                      # проход по всему

# O(1)
if x in my_set:               # хеш
if x in my_dict:              # хеш
arr.append(x)                 # амортизированно
arr.pop()                     # с конца

Классический пример скрытого квадрата:

# выглядит как O(n), на деле O(n²)
result = ''
for ch in text:
    result += ch          # каждая конкатенация создаёт новую строку

# правильно: O(n)
result = ''.join(text)

И ещё один:

# O(n²) — поиск по списку внутри цикла
seen = []
for x in nums:
    if x not in seen:     # O(n) на каждой итерации
        seen.append(x)

# O(n) — поиск по множеству
seen = set()
for x in nums:
    if x not in seen:     # O(1)
        seen.add(x)

JavaScript

arr.indexOf(x)      // O(n)
arr.includes(x)     // O(n)
arr.shift()         // O(n) — сдвиг всего массива
arr.unshift(x)      // O(n)
arr.splice(i, 1)    // O(n)
arr.push(x)         // O(1) амортизированно
set.has(x)          // O(1)
map.get(x)          // O(1)

arr.shift() в цикле — самая частая скрытая ошибка в JavaScript. Очередь на массиве превращается в квадрат.

Амортизированная сложность

Отдельная тема, которую любят на позициях middle и выше.

list.append() в Python — O(1) амортизированно. Отдельная вставка может стоить O(n), если массив расширяется, но такое случается редко.

Механика: при нехватке места ёмкость удваивается и все элементы копируются. Но следующие n вставок пройдут без расширения. Суммарно на n вставок приходится меньше 2n операций копирования, то есть меньше двух на элемент.

Важное уточнение: амортизированная оценка — это гарантия для последовательности операций, а не средний случай. Разницу иногда специально спрашивают.

Сложность по памяти

Забывают чаще, чем время, а спрашивают почти всегда.

# O(1) по памяти — только счётчик
def total(nums):
    s = 0
    for x in nums:
        s += x
    return s

# O(n) по памяти — новый список
def doubled(nums):
    return [x * 2 for x in nums]

# O(n) по памяти — стек рекурсии!
def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

Последний пример коварен: рекурсия расходует память на стек вызовов, даже если не создаёт структур данных. Глубина рекурсии — это и есть память.

Для рекурсии по дереву память равна высоте: O(log n) для сбалансированного, O(n) для вырожденного.

Логарифм: откуда он берётся

Правило простое: если на каждом шаге задача уменьшается в константу раз, получается логарифм.

while n > 0:
    n //= 2       # O(log n)

Отсюда логарифм в бинарном поиске, в высоте сбалансированного дерева, в быстром возведении в степень.

А O(n log n) обычно означает: n элементов, для каждого делаем логарифмическую операцию. Или сортировка. Или «разделяй и властвуй» с линейным слиянием.

Как отвечать на собеседовании

Называйте обе сложности — время и память. Даже если спросили только про время.

Обосновывайте, а не констатируйте. Не «O(n)», а «один проход по массиву, внутри только операции со словарём за O(1), значит O(n)».

Упоминайте худший случай, если он отличается. «В среднем O(n), но при плохой хеш-функции может выродиться в O(n²)».

Проговаривайте компромисс. «Мы разменяли O(n) памяти на ускорение с квадрата до линии».

Проверяйте себя по ограничениям. Если в условии n = 10⁵, решение за O(n²) не пройдёт. Оценка сложности до написания кода экономит время.

Полезная табличка соответствия ограничений и допустимой сложности:

Частые вопросы-ловушки

«Какая сложность у сортировки в стандартной библиотеке?» O(n log n). В Python это Timsort, который на почти отсортированных данных даёт O(n).

«Что быстрее: O(n) или O(log n)?» O(log n) — но только на больших данных. При маленьком n константы решают, и линейный поиск по массиву из десяти элементов быстрее бинарного из-за локальности памяти.

«Какая сложность у обхода дерева?» O(n) — каждый узел посещается один раз. Часто путают с высотой.

«Сложность добавления в словарь?» O(1) амортизированно, O(n) в худшем случае при полном расширении.

«O(2n) и O(n) — это одно и то же?» Да, константы отбрасываются. Но на практике разница в два раза может быть значимой, и стоит это упомянуть.

Что запомнить

• Считайте сложность каждой строки, а не решения целиком.
• Скрытые операции — главный источник ошибок: in для списка, срезы, конкатенация строк, shift.
• Всегда называйте и время, и память; рекурсия расходует память на стек.
• Амортизированная сложность — гарантия для последовательности операций, а не средний случай.
• Сверяйтесь с ограничениями из условия до написания кода.