Нотация «большое O»: сложность алгоритмов на практике

О проверке кода. Оценки сложности — это математика, а не замер: они верны по определению алгоритма. Конкретные времена в статье не измерялись на живой машине, поэтому бейджа «проверено» нет — в отличие от материалов по Node.js с фактическим выводом.

«Большое O» звучит как академическая тема, а на деле это единственный инструмент, который отвечает на практический вопрос: мой код переживёт рост данных или упадёт?

Что это на самом деле

Big O описывает, как растёт время работы при увеличении размера входа n. Не сколько миллисекунд — а во сколько раз станет дольше, если данных станет больше.

Разница принципиальная. Замер говорит «на тысяче элементов заняло 5 мс». Big O говорит «на миллионе займёт в миллион раз больше» — или «почти столько же», в зависимости от алгоритма. Первое — про сейчас, второе — про будущее.

Почему отбрасывают константы

Формально время можно записать как 2n + 5: два действия на элемент плюс пять на подготовку. Big O это упрощает до O(n), и вот почему.

При n = 10 пятёрка заметна. При n = 1 000 000 она исчезает: 2 000 000 + 5 — это практически 2 000 000. А двойка не меняет характер роста: удвоили вход — удвоилось время, была там двойка или нет.

Big O описывает поведение на больших n, где важен только тип роста, а не множители. Поэтому O(n), O(2n) и O(100n + 50) — один класс: линейный.

Классы сложности от лучшего к худшему

Ключевая интуиция в последнем столбце: O(1) и O(log n) практически не замечают роста данных, O(n) растёт терпимо, а O(n²) на большом входе становится стеной.

Главная практическая история: O(n²) → O(n)

Это самая частая оптимизация в реальном коде, и она стоит того, чтобы её понять на примере. Задача: есть ли в массиве повторяющийся элемент?

Наивно — вложенный цикл, O(n²):

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Для каждого элемента проходим весь остаток. На 1000 элементов — около полумиллиона сравнений. На 100 000 — пять миллиардов. Секунды превращаются в минуты.

Через хеш-таблицу — один проход, O(n):

function hasDuplicate(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;   // O(1) проверка
    seen.add(x);
  }
  return false;
}

Один проход, а проверка «видели ли раньше» — за O(1), потому что Set (и Map, и объект) ищут по ключу мгновенно. Итог — O(n).

Мы обменяли память на время. Set занимает место, зато на 100 000 элементов разница не в проценты, а в тысячи раз. Это фундаментальный размен, и он работает почти всегда, где есть вложенный перебор одного набора данных.

Тот же принцип виден и на уровне баз: индекс в MongoDB — это ровно замена O(n)-перебора коллекции на быстрый поиск по структуре. COLLSCAN из того замера — это и есть линейный проход, которого индекс позволяет избежать.

O(log n): сила деления пополам

Логарифмическая сложность кажется магией: на миллион элементов — около 20 шагов. Секрет в том, что каждый шаг выбрасывает половину оставшегося.

Бинарный поиск в отсортированном массиве:

function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;   // отбросили левую половину
    else hi = mid - 1;                          // отбросили правую
  }
  return -1;
}

Миллион элементов → полмиллиона → четверть → … → один. Двадцать делений, и всё. Отсюда правило: если можно на каждом шаге отбрасывать половину — вы в O(log n), и рост данных вам почти не страшен.

Плата — данные должны быть отсортированы. А сортировка это O(n log n), так что бинарный поиск окупается, когда по одному отсортированному массиву ищут много раз.

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

Важные оговорки, без которых нотацию применяют неверно:

• Константы иногда решают. O(n) с тяжёлой операцией на каждый элемент может на реальных данных проиграть O(n²) с лёгкой — на маленьких n. Big O про большие данные, не про все.
• Память тоже имеет сложность. O(n) по времени может стоить O(n) по памяти — как Set выше. На ограниченной памяти это ограничение.
• Худший случай ≠ типичный. Быстрая сортировка в среднем O(n log n), но в худшем — O(n²). Средний случай тоже считают.

Практический вывод: Big O — это сигнал тревоги, а не финальная метрика. Увидели вложенный цикл по одному массиву — насторожитесь и подумайте про хеш-таблицу. Дальше решает замер на реальных данных.

Что было на этой странице в 2016 году

Первая версия вышла 26 января 2016 года и объясняла нотацию академически: определения, классы, поведение в худшем случае. Всё корректно — и всё осталось верным, потому что математика не устаревает.

Чего в ней не хватало — практического мостика. Big O подавался как теория для собеседований, оторванная от кода. А ведь главная его польза — конкретная: увидеть вложенный цикл и заменить его проходом с Set. Именно эту связь — «O(n²) в реальном коде почти всегда сводится к O(n)» — мы и вынесли в центр.

Ещё одна деталь: в 2016-м структуры Set и Map были новинкой из ES6, и примеры оптимизации через них ещё не стали привычными. Сегодня это первое, что делают с квадратичным алгоритмом.

Смежные темы: теория сложности алгоритмов — подробнее про классы; массивы в JavaScript — где сложность методов важна; индексы в MongoDB — тот же принцип в базе. Полный список — в уроках JavaScript.