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

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

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

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

Контент

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

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

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

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

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

## Що означає "найгірший випадок" (worst case)?

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

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

### Докладне пояснення

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

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

- Гарантії продуктивності: показує верхню межу і допомагає виконувати SLA.
- Оцінка масштабованості: як алгоритм поводиться при збільшенні n.
- Порівняння альтернатив: вибір між алгоритмами і структурами даних.
- Безпека і стійкість: розуміння найгірших сценаріїв допомагає уникнути деградацій у продакшені.

#### Best, Average, Worst, Амортизована

- Best case (найкращий випадок): мінімальні витрати на «вдалому» вході.
- Average case (середній випадок): математичне сподівання витрат за всіма входами (або деяким розподілом).
- Worst case (найгірший випадок): максимальні витрати за всіма входами розміру n (верхня межа).
- Амортизована складність: середня вартість операції на довгій послідовності операцій (наприклад, push у динамічний масив - амортизовано O(1), хоча окрема операція розширення - дорожча).

#### Приклади для різних алгоритмів

1. Лінійний пошук по масиву: worst O(n) (елемент у кінці або відсутній), best O(1), average O(n).
2. Бінарний пошук у відсортованому масиві: worst O(log n), оскільки глибина ділень логарифмічна.
3. Швидке сортування (quicksort): average O(n log n), але worst O(n²), якщо опорний елемент обирається невдало (наприклад, перший при вже відсортованому масиві).
4. Хеш-таблиця: пошук у середньому O(1), але worst O(n) при численних колізіях (наприклад, зловмисні ключі).
5. Збалансоване дерево пошуку (AVL/Red-Black): пошук/вставка/видалення - worst O(log n) завдяки балансуванню.

#### Приклад коду: найгірший випадок для лінійного пошуку

```
// O(n) у найгіршому випадку: елемент відсутній або перебуває в самому кінці
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // ранній вихід - кращий/середній випадок
  }
  return -1; // пройшли весь масив - найгірший випадок
}

const data = Array.from({ length: 100000 }, (_, i) => i); // [0..99999]
console.time('worst');
linearSearch(data, -1); // відсутній: найгірший сценарій
console.timeEnd('worst');
```

#### Приклад коду: найгірший випадок для швидкого сортування

```
// Просте швидке сортування з вибором першого елемента як опорного
// На відсортованому масиві такий вибір дає глибину рекурсії n і O(n^2)
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

const sorted = Array.from({ length: 20000 }, (_, i) => i);
console.time('qs-worst');
quickSort(sorted); // найгірший випадок для даного вибору опорного
console.timeEnd('qs-worst');
```

#### Як міркувати про найгірший випадок на співбесіді

- Визначте розмірність задачі: що таке n (довжина масиву, кількість вузлів, кількість запитів)?
- Знайдіть гілки алгоритму і «несприятливі» входи, які максимізують роботу.
- Оцініть вкладені цикли, рекурсію і домінуючі операції (порівняння, переміщення, виклики API).
- Запишіть підсумкову верхню межу в Big-O і, за потреби, вкажіть пам'ять (Space Complexity).
- Якщо доречно - згадайте захисні заходи (рандомізація, балансування, ліміти) для пом'якшення найгірших сценаріїв.

#### Коротке формулювання для відповіді на співбесіді

> Найгірший випадок - це верхня межа складності алгоритму: максимальні витрати часу та/або пам'яті для будь-якого входу розміру n. Вона показує, наскільки повільно алгоритм може працювати в найнесприятливішому сценарії, і дає гарантії продуктивності.

#### Контексти у веб-розробці

- Маніпуляції з DOM: обхід/зміна великої кількості вузлів - часто O(n), де n - кількість елементів.
- Парсинг JSON/CSV: час парсингу зростає з розміром входу - O(n).
- Регулярні вирази: невдалі патерни можуть мати катастрофічний бектрекінг - аж до експоненційного worst case.
- SQL/N+1-запити: найгірший випадок - повне сканування таблиці або каскад із сотень запитів, що дає O(n²) за кількістю сутностей.
- Черги/повтори в мережі: агресивні повтори без бек-офф можуть багаторазово збільшувати час у найгіршому випадку.

#### Типові пастки

- Плутанина між середнім випадком і амортизованою складністю.
- Ігнорування моделі вхідних даних: у найгіршому випадку важливий саме «найгірший» ввід, а не типовий.
- Забувають про пам'ять: іноді час прийнятний, але пам'ять у найгіршому випадку стає вузьким місцем.
- Фокус тільки на Big-O без констант: теоретично однакові алгоритми можуть сильно відрізнятися на практиці.

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

Для рев’юера

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

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