Классы сложности

Есть семь Big-O классов, которые охватывают почти все алгоритмы, которые ты когда-нибудь напишешь или увидишь. Вот они, упорядоченные от самого быстрого (наименьшая стоимость) к самому медленному (наибольшая стоимость):

O(1) — Постоянное время Алгоритм делает одинаковое число операций независимо от того, насколько большой вход. Один поиск, одна проверка, готово. Масштабируется как плоская линия. Для n = 1 000 000: всё ещё 1 операция.

Форма кода: Прямой доступ, без циклов.

function getFirst(array) {
  return array[0];  // O(1)
}

O(log n) — Логарифмическое время Алгоритм делит задачу пополам на каждом шаге (бинарный поиск, разделяй и властвуй). Log₂ от 1 000 000 — примерно 20, поэтому это очень быстро даже для огромных входов. Для n = 1 000 000: примерно 20 операций.

Форма кода: Раздели область поиска пополам на каждой итерации.

function binarySearch(numbers, target) {
  let left = 0, right = numbers.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (numbers[mid] === target) return mid;
    if (numbers[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;  // O(log n)
}

O(n) — Линейное время Алгоритм трогает каждый элемент один раз. Для n = 1 000 000: 1 000 000 операций. Это практично для почти любого размера входа.

Форма кода: Один цикл по входу.

function sumAll(numbers) {
  let sum = 0;
  for (let num of numbers) {
    sum += num;
  }
  return sum;  // O(n)
}

O(n log n) — Линеарифмическое время Алгоритм сортирует или делит с умом. Для n = 1 000 000: 1 000 000 × 20 ≈ 20 000 000 операций. Всё ещё практично; это цена большинства эффективных алгоритмов сортировки (merge sort, quicksort).

Форма кода: Часто один цикл, который делает O(log n) работы за итерацию, или алгоритм разделяй-и-властвуй.

// Merge sort делает O(n log n) работы всего
function mergeSort(numbers) {
  if (numbers.length <= 1) return numbers;
  const mid = Math.floor(numbers.length / 2);
  const left = mergeSort(numbers.slice(0, mid));
  const right = mergeSort(numbers.slice(mid));
  return merge(left, right);  // O(n log n)
}

O(n²) — Квадратичное время Вложенные циклы: для каждого элемента ты трогаешь все остальные элементы. Для n = 1 000 000: 1 триллион операций. Практично только для малых входов (до нескольких тысяч элементов).

Форма кода: Вложенные циклы.

function allPairs(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      console.log(numbers[i], numbers[j]);
    }
  }  // O(n²)
}

O(2ⁿ) — Экспоненциальное время На каждый дополнительный элемент операции удваиваются. Для n = 20: 1 миллион операций. Для n = 30: 1 миллиард. Для n = 40: 1 триллион. Практично только для очень малых входов (n ≤ ~30).

Форма кода: Рекурсивное исследование всех подмножеств или комбинаций.

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);  // O(2ⁿ) — создаёт экспоненциальное дерево
}

O(n!) — Факториальное время На каждый дополнительный элемент операции умножаются: 1, 2, 6, 24, 120, 720, … . Для n = 10: 3 600 000 операций. Для n = 12: 480 000 000 операций. Практично только для крошечных входов (n ≤ ~10).

Форма кода: Создай и проверь все перестановки.

function allPermutations(items) {
  if (items.length <= 1) return [items];
  const result = [];
  for (let i = 0; i < items.length; i++) {
    const rest = items.slice(0, i).concat(items.slice(i + 1));
    for (let perm of allPermutations(rest)) {
      result.push([items[i], ...perm]);
    }
  }
  return result;  // O(n!)
}

Эти семь классов составляют основной спектр. Некоторые алгоритмы падают между ними (O(n^1.5), O(n²log n)), но семь выше — это те, которые ты встретишь чаще всего.