Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як можна визначити складність алгоритму?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

**Складність алгоритму (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` разів, а не один. Відстежуй те, що масштабується з розміром вхідних даних.

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

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

1. Знайди найглибшу операцію: присвоєння, порівняння або доступ до елемента.
2. Порахуй, скільки разів вона виконується відносно `n`.
3. Один навколишній цикл = O(n). Два вкладені = O(n²).
4. Для рекурсії рахуй глибину дерева викликів. Функція, яка викликає себе двічі на кожному рівні, дає O(2^n) без мемоізації (memoization).
5. Залишай лише домінуючий член. 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.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати1149 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.