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

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

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

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

Контент

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

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

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

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

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

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

- Big O - це асимптотична нотація, що описує, як час виконання або споживання пам'яті алгоритму зростає залежно від розміру входу n.
- Вона ігнорує константи і молодші члени, фокусуючись на домінуючому зростанні: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
- Використовується для порівняння алгоритмів і оцінки масштабованості за часом і пам'яттю (time/space complexity).

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

### Що таке Big O

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

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

### Навіщо це потрібно

- Порівнювати алгоритми за масштабованістю, а не за конкретними мілісекундами.
- Обирати структури даних і підходи, які витримають зростання навантаження.
- Комунікувати рішення спільною мовою в командних обговореннях і на співбесідах.

### Основні класи складності

| Клас | Опис | Приклад |
|---|---|---|
| O(1) | Стала часова/пам'ять, не залежить від n | Доступ за індексом масиву |
| O(log n) | Логарифмічне зростання, ділення входу навпіл | Бінарний пошук, операції у збалансованих деревах |
| O(n) | Лінійне зростання, один прохід | Сумування масиву, пошук мінімуму |
| O(n log n) | Лінійний прохід × логарифмічна глибина | Merge sort, Heap sort, ефективні алгоритми сортування |
| O(n²) | Квадратичне зростання, вкладені цикли по n | Перевірка всіх пар, прості сортування (bubble, insertion у найгіршому випадку) |
| O(2ⁿ) | Експоненційне зростання, перебір підмножин | Задачі повного перебору всіх комбінацій, backtracking |
| O(n!) | Факторіальне зростання | Перестановки, повний перебір порядку |

### Як рахувати складність: практичні правила

1. Відкидайте константи: O(3n + 10) → O(n), O(5) → O(1).
2. Беріть домінуючий член: O(n + n²) → O(n²).
3. Послідовні частини додаються, вкладені перемножуються: цикл усередині циклу по n → O(n²).
4. Розділяй-і-володарюй часто дає O(n log n) (наприклад, merge sort). Рекурсивний стек враховуйте в пам'яті.
5. Структури даних важливі: хеш-таблиця - середнє O(1), найгірше O(n); дерево пошуку - O(log n) при балансі, інакше O(n).

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

```javascript
// O(1) - стала складність
function getFirst(arr) {
  return arr[0];
}

// O(n) - лінійний прохід
function sum(arr) {
  let s = 0;
  for (const x of arr) s += x;
  return s;
}

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

// O(n log n) - merge sort (у середньому/найгіршому), пам'ять O(n)
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}
function merge(left, right) {
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) res.push(left[i++]); else res.push(right[j++]);
  }
  return res.concat(left.slice(i)).concat(right.slice(j));
}

// O(n^2) - перевірка наявності дублікатів наївно
function hasDuplicateNested(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(2^n) - генерація всіх підмножин (power set)
function subsets(nums) {
  const res = [[]];
  for (const x of nums) {
    const add = res.map(s => s.concat(x));
    res.push(...add);
  }
  return res;
}

// Пам'ять: O(1) проти O(n)
function maxValue(arr) { // O(1) дод. пам'ять
  let max = -Infinity;
  for (const x of arr) if (x > max) max = x;
  return max;
}
function copyArray(arr) { // O(n) дод. пам'ять
  const copy = [];
  for (const x of arr) copy.push(x);
  return copy;
}

// Амортизована складність: push у динамічний масив - O(1) амортизовано
class Stack {
  constructor() {
    this.data = new Array(1);
    this.size = 0;
  }
  push(x) {
    if (this.size === this.data.length) {
      const newData = new Array(this.data.length * 2);
      for (let i = 0; i < this.data.length; i++) newData[i] = this.data[i];
      this.data = newData; // рідкісна подія O(n)
    }
    this.data[this.size++] = x; // O(1) зазвичай, O(1) амортизовано
  }
  pop() {
    if (this.size === 0) return undefined;
    return this.data[--this.size];
  }
}
```

### Time vs Space complexity

Оцінюйте обидва ресурси: час і пам'ять. У пам'ять включайте: додаткові структури (масиви, хеш-таблиці), вихідний результат, рекурсивний стек, внутрішні буфери. Іноді розумно обміняти пам'ять на прискорення (time-memory trade-off).

### Найгірший, середній і найкращий випадки. Амортизована оцінка

- Найгірший випадок (worst-case) - що зазвичай запитують на співбесіді: наприклад, пошук у незбалансованому BST може бути O(n).
- Середній випадок - корисний для хеш-таблиць: пошук/вставка O(1) при хорошій хеш-функції і низькому навантаженні.
- Найкращий випадок - рідко корисний, але уточнюйте при аналізі (наприклад, вставка у відсортований масив для insertion sort - O(n) у середньому, O(n²) у найгіршому, O(n) у найкращому).
- Амортизована складність - середня вартість операції в послідовності: наприклад, динамічне розширення масиву робить push O(1) амортизовано.

### Типові помилки і нюанси

- Ігнорування прихованих констант: O(n) з величезною константою може програти O(n log n) на малих n.
- Забувають враховувати вартість сортування: часто вузьке місце - саме sort O(n log n).
- Пам'ять: розмір виходу теж рахується (створення нового масиву O(n)).
- Хеш-таблиці: середнє O(1) можливе тільки при хорошій хеш-функції і ребалансуваннях (інакше найгірше O(n)).

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

1. Позначте n - розмір входу (і m, якщо є другий параметр).
2. Назвіть часову і просторову складність: «Час O(n log n), пам'ять O(n) через тимчасовий масив».
3. Обґрунтуйте за правилами: послідовність/вкладеність/домінування. Вкажіть найгірший/середній/найкращий, якщо доречно.
4. Озвучте припущення: «Хеш-операції в середньому O(1), припускаю хорошу хеш-функцію».
5. Порівняйте альтернативи коротко: «Цей підхід O(n log n) швидший на великих n, але вимагає O(n) пам'яті, тоді як інший - O(1) пам'яті, але O(n²) за часом».

### Висновок

Big O - мова для оцінки масштабованості алгоритмів. Знаючи класи складності, правила їх обчислення і типові структури даних, ви зможете швидко аргументувати вибір рішення і коректно оцінити час і пам'ять на співбесіді.

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

Для рев’юера

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

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