Big O нотация

Big O — математическая нотация, описывающая верхнюю границу роста времени выполнения (или памяти) алгоритма при увеличении размера входных данных.

Зачем нужно

Big O позволяет сравнивать эффективность алгоритмов без привязки к конкретному оборудованию. Алгоритм O(n) обработает 1 миллион элементов за секунды, а O(n^2) — за часы. Выбор алгоритма может определить, работает ваше приложение или «зависает».

Где используется

  • Выбор алгоритма сортировки и поиска
  • Оценка производительности кода на code review
  • Собеседования (ожидается знание Big O)
  • Проектирование систем (масштабирование)

Предпосылки

Основные сложности

Таблица сложностей

Big O Название Пример 10 элементов 1000 элементов 1 000 000
O(1) Константная Доступ по индексу 1 1 1
O(log n) Логарифмическая Бинарный поиск 3 10 20
O(n) Линейная Перебор массива 10 1000 1 000 000
O(n log n) Линейно-логарифмическая Merge sort 33 10 000 20 000 000
O(n^2) Квадратичная Вложенные циклы 100 1 000 000 10^12
O(2^n) Экспоненциальная Полный перебор 1024 10^301 -
O(n!) Факториальная Перестановки 3 628 800 - -

Визуализация роста

Операции
│
│                                         O(n!)
│                                    O(2^n)
│                               O(n^2)
│                          ╱
│                     ╱
│               ╱               O(n log n)
│          ╱              ╱─────
│     ╱           ╱──────
│╱          ╱─────               O(n)
│      ╱───                 ─────────────
│  ╱──                ──────
│──              ─────              O(log n)
│           ─────         ────────────────
│     ─────    ──────────
│─────────────────────────          O(1)
└──────────────────────────────── n (размер входа)

O(1) — Константная сложность

Время не зависит от размера входа.

// Доступ к элементу массива по индексу
function getFirst(array) {
  return array[0]; // O(1) — всегда одна операция
}

// Доступ к свойству объекта
function getName(user) {
  return user.name; // O(1)
}

// Добавление в конец массива
function addItem(array, item) {
  array.push(item); // O(1) амортизированно
}

// Проверка чётности
function isEven(n) {
  return n % 2 === 0; // O(1)
}

O(log n) — Логарифмическая сложность

С каждым шагом отбрасывается половина данных.

// Бинарный поиск — каждый шаг уменьшает область поиска вдвое
function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;

  while (left <= right) {         // log₂(n) итераций
    const mid = Math.floor((left + right) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

// Для 1 000 000 элементов: всего ~20 шагов!
// log₂(1 000 000) ≈ 20

O(n) — Линейная сложность

Время растёт пропорционально размеру входа.

// Поиск элемента перебором
function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) { // n итераций
    if (array[i] === target) return i;
  }
  return -1;
}

// Сумма элементов
function sum(array) {
  let total = 0;
  for (const num of array) { // n итераций
    total += num;
  }
  return total;
}

// Array.prototype.map, filter, find, forEach — все O(n)
const doubled = array.map(x => x * 2);         // O(n)
const evens = array.filter(x => x % 2 === 0);  // O(n)

O(n log n) — Линейно-логарифмическая

Типичная сложность эффективных сортировок.

// Встроенная сортировка JavaScript — TimSort, O(n log n)
const sorted = [...array].sort((a, b) => a - b);

// Merge sort, Quick sort (средний случай) — O(n log n)
// Подробности: [[Merge sort]], [[Quick sort]]

O(n^2) — Квадратичная сложность

Вложенные циклы по одним и тем же данным.

// Bubble sort — O(n²)
function bubbleSort(array) {
  const arr = [...array];
  for (let i = 0; i < arr.length; i++) {           // n
    for (let j = 0; j < arr.length - i - 1; j++) { // n
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// Поиск дубликатов наивным способом — O(n²)
function hasDuplicatesSlow(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] === array[j]) return true;
    }
  }
  return false;
}

// Оптимизация до O(n) через Set
function hasDuplicatesFast(array) {
  const seen = new Set();
  for (const item of array) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

O(2^n) — Экспоненциальная сложность

// Рекурсивный Fibonacci без мемоизации — O(2^n)
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}
// fib(40) — миллиарды вызовов!

// Оптимизация через мемоизацию — O(n)
function fibFast(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibFast(n - 1, memo) + fibFast(n - 2, memo);
  return memo[n];
}

Space Complexity (сложность по памяти)

Big O описывает и дополнительную память, используемую алгоритмом.

// O(1) по памяти — используем только переменные
function sum(array) {
  let total = 0; // O(1) доп. памяти
  for (const num of array) {
    total += num;
  }
  return total;
}

// O(n) по памяти — создаём новый массив
function double(array) {
  return array.map(x => x * 2); // новый массив размера n
}

// O(n) по памяти — Set для хранения уникальных элементов
function unique(array) {
  return [...new Set(array)]; // Set до n элементов
}

Best / Worst / Average Case

Случай Описание Пример (линейный поиск)
Best case Лучший сценарий O(1) — элемент первый
Average case Средний сценарий O(n/2) = O(n)
Worst case Худший сценарий O(n) — элемент последний или нет

Big O обычно описывает worst case, если не указано иначе.

Правила упрощения Big O

1. Отбрасываем константы:     O(2n) → O(n)
2. Отбрасываем меньшие слагаемые: O(n² + n) → O(n²)
3. Разные входы — разные переменные: O(n + m), не O(2n)

// O(n), а не O(3n)
function example(array) {
  array.forEach(x => console.log(x));  // O(n)
  array.forEach(x => console.log(x));  // O(n)
  array.forEach(x => console.log(x));  // O(n)
  // Итого: O(3n) → O(n)
}

// O(n + m), а не O(n)
function merge(arr1, arr2) {
  arr1.forEach(x => console.log(x)); // O(n)
  arr2.forEach(x => console.log(x)); // O(m)
  // Итого: O(n + m) — два РАЗНЫХ входа
}

Сводная таблица операций

Операция Array Object Map Set
Доступ по индексу/ключу O(1) O(1) O(1) —
Поиск значения O(n) O(n) O(n) O(1)
Вставка в конец O(1)* O(1) O(1) O(1)
Вставка в начало O(n) O(1) O(1) O(1)
Удаление O(n) O(1) O(1) O(1)
Сортировка O(n log n) — — —

* амортизированно

Частые ошибки

  1. Игнорировать Big O в реальном коде. O(n^2) на 100 элементах — ок, на 100 000 — катастрофа
  2. Забывать о пространственной сложности. Создание копии массива = O(n) дополнительной памяти
  3. Думать, что O(n) всегда быстрее O(n log n). Константы имеют значение на малых n
  4. Путать амортизированную и гарантированную сложность. array.push — O(1) амортизированно, но иногда O(n) при расширении

Практика

  1. Определите Big O для каждой функции:
    function a(n) { return n * n; }                    // ?
function b(arr) { return arr.slice.sort(); }      // ?
function c(arr) { for (let i of arr) for (let j of arr) console.log(i,j); } // ?
  2. Оптимизируйте hasDuplicatesSlow (O(n^2)) до O(n) используя Set
  3. Замерьте реальное время: сравните bubbleSort и Array.sort() на массиве из 10 000 элементов

Связанные темы

Ресурсы