Розмір вхідних даних і продуктивність

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

Чим більший обсяг вхідних даних, тим довше виконується код, якщо алгоритм не масштабується ефективно. Залежність між розміром входу і кількістю роботи описує асимптотична складність (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
Обсяг вводу-виводу	Затримка через мережу або диск

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

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

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

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

Premium

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