Як можна визначити складність алгоритму?

JavaScript~4 хв читання

Складність алгоритму (algorithm complexity) показує, як час виконання або витрати пам'яті змінюються зі зростанням розміру вхідних даних n, і виражається через нотацію Big O як верхня межа в найгіршому випадку.

Теорія

TL;DR

Big O рахує, як зростає кількість операцій при збільшенні n, а не абсолютну швидкість на конкретній машині.
Знайди домінуючу операцію: найглибший цикл або найважчу рекурсію. Все інше - шум.
Вхідні дані подвоїлися, а час виріс вчетверо? Це O(n²). Якщо вдвічі - O(n).
Константи відкидаємо: 3n + 5 стає O(n), бо при великому n цикл переважає.
Два окремі цикли по одному масиву дають O(n), а не O(2n).

Швидкий приклад

javascript

// O(1) - константна: не залежить від розміру масиву
function getFirst(arr) {
  return arr[0]; // завжди 1 операція, хай масив має 3 або 3 мільйони елементів
}

// O(n) - лінійна: один прохід по масиву
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) { // n кроків
    total += arr[i];
  }
  return total;
}

// O(n²) - квадратична: цикл всередині циклу
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {       // n
    for (let j = i + 1; j < arr.length; j++) { // до n
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Правило просте: рахуй рівень вкладеності циклів. Один цикл = O(n). Цикл всередині циклу = O(n²). Кожен рівень множить результат.

Ключова ідея: операції, а не рядки коду

Часта помилка - вважати кожен рядок коду однією операцією. Це працює лише для фіксованого доступу на зразок arr[0]. Щойно код залежить від n, рахунок змінюється. arr[i] всередині циклу виконується n разів, а не один. Відстежуй те, що масштабується з розміром вхідних даних.

Як аналізувати код: покроково

Читай код зсередини назовні:

Знайди найглибшу операцію: присвоєння, порівняння або доступ до елемента.
Порахуй, скільки разів вона виконується відносно n.
Один навколишній цикл = O(n). Два вкладені = O(n²).
Для рекурсії рахуй глибину дерева викликів. Функція, яка викликає себе двічі на кожному рівні, дає O(2^n) без мемоізації (memoization).
Залишай лише домінуючий член. O(n² + n) спрощується до O(n²).

Коли що використовувати

Фіксовані дані (до 100 елементів): O(n²) нормально, різниця непомітна.
Дані користувача (від 1K до 1M): цілься в O(n log n) або краще. O(n²) буде помітно гальмувати.
Реальний час (ігри, UI-взаємодія): тримайся O(1) або O(log n).
Сортування: вбудований array.sort() дає O(n log n).

Класи складності: коротко

Складність	n=10	n=100	Приклад
O(1)	1	1	`obj.key`, `arr[0]`
O(log n)	3-4	7	Бінарний пошук
O(n)	10	100	`array.filter()`
O(n log n)	~33	~664	`array.sort()`
O(n²)	100	10 000	Вкладені цикли, bubble sort
O(2^n)	1 024	~10^30	Наївна рекурсія (Fibonacci)

O(n²) при n=100 - це 10 000 операцій. При n=1000 - вже мільйон. Саме ця різниця роняє продакшн.

Типові помилки

Помилка 1: Думати, що .filter().map() - це O(n²)

javascript

// O(2n) = O(n) - два окремі проходи, все ще лінійна
const result = arr.filter(x => x > 0).map(x => x * 2);

Два цикли по одному масиву складаються, а не множаться. O(n + n) = O(2n) = O(n).

Помилка 2: Вкладені вбудовані методи

javascript

// O(n²) прихована за чистим синтаксисом
arr.map(a => others.includes(a)); // .includes() - це O(n) всередині O(n) map

Виправлення через Set: const set = new Set(others); arr.map(a => set.has(a)); - тепер O(n). Більшість таких багів у продакшн-коді виглядає саме так: чистий синтаксис, прихована квадратична складність.

Помилка 3: Наївна рекурсія

javascript

// O(2^n) - заморожує браузер при n=50
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // два виклики на кожному рівні
}

// O(n) з мемоізацією (memoization)
const memo = new Map();
function fibMemo(n) {
  if (memo.has(n)) return memo.get(n);
  if (n <= 1) return n;
  const res = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, res);
  return res;
}
console.log(fibMemo(100)); // миттєво

fib(40) технічно завершується, але помітно гальмує. fib(50) заморожує вкладку. Дерево викликів гілкується двічі на кожному вузлі.

Помилка 4: Просторова складність як другорядне питання

javascript

function dup(arr) {
  return arr.concat(arr); // O(n) додаткової пам'яті, яку легко не помітити
}

Якщо масив має 1M елементів, ти щойно виділив пам'ять для 2M. Просторова складність рахує допоміжні алокації, а не тільки час виконання.

Де зустрічається на практиці

React: useMemo запобігає повторному O(n) сортуванню на кожному рендері - const sorted = useMemo(() => users.sort((a, b) => a.age - b.age), [users]).
Express: пошук користувача в масиві записів - O(n). Додай індекс у базі даних - стане O(log n).
Node.js: readFileSync - O(n), де n - розмір файлу. Для великих файлів використовуй streams.
Set проти масиву: arr.includes(item) - O(n). set.has(item) - O(1).

Питання на співбесіді

Q: Яка різниця між O(n) і Θ(n)?
A: O(n) - верхня межа: алгоритм виконується щонайбільше kn операцій. Θ(n) - точна межа: і верхня, і нижня пропорційні n. На практиці інтерв'юери мають на увазі Θ, коли кажуть O, але сеньори знають різницю.

Q: Яка часова складність цього циклу?

javascript

for (let i = 0; i < n; i++)
  for (let j = i; j < n; j++) sum += arr[i][j];

A: O(n²/2) = O(n²). Внутрішній цикл з кожним кроком коротшає, але це все одно трикутний обхід. Константи відкидаються.

Q: Яка просторова складність quicksort?
A: O(log n) у середньому через глибину стека рекурсії, O(n) у найгіршому випадку. Merge sort завжди O(n), бо виділяє тимчасовий масив.

Q: array.includes(item) - яке Big O?
A: O(n). Метод сканує масив з індексу 0 щоразу. Для O(1)-пошуку використовуй Map або Set.

Приклади

Пошук максимального значення

javascript

function findMax(numbers) {
  let max = numbers[0]; // O(1) - одне присвоєння

  for (let i = 1; i < numbers.length; i++) { // O(n) - один прохід
    if (numbers[i] > max) max = numbers[i];
  }

  return max; // загальна складність: O(n)
}

console.log(findMax([3, 7, 1, 9, 4])); // 9

Цикл виконується n - 1 разів. Константу відкидаємо - O(n). Складність функції визначається найважчою операцією, а тут це один прохід по масиву.

Фільтрація списку з пошуком за Set

javascript

const users = [{ id: 1, name: "Alice" }, { id: 2, name: "Bob" }, { id: 3, name: "Carol" }];
const blocked = [1, 5, 7];

// O(n * m) - для кожного користувача сканує весь blocked
const slow = users.filter(u => blocked.includes(u.id));

// O(n + m) - Set будується один раз, кожен пошук O(1)
const blockedSet = new Set(blocked);
const fast = users.filter(u => !blockedSet.has(u.id));

console.log(fast); // [{ id: 2, name: "Bob" }, { id: 3, name: "Carol" }]

При 3 користувачах різниця непомітна. При 10 000 користувачів і 1 000 заблокованих ID перший варіант робить 10 мільйонів порівнянь. Другий - 11 000.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Дочитали статтю?