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

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

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

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

Контент

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

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

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

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

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

## 1. Основна ідея

> Чим **більше вхідних даних**, тим **довше виконується код**, якщо алгоритм не масштабується ефективно.

Розмір вхідних даних напряму впливає на:

- час виконання (навантаження на CPU);
- використання пам'яті;
- кількість операцій вводу/виводу (I/O);
- кількість ітерацій і глибину рекурсії.

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

---

## 2. Проста візуалізація

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

---

## 3. Приклади на 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);
}

sum([1, 2, 3]);           // ~3 операції
sum(new Array(1000000));  // ~1 000 000 операцій
```

Чим більший масив, тим більше часу.

---

### 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); // вже гальмує!
```

Зростання вибухове. При 100 елементах порахувати просто неможливо.

---

## 4. Як зростання вхідних даних впливає на продуктивність

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

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

---

## 5. Продуктивність у різних сценаріях

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

---

## 6. Практичні наслідки

- **навантаження на CPU зростає** - операції тривають довше;
- **пам'ять збільшується** - особливо при копіюванні або зберіганні великих структур;
- **event loop блокується** - інтерфейс "підвисає";
- **FPS падає** - анімації стають нерівними;
- **GC (збирач сміття)** працює частіше -> лаги.

---

## 7. Як покращити продуктивність при зростанні даних

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

---

## Резюме

> Чим більший розмір вхідних даних,
> тим сильніше проявляється **асимптотична складність алгоритму** і навантаження на пам'ять/CPU.

| Розмір даних вгору | -> Впливає на |
|---|---|
| Кількість ітерацій | Час виконання |
| Глибина рекурсії | Ризик переповнення стека |
| Кількість об'єктів | Використання пам'яті |
| Довжина списку / масиву | Кількість перемальовувань (у React) |
| Обсяг I/O | Затримка через мережу / диск |

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

Для рев’юера

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

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