Розмір вхідних даних

JavaScriptJunior~3 хв читання

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	Затримка через мережу / диск

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

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

Premium

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