Що означає "складність алгоритму"?

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

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

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

Детально

Що таке "складність"

Часова складність (time complexity): як зростає кількість елементарних операцій зі збільшенням n.
Просторова складність (space complexity): як зростає обсяг додаткової пам'яті, не рахуючи входу/виходу.
Випадки: найгірший (worst-case), середній (average), найкращий (best-case). На співбесіді за замовчуванням - найгірший, якщо не обумовлено інше.

Нотації

O (Big-O): верхня межа - наскільки швидко може зростати час/пам'ять у найгіршому випадку.
Θ (Theta): точна асимптотика - і верхня, і нижня межа збігаються за порядком.
Ω (Omega): нижня межа - наскільки швидко зростає щонайменше.
Амортизована складність: середня вартість однієї операції в послідовності (наприклад, push у динамічний масив).

Правила швидкої оцінки

Послідовність незалежних блоків: додаємо (беремо домінантний порядок).
Вкладені цикли: перемножуємо кількості ітерацій.
Умовні гілки: беремо найгіршу за складністю.
Ділення задачі навпіл (як бінарний пошук): логарифм O(log n).
Рекурсії з розбиттям (наприклад, сортування): використовуємо рекурентні співвідношення; часто дають O(n log n).
Відкидаємо константи і нижчі порядки: O(3n + 10) → O(n).

Приклади коду і розбір

Лінійний прохід - O(n) за часом, O(1) за пам'яттю:

javascript

function sum(arr) {
  let s = 0;                // O(1)
  for (let i = 0; i < arr.length; i++) { // n разів
    s += arr[i];            // O(1) * n
  }
  return s;                 // O(1)
}
// Разом: O(n) часу, O(1) додаткової пам'яті

Вкладені цикли - O(n^2):

javascript

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {        // n
    for (let j = i + 1; j < arr.length; j++) {  // ~n/2 у середньому
      if (arr[i] === arr[j]) return true;       // O(1)
    }
  }
  return false;
}
// Разом: O(n^2) часу, O(1) пам'яті

Логарифмічна складність (бінарний пошук) - O(log n):

javascript

function binarySearch(sortedArr, target) {
  let l = 0, r = sortedArr.length - 1;
  while (l <= r) {                 // ділимо діапазон навпіл на кожному кроці
    const mid = (l + r) >> 1;
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) l = mid + 1; else r = mid - 1;
  }
  return -1;
}
// O(log n) часу, O(1) пам'яті

Сортування з розбиттям (merge sort) - O(n log n) часу, O(n) пам'яті:

javascript

function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const left = mergeSort(a.slice(0, mid));   // T(n/2)
  const right = mergeSort(a.slice(mid));     // T(n/2)
  return merge(left, right);                 // O(n)
}

function merge(l, r) {
  const res = [];
  let i = 0, j = 0;
  while (i < l.length && j < r.length) {
    if (l[i] <= r[j]) res.push(l[i++]); else res.push(r[j++]);
  }
  return res.concat(l.slice(i)).concat(r.slice(j));
}
// Рекурентне співвідношення: T(n) = 2T(n/2) + O(n) => O(n log n)

Амортизована складність на прикладі push у динамічний масив: більшість операцій O(1), інколи - рідкісні перерозподіли O(n), але в середньому - O(1):

javascript

const a = [];
for (let i = 0; i < 1e6; i++) {
  a.push(i); // зазвичай O(1); при рідкісному збільшенні буфера - дорожче, але амортизовано O(1)
}
// У JavaScript розмір масиву зростає автоматично; модель така сама, як у динамічних масивів

Класи складності та приклади

Клас	Що означає	Приклад
O(1)	Константна	Доступ за індексом у масиві
O(log n)	Логарифмічна	Бінарний пошук
O(n)	Лінійна	Прохід по масиву
O(n log n)	Лінійно-логарифмічна	Merge sort, Quick sort (у середньому)
O(n^2)	Квадратична	Два вкладені цикли по n
O(2^n)	Експоненційна	Повний перебір підмножин
O(n!)	Факторіальна	Перебір усіх перестановок

Пам'ять: як рахувати

Додаткові структури даних: масиви, мапи, стек рекурсії.
Вхід і вихід зазвичай не враховуються (якщо не обумовлено інше).
In-place алгоритми: O(1) дод. пам'яті, але перевірте стек викликів при рекурсії.

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

Говорити лише про найкращий випадок замість найгіршого.
Ігнорувати пам'ять чи рекурсивний стек.
Упускати константи там, де вони значущі на практиці (наприклад, вибір сортування для малих n).
Не враховувати розподіл входу (наприклад, майже відсортованість).

Як відповідати коротко і структуровано

Визначте, що таке n (довжина масиву, кількість вузлів, діапазон значень тощо).
Уточніть випадок (найгірший/середній/найкращий) і обмеження пам'яті.
Оцініть блоки: цикл/вкладеність/гілки/рекурсію. Поясніть правила (додаємо/множимо/беремо максимум).
Назвіть підсумок: час і пам'ять, за потреби - амортизовану оцінку.
Коротко відзначте trade-off'и (швидкість vs пам'ять, стійкість, простота коду).

Міні-кейс: оцінка коду з умовним виходом

javascript

function findFirstGreater(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > x) return i; // ранній вихід
  }
  return -1;
}
// Найгірший випадок: O(n) (нічого не знайшли)
// Найкращий випадок: O(1) (перший елемент підійшов)
// Середній: залежить від розподілу; часто ~O(n)

Підсумок: "складність алгоритму" - це формальний спосіб говорити про масштабованість за часом і пам'яттю відносно розміру входу. На співбесіді важливо вміти назвати нотацію, випадок, припущення про вхід і аргументувати оцінку.

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

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

Premium

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