Что такое Big O простыми словами — и почему код летал на 100 записях и умер на 100 000

Смотри, знакомая история. Ты собрал сравнение двух списков, проверил на 100 строках — мгновенно. Залил реальный файл на 100 000 строк — и вкладка зависла на минуту.

Код не сломался. Он делает ровно то же, что делал. Просто данных стало в 1000 раз больше, а работы — в миллион. Вот эту разницу и описывает Big O.

Что такое Big O

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

Это важно. Миллисекунды зависят от твоего ноутбука. А рост — от самого кода. Если код растёт как квадрат, никакой мощный процессор не спасёт: удвоил данные — работы стало вчетверо.

Записывают это так: O(n), O(n²), O(log n). Буква n — размер данных. Сколько строк, пользователей, товаров.

Четыре скорости роста, которые ты встретишь

Почти всё, что ты будешь писать, укладывается в четыре класса.

• O(1) — константа. Работа не зависит от размера. Взять элемент массива по номеру items[5] — одно действие, хоть там 10 элементов, хоть миллион.
• O(log n) — логарифм. Каждый шаг отбрасывает половину. Миллион элементов — около 20 шагов. Так ищут слово в словаре: открыл середину, понял, левее или правее.
• O(n) — линейно. Один проход по всем данным. Данных вдвое больше — работы вдвое больше. Это обычный цикл или .filter().
• O(n²) — квадрат. Цикл внутри цикла. На 100 элементах — 10 000 действий. На 100 000 — уже 10 миллиардов.

Вот где была засада из начала. Между n и n² на маленьких данных разницы не видно. На больших это разница между секундой и часом.

Где прячется квадрат

Самое коварное: O(n²) редко выглядит как два вложенных for. Чаще он спрятан внутри обычного метода.

// найти пользователей, которые есть в обоих списках
const common = listA.filter(user => listB.includes(user))

Выглядит как одна строчка и один проход. Но includes — это тоже цикл. Он перебирает listB целиком, пока не найдёт совпадение. Получается проход внутри прохода. Два списка по 100 000 — до 10 миллиардов сравнений.

Чинится заменой одной структуры:

const setB = new Set(listB)
const common = listA.filter(user => setB.has(user))

Set ищет элемент не перебором, а по хешу — в среднем за одно действие. Код стал O(n). Те же 100 000 строк — доли секунды.

Ещё несколько мест, где квадрат любит прятаться:

• indexOf и find внутри цикла — тот же перебор, что и includes.
• array.shift() в цикле. Он удаляет первый элемент и сдвигает все остальные. Очередь на shift() по большому массиву — снова квадрат.
• Склейка строк или массивов в цикле через spread — result = [...result, item] копирует всё накопленное на каждом шаге.

Что Big O не говорит

Big O — грубая оценка, и это нормально. Она отбрасывает детали.

• Константы не считаются. Два прохода по массиву — всё ещё O(n). Для роста это неважно.
• На маленьких данных это не главное. Если в списке никогда не будет больше 50 элементов, includes в цикле — нормальный код. Не надо превращать каждую строку в оптимизацию.
• Обычно говорят о худшем случае. includes может найти элемент сразу. Но рассчитывать стоит на то, что придётся пройти весь список.

Практичное правило: думай о Big O там, где данные могут вырасти. Импорт файлов, поиск, ленты, всё, что приходит от пользователей.

Как это использовать с ИИ

ИИ пишет filter + includes постоянно — так короче. Попроси его проверить:

Хороший ответ называет конкретную строку и сложность «было/стало». Если ИИ просто переписал всё «покрасивее» — попроси доказать, где был квадрат. А дальше проверь замером, что стало быстрее.

Нужно ли учить Big O, если код пишет ИИ?

Да, хотя бы четыре класса. ИИ часто выбирает самый короткий код, а не самый быстрый. Чтобы заметить квадрат на ревью, тебе хватит вопроса «тут цикл внутри цикла?».

Что значит O(n log n)?

Чуть медленнее линейного, но намного быстрее квадрата. Такая сложность у сортировки: array.sort() в современных браузерах работает за O(n log n). Миллион элементов сортируется за доли секунды.

Big O бывает про память?

Да. Так же оценивают, сколько памяти нужно при росте данных. new Set(listB) из примера выше — это O(n) дополнительной памяти. Обычно это честный обмен: немного памяти за огромный выигрыш в скорости.