Що означає асимптотична складність?

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

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

Асимптотична складність - це спосіб оцінювати, як зростають витрати алгоритму (за часом і пам'яттю) при збільшенні розміру вхідних даних n. Ми описуємо зростання функціями і порівнюємо їх за порядком, опускаючи константи і молодші доданки. Для позначень використовують нотації O (верхня межа), Θ (точна оцінка) і Ω (нижня межа).

Що вимірюємо: час виконання та/або споживання пам'яті як функцію від n.
Навіщо: порівняти алгоритми за масштабованістю, а не за конкретними мілісекундами.
Як читається: O(n log n) зростає повільніше, ніж O(n²), а O(1) - стала.

Розгорнуте пояснення

Асимптотична складність описує поведінку алгоритму при великих n, тобто «в межі». Замість абсолютних вимірів ми рахуємо, скільки базових операцій виконається і як це число зростає зі збільшенням n. Це дозволяє порівнювати алгоритми незалежно від мови, заліза й оптимізацій компілятора/рушія.

Нотації

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

Чому відкидаємо константи і молодші доданки

Константи і молодші порядки не впливають на масштабованість. Алгоритм із 1000·n швидший за алгоритм із 0.001·n² лише до певного порогу; при великому n квадратичний неминуче програє лінійному. Тому O(n) кращий за O(n²), навіть якщо реалізація O(n) повільніша на малих входах.

Типові класи складності та інтуїція

O(1): стала - доступ до елемента масиву за індексом, хеш-вставка/пошук (у середньому).
O(log n): логарифмічна - бінарний пошук, операції у збалансованих деревах.
O(n): лінійна - один прохід по даних (filter/map/reduce).
O(n log n): квазілінійна - ефективні сортування порівняннями (швидке/злиттям), багато «розділяй і володарюй».
O(n²): квадратична - два вкладені проходи (наївний пошук дублікатів, бульбашкове сортування).
O(2^n), O(n!): експонента/факторіал - повний перебір підмножин/перестановок.

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

javascript

// O(1): доступ за індексом і push (амортизовано)
const arr = [10, 20, 30];
const x = arr[1]; // O(1)
arr.push(40);      // амортизовано O(1)

// O(n): лінійний пошук
function linearSearch(a, target) {
  for (let i = 0; i < a.length; i++) {
    if (a[i] === target) return i; // найкращий випадок: O(1), найгірший: O(n)
  }
  return -1;
}

// O(log n): бінарний пошук (масив має бути відсортований)
function binarySearch(a, target) {
  let l = 0, r = a.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (a[m] === target) return m;
    if (a[m] < target) l = m + 1; else r = m - 1;
  }
  return -1; // найгірший випадок: O(log n)
}

// O(n log n): сортування (типова середня оцінка)
const sorted = [...arr].sort((a, b) => a - b); // середня: O(n log n)

// O(n^2): вкладені цикли
function hasDuplicatesQuadratic(a) {
  for (let i = 0; i < a.length; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if (a[i] === a[j]) return true;
    }
  }
  return false; // найгірший випадок: O(n^2)
}

// Оптимізація до O(n) за часом і O(n) за пам'яттю з використанням множини
function hasDuplicatesLinear(a) {
  const seen = new Set();
  for (const v of a) {
    if (seen.has(v)) return true;
    seen.add(v);
  }
  return false; // час: O(n), пам'ять: O(n)
}

Найкращий, середній і найгірший випадок

Лінійний пошук: найкращий O(1) (перший елемент), середній O(n), найгірший O(n).
Бінарний пошук: найкращий O(1), найгірший O(log n).
Швидке сортування: середнє O(n log n), найгірше O(n²) без рандомізації/вдалого вибору опорного.

Амортизована складність

Іноді окрема операція дорога, але в середньому по серії операцій - дешева. Приклад: динамічний масив при нестачі місця подвоює буфер і копіює елементи (рідкісна операція O(n)). Однак більшість push - O(1), тому середня вартість одного push по довгій серії - амортизовано O(1).

Пам'ять (space complexity)

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

Як відповідати на співбесіді

Визначте n: розмір входу (кількість елементів, вершин, ребер, довжина рядка).
Опишіть, які операції домінують і скільки разів вони виконуються (лічильник ітерацій, рекурентні співвідношення).
Дайте оцінки за часом і пам'яттю: найкращий/середній/найгірший, і за потреби - амортизовану.
Обґрунтуйте спрощення: чому відкинули константи і молодші члени, який фактор зростання домінує.

Короткий чек-лист

Назвіть вхідний параметр n.
Визначте домінуючі операції та їхню кількість.
Запишіть оцінку: O, Θ, Ω (час і пам'ять).
Відзначте найкращий/середній/найгірший або амортизований випадки.

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

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

Premium

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