Big O Notation: оценка сложности алгоритмов

Зачем нужна оценка сложности

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

Говорят: «этот алгоритм работает за O(n)» — значит, если данных станет в 10 раз больше, он будет работать примерно в 10 раз дольше.

Основные обозначения

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

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

function getFirst(arr) {
  return arr[0]
}

Массив из 10 элементов или из 10 миллионов — операция одна и та же. Взять элемент по индексу, присвоить переменную, вернуть значение — всё это O(1).

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

На каждом шаге объём данных уменьшается примерно вдвое. Классический пример — бинарный поиск:

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1

  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) return mid
    if (arr[mid] < target) left = mid + 1
    else right = mid - 1
  }

  return -1
}

Для массива из 1 000 000 элементов понадобится максимум ~20 проверок (log₂ 1000000 ≈ 20).

O(n) — линейная

Проходим по всем элементам один раз:

function sum(arr) {
  let total = 0
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]
  }
  return total
}

100 элементов — 100 итераций. 1000 — 1000. Рост прямо пропорциональный.

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

Встречается в эффективных алгоритмах сортировки (merge sort, quick sort в среднем). Обычно это лучший результат для сортировки сравнениями.

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
}

10 элементов — до 45 сравнений. 100 — до 4950. 1000 — до 499500. Растёт очень быстро.

O(2ⁿ) — экспоненциальная

Каждый вызов порождает два новых. Классика — наивный поиск чисел Фибоначчи:

function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

Для fib(40) этот код сделает более миллиарда вызовов. На практике такие алгоритмы оптимизируют через мемоизацию или итеративный подход.

Пространственная сложность

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

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

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

Как определять сложность

Отбрасываем константы

O(2n) → O(n). O(500) → O(1). O(n/2) → O(n).

Big O описывает тенденцию при росте данных, а не точное число операций. Константы не влияют на тенденцию.

Отбрасываем младшие члены

O(n² + n) → O(n²). O(n + log n) → O(n).

При больших n член n² доминирует, и n становится незаметным.

Сложность по худшему случаю

Big O обычно описывает худший сценарий. Но иногда различают:

• O(n) — худший случай (worst case)
• Ω(n) — лучший случай (best case)
• Θ(n) — средний случай (average case)

На собеседованиях почти всегда имеют в виду worst case.

Шпаргалка по операциям

Типичные ловушки

// Кажется O(n), но .includes() внутри цикла даёт O(n²)
function findCommon(arr1, arr2) {
  return arr1.filter(item => arr2.includes(item))
}

// Лучше через Set — O(n + m)
function findCommonBetter(arr1, arr2) {
  const set2 = new Set(arr2)
  return arr1.filter(item => set2.has(item))
}

// .splice(i, 1) внутри цикла — O(n²), потому что сдвигает элементы
for (let i = arr.length - 1; i >= 0; i--) {
  if (arr[i] < 0) arr.splice(i, 1)
}

// Часто лучше создать новый массив — O(n)
const filtered = arr.filter(item => item >= 0)

Как сложность выглядит на графике

При n = 100:

Разница между O(n) и O(n²) на 100 элементах — 100 раз. На 10 000 — в 10 000 раз.

Итог

• Big O описывает, как растёт время/память при росте данных
• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• Отбрасывайте константы и младшие члены
• Вложенные циклы по одним данным — почти всегда O(n²)
• Используйте Map/Set для O(1) поиска вместо O(n) через includes/indexOf