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

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

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

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

Контент

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

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

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

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

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

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

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

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

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

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

Для рев’юера

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

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