Big O на практике: как один цикл убивает производительность

Почему 60 строк работают мгновенно, а 14 000 — вешают браузер?

Представьте: локально страница грузится за 80 мс. В продакшене, на реальной базе данных, — 9 секунд, и вкладка зависает. Код не менялся. Изменились данные: 60 тестовых строк локально против 14 000 в продакшене. Виновник — десять строк цикла, идеально читаемых, ищущих дубликаты в списке. Никакой ошибки. Просто неправильная форма. И понимание этой формы — и есть Big O. Никакой математики, обещаю: достаточно, чтобы читать свой код и знать, какая часть взорвётся при росте данных.

Big O измеряет форму, а не скорость

Первое, что нужно сломать в голове: O(...) не говорит «это занимает 3 миллисекунды». Оно говорит, как время реагирует на удвоение данных. Это форма кривой, а не секундомер. Три семейства покрывают подавляющее большинство задач:

• O(1) — константа. Размер данных ничего не меняет. Чтение array[5000] так же быстро, как array[5].
• O(n) — линейное. Вдвое больше данных — вдвое больше времени. Цикл, проходящий по всем элементам.
• O(n²) — квадратичное. Вдвое больше данных — в четыре раза больше времени. Убийственный класс, именно такой был у моего цикла.

Ловушка: на 60 строках все три кривые сливаются

На малом объёме O(1), O(n) и O(n²) выглядят одинаково. Именно на продакшен-масштабе O(n²) отрывается. Поэтому мой баг был невидим локально: при n=60 O(n) делает 60 операций, а O(n²) — 3 600. Разница в микросекундах, никто её не замечает. При n=14 000 O(n) делает 14 000 операций, O(n²) — 196 миллионов. Вот это уже чувствуется.

Цикл, который всё ломает

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

# ✗ O(n²): цикл ВНУТРИ цикла
dupes = []
for a in lst:
    for b in lst:  # ← повторный просмотр, который дорого стоит
        if a['id'] == b['id'] and a is not b:
            dupes.append(a)

Та же ловушка прячется в более хитрой форме — той, что годами ловила меня: includes() внутри цикла. Выглядит как один цикл, но includes скрывает второй.

# ✗ замаскированное O(n²): каждый includes() просматривает весь массив заново
seen = []
for item in lst:
    if item['id'] in seen:  # in для списка — O(n), а в цикле — O(n²)
        continue
    seen.append(item['id'])

Исправление — одно слово: Set. Set (или dict, или frozenset) — это хеш-таблица: проверка вхождения через in работает за O(1), независимо от размера. Двойной цикл схлопывается в один.

# ✓ O(n): Set отвечает за O(1), одного прохода достаточно
seen = set()
dupes = []
for item in lst:
    if item['id'] in seen:  # O(1)
        dupes.append(item)
    seen.add(item['id'])

Мои 9 секунд превратились в 40 миллисекунд. Никакой хитрой оптимизации, никакого кэша — просто правильная форма кривой.

Почему Set — магия: массив против связного списка

Чтобы понять, откуда берётся O(1), нужно заглянуть под капот структур данных. Всё упирается в один вопрос: где в памяти живут элементы?

Память — это длинный ряд пронумерованных ячеек. Массив хранит элементы в ячейках, расположенных подряд друг за другом. Зная начальный адрес, он мгновенно вычисляет, где находится 5000-й элемент: чтение за O(1). Обратная сторона: вставка в начало заставляет все остальные сдвинуться — O(n). Именно это делает list.insert(0, x) в Python, тогда как list.append(x) (добавление в конец) бесплатно.

Связный список делает наоборот: его элементы разбросаны где угодно, и каждый хранит адрес следующего, как поиск сокровищ. Вставка ничего не сдвигает (O(1)), но чтение 5000-го элемента заставляет идти по стрелкам одну за другой с самого начала (O(n)). Вы почти никогда не будете писать его вручную: в Python это collections.deque (двусторонняя очередь), в Java — LinkedList. В Python обычный список — это динамический массив, не связный список.

Хеш-таблица (Set, dict в Python, объект в JavaScript) играет в другой лиге: функция превращает ключ прямо в позицию в памяти. Никакого обхода, никаких сдвигов: чтение, запись, проверка вхождения — всё за O(1). Именно поэтому замена список in на множество in превращает квадратичную кривую в линейную.

Скрытое O(n) за невинной строкой

Настоящее мастерство — не заучивать эти классы, а замечать их в своём коде, часто спрятанными за безобидным синтаксисом:

• list.insert(0, x) или list.pop(0): O(n), всё сдвигается.
• x in список или list.index(x) внутри цикла: O(n²). Set или dict возвращают к O(n).
• SQL-запрос WHERE email = ? без индекса на колонке: база данных делает полное сканирование, O(n) над миллионами строк. Индекс — это её версия бинарного поиска, O(log n).
• Вложенные циклы при «соединении» двух списков: снова цикл в цикле. Проиндексируйте один из списков в dict или set заранее.

Вывод

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

И ирония в том, что ИИ здесь ничего не меняет, даже наоборот. Ассистент с радостью сгенерирует O(n²)-цикл, который проходит все тесты на 50 строках и умирает в продакшене. Распознавать форму кривой в сгенерированном коде — то, что нельзя делегировать.

Что делать прямо сейчас: Откройте свой проект, найдите место, где вы ищете элемент в списке внутри цикла. Замените список на set или dict. Замерьте производительность — и увидите разницу.