Что на самом деле значит O(n log n), как по ограничениям угадать нужный алгоритм, сколько стоят встроенные операции Python — и пять приёмов, которые решают добрую половину задач на собеседованиях.
Первая часть серии «Алгоритмы и структуры данных». Листайте стрелками ← →, свайпом или кнопками внизу. В схемах нажимайте кнопки и двигайте ползунки. Следующая тема — массивы и хеширование.
O(f(n)) — верхняя оценка роста с точностью до константы при больших n. Она отвечает на вопрос «что будет, если данных станет в 10 раз больше», но не «что быстрее сейчас».
100·n и n — оба O(n).sort в Go — отрезки до 12 элементов.Грубая, но рабочая оценка: простой цикл на C, Go или Java делает около 10⁸ шагов в секунду. Python — в 30–100 раз меньше, если не уходит в C (numpy, встроенные функции).
Двигайте n. Шкала полос логарифмическая: каждое деление — в 1000 раз больше. Зелёная отметка — укладывается в секунду при 10⁸ шагов/с.
В условии задачи всегда есть n ≤ …. Это подсказка: лимит времени около секунды, значит, допустимо порядка 10⁸ шагов. Отсюда — какую сложность от вас ждут.
На собеседовании ограничения часто не называют — спросите сами: «сколько элементов? влезает ли в память? сколько запросов?». Это и есть первый шаг к выбору алгоритма.
n!перебор перестановок2ⁿ · nперебор подмножеств, битовые маскиn³тройной цикл, ДП по отрезкам, Флойдn²двойной цикл, ДП на двух строкахn log nсортировка, куча, бинпоиск, деревоnодин проход: окно, указатели, хешlog n, 1бинпоиск, формула, математикаВ условии: «дано n ≤ 18 заданий, у каждого время и награда…». Какую сложность, скорее всего, ждут?
Динамический массив (list, []T, ArrayList, JS Array) при нехватке места выделяет новый и копирует всё. Отдельный append бывает O(n), но в среднем по любой последовательности — O(1).
n · 1/(k−1) — константа на элемент.Память тоже сложность. Рекурсия тратит O(глубины) памяти на стек вызовов: обход сбалансированного дерева — O(log n), обход «дерева-списка» — O(n). А стек маленький и с жёстким пределом.
sys.getrecursionlimit() = 1000 кадров — RecursionError.-Xss), Go растит стек горутины до 1 ГБ.Самые дорогие ошибки — одна строчка, которая выглядит как O(1). В Python list — массив указателей, set и dict — хеш-таблицы, str неизменяемая.
То же в других языках: Java ArrayList.add(0, x) и remove(Object) — O(n), LinkedList.get(i) — O(n); JS arr.includes, indexOf, unshift — O(n); в Go вставка в начало слайса — copy всего хвоста.
lst.append(x)O(1)** амортизированноlst.insert(0, x), lst.pop(0)O(n)collections.dequex in lst, lst.index(x), lst.remove(x)O(n)set / dictx in s, d[k]O(1)в среднем; худший — O(n)lst[a:b], s[1:]O(b−a)копия! индексы, islice, memoryviews += t в цикледо O(n²)''.join(parts), io.StringIOsorted(lst), lst.sort()O(n log n)почти отсортированное — почти O(n)heapq.heappush, bisect.bisectO(log n)но bisect.insort — O(n)В data 10⁵ элементов. Какой фрагмент работает за квадратичное время?
pop(0) сдвигает все оставшиеся элементы: 10⁵ вызовов × в среднем 5 · 10⁴ сдвигов = 5 · 10⁹ перемещений указателей. Это секунды вместо миллисекунд. Для очереди есть collections.deque с popleft() за O(1). Остальные три — O(n).Задач тысячи, приёмов — пара десятков. Учитесь узнавать приём по признакам в условии. Пять самых частых разберём по шагам, остальные — в следующих частях серии.
Найти в отсортированном массиве пару с суммой target. Перебор пар — O(n²). Указатели с двух концов — O(n): если сумма мала, левый элемент не подойдёт ни к одному из оставшихся, его можно выбросить.
def pair_sum(a, target):
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target: return l, r
if s < target: l += 1
else: r -= 1
return None
В жизни: шаг слияния в merge sort, Merge Join в PostgreSQL, слияние отсортированных сегментов в LSM-деревьях (RocksDB, Cassandra), git diff по отсортированным спискам.
Самая длинная подстрока без повторов. Правая граница идёт вперёд, левая — только догоняет. Каждый индекс входит в окно и выходит из него по разу: O(n) вместо O(n²) или O(n³).
def longest_unique(s):
last, l, best = {}, 0, 0
for r, ch in enumerate(s):
if last.get(ch, -1) >= l:
l = last[ch] + 1 # за повтор
last[ch] = r
best = max(best, r - l + 1)
return best
В жизни: rate limiter со скользящим окном, скользящее среднее в метриках, окно TCP (сети), окна в Kafka Streams и Flink.
Один проход O(n) — и потом сумма любого отрезка за O(1): P[r+1] − P[l]. Окупается, когда запросов много: 10⁵ запросов по 10⁵ элементам — 10⁵ вычитаний вместо 10¹⁰ сложений.
from itertools import accumulate
P = [0, *accumulate(a)] # P[i] = sum(a[:i])
def range_sum(l, r): # включительно
return P[r + 1] - P[l]
«Сколько подмассивов с суммой k» — тоже префиксы: идём слева направо и считаем в dict, сколько раз встречалась сумма P − k. В жизни: счётчики Prometheus накопительные, и rate() — это разность префиксных сумм; суммы по прямоугольнику в обработке изображений.
Посылки едут по порядку, за D дней. Какая минимальная грузоподъёмность? Искать ответ напрямую трудно, а проверить «хватит ли C» — легко жадным проходом O(n). И если хватает C, хватит и C + 1.
lo, hi = max(w), sum(w)
while lo < hi:
mid = (lo + hi) // 2
if days_needed(w, mid) <= D: hi = mid
else: lo = mid + 1
return lo # O(n · log(sum))
Признак: «минимальное / максимальное X, при котором…» и монотонная проверка. В жизни: git bisect, подбор максимального размера батча, который не падает по памяти, поиск порога в нагрузочном тесте.
Для каждого элемента найти ближайший справа, который больше. В стеке ждут элементы, для которых ответ ещё не найден, — их значения убывают. Новый элемент выталкивает всех, кто меньше него, и становится их ответом.
ans, st = [-1] * len(a), []
for i, x in enumerate(a):
while st and a[st[-1]] < x:
ans[st.pop()] = x
st.append(i)
Вложенный while не делает алгоритм квадратичным: каждый индекс кладут и вынимают ровно по разу — всего не больше 2n операций. Это тоже амортизированный анализ. Задачи: «сколько дней до потепления», наибольший прямоугольник в гистограмме, индикатор stock span.
Найти длину самого длинного подотрезка с суммой не больше K. Все числа положительные, n ≤ 10⁵. Какой приём?
Оценивают не только ответ, но и ход мысли. Интервьюер помогает тому, кто думает вслух, и не может помочь тому, кто молча пишет код.
Пройдите по шагам на классической задаче Two Sum. Не пропускайте перебор: он показывает, что вы поняли задачу, и даёт точку отсчёта для оптимизации.
select_related/prefetch_related, joinedload, JOIN FETCH, WHERE id IN (…).next(u for u in users …). Постройте dict по id один раз.list.remove / x in list в цикле: невидимый второй цикл. На тестовых 100 строках незаметно, на 10⁵ в проде — минуты.Двигайте размер данных и задержку до базы.
py-spy top --pid, py-spy record -o flame.svg, cProfile; Go — pprof; Java — async-profiler, JFR; Node — --cpu-prof, Chrome DevTools. Ищите широкую полку с list.remove, __contains__, index, includes.echo=True в SQLAlchemy, calls в pg_stat_statements.Справа — настоящий замер в вашем браузере: удаление дублей через Array.includes и через Set.
pop(0), in по списку, срезы и склейка строк — источник случайного O(n²).Сначала правильно, потом быстро — но квадрат замечайте сразу.