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

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

Що означає "найгірший випадок" (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), хоча окрема операція розширення - дорожча).

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

Лінійний пошук по масиву: worst O(n) (елемент у кінці або відсутній), best O(1), average O(n).
Бінарний пошук у відсортованому масиві: worst O(log n), оскільки глибина ділень логарифмічна.
Швидке сортування (quicksort): average O(n log n), але worst O(n²), якщо опорний елемент обирається невдало (наприклад, перший при вже відсортованому масиві).
Хеш-таблиця: пошук у середньому O(1), але worst O(n) при численних колізіях (наприклад, зловмисні ключі).
Збалансоване дерево пошуку (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 без констант: теоретично однакові алгоритми можуть сильно відрізнятися на практиці.

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

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

Premium

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