Временная сложность

Временная сложность (time complexity) — характеристика алгоритма, описывающая, как растёт число операций в зависимости от размера входных данных n, выражается через нотацию Big O.

Зачем нужно

Временная сложность позволяет предсказать поведение алгоритма при росте данных без его запуска. Алгоритм O(n^2), работающий 1 мс на 1000 элементах, займёт 1000 секунд на 1 000 000 элементах. Знание временной сложности помогает выбирать правильные алгоритмы и структуры данных ещё на этапе проектирования.

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

Code review: оценка производительности написанного кода
Выбор алгоритма при проектировании системы
Собеседования: обязательный вопрос о сложности решения
Оптимизация узких мест (profiling + алгоритмический анализ)

Основной контент

Нотации сложности

Big O (O) — верхняя граница (worst case): алгоритм работает не хуже, чем O(f(n))
Big Ω (Omega) — нижняя граница (best case)
Big Θ (Theta) — точная граница (tight bound): и сверху, и снизу

В практике используют Big O как консервативную оценку.

Правила подсчёта

// 1. Константы отбрасываются: O(3n) → O(n)
function printThrice(arr) {
  arr.forEach(x => console.log(x)); // O(n)
  arr.forEach(x => console.log(x)); // O(n)
  arr.forEach(x => console.log(x)); // O(n)
  // Итого: O(n)
}

// 2. Доминирующий член: O(n² + n) → O(n²)
function example(arr) {
  for (let i = 0; i < arr.length; i++)       // O(n)
    for (let j = 0; j < arr.length; j++) {}  // O(n) → всего O(n²)
  arr.forEach(x => {});                       // O(n)
  // Итого: O(n² + n) → O(n²)
}

// 3. Разные входы — разные переменные
function twoLoops(a, b) {
  a.forEach(x => {});  // O(n)
  b.forEach(x => {});  // O(m)
  // Итого: O(n + m), НЕ O(2n)
}

// 4. Вложенные циклы перемножаются
function nested(arr) {
  for (let i = 0; i < arr.length; i++)      // O(n)
    for (let j = 0; j < arr.length; j++) {} // O(n)
  // Итого: O(n * n) = O(n²)
}

Сложность встроенных операций JavaScript

arr[i]                   // O(1) — доступ по индексу
arr.push(x)              // O(1) амортизированно
arr.pop()                // O(1)
arr.unshift(x)           // O(n) — сдвиг всех элементов
arr.shift()              // O(n)
arr.splice(i, 1)         // O(n)
arr.indexOf(x)           // O(n)
arr.sort()               // O(n log n)
arr.includes(x)          // O(n)

obj[key]                 // O(1)
map.get(key)             // O(1)
set.has(val)             // O(1)

Как анализировать рекурсию

Для рекурсии используют Мастер-теорему: T(n) = a·T(n/b) + f(n).

// Merge sort: T(n) = 2·T(n/2) + O(n) → O(n log n)
// Fibonacci без мемо: T(n) = T(n-1) + T(n-2) → O(2^n)
// Бинарный поиск: T(n) = T(n/2) + O(1) → O(log n)

Сводная таблица классов сложности

Сложность	Пример	Предел практичности
O(1)	Доступ по ключу	Любой n
O(log n)	Бинарный поиск	Любой n
O(n)	Перебор массива	10^8
O(n log n)	Merge Sort	10^7
O(n^2)	Вложенные циклы	10^4
O(2^n)	Перебор подмножеств	n ≤ 25
O(n!)	Перестановки	n ≤ 12

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

Забывать, что arr.includes, arr.indexOf, arr.unshift — это O(n), а не O(1).
Считать рекурсию дешевле итерации: рекурсия добавляет O(depth) по памяти.
Смешивать временну́ю и пространственную сложность.
Оптимизировать O(1) операции вместо O(n^2) циклов — неправильная расстановка приоритетов.