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

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

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

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

Контент

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

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

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

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

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

**Чим більший обсяг вхідних даних, тим довше виконується код, якщо алгоритм не масштабується ефективно.** Залежність між розміром входу і кількістю роботи описує асимптотична складність (Big O), і саме вона, а не абсолютна швидкість окремої операції, вирішує, чи витримає код зростання даних.

## Теорія

### TL;DR
- Розмір входу впливає на час на CPU, обсяг пам'яті, кількість операцій вводу-виводу, кількість ітерацій та глибину рекурсії.
- Big O показує, як швидко росте час виконання при збільшенні `n`, а не скільки мілісекунд займе конкретний виклик.
- На `n = 10` різниці між `O(n)` і `O(n²)` немає, на `n = 100 000` вона визначає, працює застосунок чи ні.
- Пошук у `Map` або `Set` майже `O(1)`, пошук у масиві `O(n)`, вкладені цикли `O(n²)`.
- Довгі синхронні цикли блокують event loop: інтерфейс завмирає, FPS падає.
- Основні ліки: кращі структури даних, мемоізація, розбиття роботи на чанки, віртуалізація списків, стримінг.

### Швидкий приклад
```javascript
// O(n): час зростає пропорційно кількості елементів
function sum(arr) {
  return arr.reduce((acc, num) => acc + num, 0);
}

sum([1, 2, 3]);              // приблизно 3 операції
sum(new Array(1000000));     // приблизно 1 000 000 операцій

// O(n^2): час зростає як квадрат кількості елементів
function allPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      // якась операція над парою
    }
  }
}
// n = 1 000    -> близько 1 000 000 операцій
// n = 10 000   -> вже 100 000 000 операцій
```

### Асимптотична складність: як росте час

| Складність | Назва | Що означає | Приклад |
| --- | --- | --- | --- |
| **O(1)** | константна | не залежить від розміру даних | доступ за індексом `arr[0]` |
| **O(log n)** | логарифмічна | росте дуже повільно | бінарний пошук |
| **O(n)** | лінійна | час росте пропорційно кількості елементів | цикл `for` по масиву |
| **O(n log n)** | квазілінійна | помірне зростання | `Array.prototype.sort()` |
| **O(n²)** | квадратична | вибухове зростання на великих даних | вкладені цикли |
| **O(2ⁿ)** | експоненційна | зростає катастрофічно | наївний рекурсивний Fibonacci |
| **O(n!)** | факторіальна | неможлива для великих `n` | генерація всіх перестановок |

Та сама таблиця, але з боку відчуттів користувача:

| Розмір вхідних даних | O(1) | O(log n) | O(n) | O(n²) | O(2ⁿ) |
| --- | --- | --- | --- | --- | --- |
| 10 | миттєво | миттєво | миттєво | миттєво | миттєво |
| 100 | миттєво | миттєво | миттєво | помітно | повільно |
| 1 000 | миттєво | миттєво | помітно | повільно | нереально |
| 100 000 | миттєво | миттєво | повільно | нереально | нереально |

Висновок: на малих даних «летить» будь-який код, а неефективність проявляється рівно тоді, коли обсяг виріс.

### Приклади на JavaScript
`O(1)`, доступ не залежить від розміру:

```javascript
const arr = [1, 2, 3, 4, 5];
console.log(arr[3]); // миттєво, хоч 5, хоч 5 мільйонів елементів
```

`O(n)`, лінійна залежність:

```javascript
function sum(arr) {
  return arr.reduce((acc, num) => acc + num, 0);
}
```

Чим більший масив, тим більше часу: кожен елемент обробляється рівно один раз.

`O(n²)`, квадратичне зростання:

```javascript
function allPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      // якась операція
    }
  }
}
```

Якщо `n = 1000`, операцій приблизно **1 000 000**. Якщо `n = 10 000`, то вже **100 000 000**.

`O(2ⁿ)`, експоненційне зростання:

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

fib(30); // працює
fib(45); // вже відчутно гальмує
```

Зростання вибухове: при `n` близько 100 порахувати це вже просто неможливо.

### Де це проявляється на практиці

| Тип задачі | Приклад | Як впливає розмір даних |
| --- | --- | --- |
| **Перебір масиву** | `map`, `filter`, `reduce` | лінійно |
| **Пошук у масиві** | `arr.includes()` | лінійно |
| **Пошук в об'єкті або Map** | `obj[key]`, `map.get()` | майже `O(1)` |
| **Сортування** | `arr.sort()` | `O(n log n)` |
| **Порівняння вкладених структур** | глибоке порівняння об'єктів | може бути `O(n²)` |
| **Рендеринг у React** | великі списки, таблиці | час росте разом з обсягом DOM |
| **Запити до бази даних** | без індексу це `O(n)` | чим більше рядків, тим повільніше |

Практичні наслідки зростання даних:

- **Зростає навантаження на CPU**: операції тривають довше.
- **Збільшується споживання пам'яті**, особливо при копіюванні або зберіганні великих структур.
- **Блокується event loop**: інтерфейс «підвисає», кліки не обробляються.
- **Падає FPS**: анімації стають рваними.
- **Збирач сміття працює частіше**, і це дає відчутні лаги.
- **Глибша рекурсія** підвищує ризик `RangeError: Maximum call stack size exceeded`.

### Що робити, коли даних стає багато

| Проблема | Рішення |
| --- | --- |
| Цикли виконуються надто довго | Розбити роботу на чанки (`setTimeout`, `requestIdleCallback`) |
| Складні фільтри та пошуки | Використати `Set`, `Map`, попередньо побудовані індекси |
| Часті повторні обчислення | Мемоізація |
| Забагато елементів у DOM | Віртуалізація списків (`react-window`, infinite scroll) |
| Постійне перестворення масивів | Обережно застосовувати мутації замість копій |
| Великі JSON | Потокове читання (`ReadableStream`) |
| Важкі обчислення в UI-потоці | Винести у Web Worker |

Підсумкова карта впливу:

| Що зростає | На що впливає |
| --- | --- |
| Кількість ітерацій | Час виконання |
| Глибина рекурсії | Ризик переповнення стека |
| Кількість об'єктів | Споживання пам'яті |
| Довжина списку або масиву | Кількість перемальовувань у React |
| Обсяг вводу-виводу | Затримка через мережу або диск |

### Типові помилки
1. **Оптимізувати константу замість складності.** Замінити `for` на `while` заради «швидкості» безглуздо, якщо алгоритм лишився `O(n²)`: правильна структура даних дає виграш у тисячі разів, мікрооптимізація у відсотки.
2. **Тестувати лише на маленьких даних.** На 20 записах працює будь-що; проблеми виявляються на реальних обсягах, тому навантажувальні перевірки треба робити на даних, наближених до продакшн.
3. **Шукати в масиві всередині циклу.** `arr.includes(x)` у циклі по іншому масиву перетворює задачу на `O(n * m)`; попередньо побудований `Set` робить її лінійною.
4. **Забувати про приховану складність вбудованих методів.** `arr.splice()`, `arr.shift()`, `arr.unshift()` зсувають елементи і коштують `O(n)`, а ланцюжок `filter().map().reduce()` проходить масив тричі.
5. **Вважати, що `O(1)` завжди швидше за `O(n)`.** Для дуже малих `n` простий лінійний прохід може бути швидшим за побудову хеш-структури: асимптотика описує поведінку при зростанні, а не абсолютний час.
6. **Блокувати головний потік синхронним циклом.** Поки цикл виконується, браузер не малює і не реагує на події, тож користувач бачить «зависання», навіть якщо загальний час прийнятний.
7. **Ігнорувати пам'ять.** Алгоритм може бути `O(n)` за часом, але `O(n)` за пам'яттю на кожному кроці, і зростання обсягу впирається не в CPU, а в збирач сміття.

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

Для рев’юера

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

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