Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що означає часова складність?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Часова складність - це оцінка того, як змінюється час виконання алгоритму при зростанні розміру вхідних даних 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): оптимальний збіг обставин.

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

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

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати794 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.