Що означає часова складність?

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

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

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

Докладний розбір

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

Це спосіб описати швидкість зростання кількості елементарних операцій алгоритму залежно від розміру входу n. Ми не вимірюємо мілісекунди, а рахуємо базові кроки (порівняння, присвоєння, звернення до структур даних) і дивимося, як їхня кількість зростає при збільшенні n.

Вимірює не точний час, а порядок зростання операцій.
Рахуємо елементарні операції; конкретний «час на машині» абстрагуємо.
Дивимося на n, ігноруємо сталі множники і молодші члени.

Нотації: O, Θ, Ω

O(f(n)) - верхня межа (не швидше, ніж f(n) з точністю до константи). Часто використовується для «найгіршого випадку».
Θ(f(n)) - точна асимптотика (і верхня, і нижня межі збігаються за порядком).
Ω(f(n)) - нижня межа (не повільніше, ніж f(n) з точністю до константи).

Випадки оцінки

Найгірший випадок (worst-case): гарантована верхня межа.
Середній випадок (average-case): математичне сподівання за розподілом входів.
Найкращий випадок (best-case): оптимальний збіг обставин.

Як прикидувати складність (правила)

Послідовні фрагменти - складаємо. Беремо домінуючий член (більшого порядку).
Один цикл по n - O(n). Якщо тіло циклу O(1).
Вкладені цикли - перемножуємо (наприклад, два по n дають O(n²)).
Ділимо задачу навпіл кожен крок - O(log n) (бінарний пошук).
«Розділяй і володарюй»: T(n) = a·T(n/b) + f(n). Часто дає O(n log n) (наприклад, сортування злиттям).
Типові операції структур даних:

Хеш-таблиця: пошук/вставка/видалення - очікувано O(1), у найгіршому O(n).
Купа (пріоритетна черга): вставка/вилучення - O(log n).
Збалансоване дерево пошуку: пошук/вставка/видалення - O(log n).

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

Позначення	Приклад	Коментар
O(1)	Доступ за індексом, амортизований push у динамічний масив	Не залежить від n
O(log n)	Бінарний пошук, операції у збалансованому BST	Кожен крок скорочує пошук у сталу кількість разів
O(n)	Лінійний прохід по масиву	Пропорційно розміру входу
O(n log n)	Merge sort, Heap sort, Quick sort (у середньому), побудова купи	Часто у «розділяй і володарюй»
O(n²)	Два вкладені цикли, сортування бульбашкою	Квадратичне зростання операцій
O(2^n)	Перебір усіх підмножин	Експоненційне зростання, швидко стає непрактичним
O(n!)	Перебір усіх перестановок (наприклад, brute-force TSP)	Факторіальне зростання, практично не масштабується

Приклади коду

Бінарний пошук - O(log n)

function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (arr[m] === x) return m;
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1; // не знайдено
}
// Кількість ітерацій циклу ≈ log2(n)

Два вкладені цикли - O(n²)

function countPairsEqual(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) count++;
    }
  }
  return count; // квадратична складність
}

Пошук пари із заданою сумою за O(n) часу і O(n) пам'яті

function hasPairWithSum(arr, target) {
  const seen = new Set();
  for (const v of arr) {
    if (seen.has(target - v)) return true;
    seen.add(v);
  }
  return false;
}
// Лінійний прохід + хеш-таблиця: очікувано O(1) на операцію, разом O(n)

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

Іноді окрема операція може займати багато часу, але середня вартість серії операцій - стала. Класичний приклад - push у динамічний масив із подвоєнням місткості.

Більшість push - O(1): просто записуємо елемент у вільну комірку.
Іноді відбувається перерозподіл і копіювання - O(n) для цього кроку.
Якщо подвоювати розмір, сумарна ціна N вставок - O(N), отже амортизовано O(1) на вставку.

Практичні зауваження

Константи і кеші важливі на практиці: два алгоритми з однаковою O-оцінкою можуть працювати по-різному.
Розподіл вхідних даних впливає на середній випадок.
Попереднє сортування часто змінює складність подальших кроків.
Оцінка операцій хеш-таблиці - очікувана; у найгіршому випадку - O(n) через колізії.
Пам'ятайте про просторову складність і компроміси «час-пам'ять».

Чек-лист на співбесіді

Визначте, що таке n (довжина масиву, кількість вершин, кількість ребер тощо).
Назвіть найгірший і середній випадок, якщо доречно.
Розберіть цикли і рекурсію: правильно підсумовуйте/перемножуйте.
Скоротіть до домінуючого члена і спростіть до Big O.
Відзначте додаткові ресурси: пам'ять, I/O, мережеві виклики.

Короткий підсумок

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

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

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

Premium

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