Що означає O(n²) - квадратична складність?

АлгоритмиJunior~3 хв читання

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

O(n²) - це квадратична часова складність: час роботи алгоритму зростає пропорційно квадрату розміру входу n. Типове джерело - вкладені цикли по одному й тому самому набору даних, що дають приблизно n × n елементарних операцій.

Розгорнута відповідь

Визначення і суть

Запис O(n²) означає, що кількість елементарних операцій алгоритму для входу розміру n можна оцінити зверху виразом вигляду c·n² + a·n + b, де константи c, a, b не залежать від n. У нотації O-символіки враховується лише головний (найшвидше зростаючий) член - n², а константи і молодші члени відкидаються.

Інтуїтивно: якщо ви подвоїте n, час приблизно зросте у 4 рази; якщо збільшите n у 10 разів - приблизно у 100 разів.

Коли виникає O(n²)

Два вкладені цикли по одному й тому самому масиву/списку.
Перебір усіх пар елементів набору (кількість пар - n(n-1)/2).
Деякі сортування в найгіршому випадку (наприклад, бульбашкове сортування, просте виділення, вставками - найгірший випадок).
Операції над матрицями n×n, де потрібно відвідати кожен елемент (наприклад, порівняння кожного рядка з кожним рядком).

Приклади коду (JavaScript)

Підрахунок кількості пар - класичний O(n²):

javascript

function countPairs(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++; // елементарна операція
    }
  }
  return count; // ~ n(n-1)/2 => O(n^2)
}

Бульбашкове сортування - найгірший випадок O(n²), найкращий - O(n) завдяки ранньому виходу:

javascript

function bubbleSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // масив вже відсортований => лінійний прохід
  }
  return a;
}

Порівняння O(n²) і покращеної версії: задача Two Sum (знайти пару із заданою сумою).

javascript

// Наївно: O(n^2)
function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return null;
}

// Ефективно з Map: O(n) за часом, O(n) за пам'яттю
function twoSumHash(nums, target) {
  const map = new Map(); // значення -> індекс
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return null;
}

Різні розміри циклів: O(n·m). Якщо m пропорційний n, це вироджується в O(n²):

javascript

function processGrid(n, m) {
  let ops = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      ops++;
    }
  }
  return ops; // O(n*m); якщо m ≈ n, то O(n^2)
}

Підрахунок операцій та інтуїція

Часто трапляється трикутний перебір: i йде від 0 до n-1, j йде від i+1 до n-1. Тоді кількість ітерацій дорівнює 1 + 2 + ... + (n-1) = n(n-1)/2, що асимптотично веде до O(n²). Це пояснює, чому порівняння «кожного з кожним» швидко стає дорогим.

Як це відчувається на практиці

n	Операцій ~ n²	Зростання vs n=1
10	100	×100
100	10 000	×10 000
1 000	1 000 000	×1 000 000

Коли O(n²) прийнятно

Малі n (десятки чи сотні), одноразовий запуск, немає жорстких SLO.
Прототипування, де важлива швидкість розробки, а не ідеальна асимптотика.

Як покращити з O(n²) до швидше

Використовувати хеш-структури (Map/Set) для перевірки належності чи пошуку пари за O(1) у середньому.
Відсортувати і застосувати два вказівники або бінпошук: зазвичай O(n log n) замість O(n²).
Кешування/мемоізація результатів підзадач, щоб не перераховувати однакове.
Раннє зупинення і відсікання випадків, де подальший перебір безглуздий.
Переформулювати задачу (математика/геометрія/структури даних) так, щоб не перебирати «кожного з кожним».

Важливі нюанси на співбесіді

O(n²) - це верхня оцінка (upper bound). Якщо хочете підкреслити «точну» асимптотику, використовуйте Θ(n²).
Вкладені цикли не завжди означають O(n²): якщо внутрішній цикл сумарно виконується сталу кількість разів, складність може бути O(n).
O(n·m) - не те саме, що O(n²). Але якщо m ≈ n, це стає квадратичним.
Пам'ять: O(n²) за часом не означає O(n²) за пам'яттю. Зберігання всіх пар - це вже O(n²) пам'яті; поодинокі вкладені цикли можуть використовувати O(1) пам'яті.

Підсумок

O(n²) - це класична характеристика алгоритмів, що перебирають усі пари елементів. Вона швидко стає непрактичною при зростанні n, тому на співбесідах очікують, що ви або аргументуєте прийнятність квадратичної складності для даного n, або запропонуєте стратегію зниження до O(n log n) чи O(n) за допомогою сортування, хеш-структур та інших прийомів.

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

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

Premium

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