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

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

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

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

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

Відповідає на питання: «Наскільки погано може бути?»
Дає гарантії: час/пам'ять не гірше за вказану оцінку.
Контрастує з «середнім» і «найкращим» випадками.

Розгорнута відповідь

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

Найкращий випадок: мінімальні витрати. Приклад - пошук елемента, що стоїть на першому місці: O(1).
Середній випадок: усереднення за розподілом входів. Приклад - пошук випадкового елемента в несортованому масиві: ≈O(n/2) → O(n).
Найгірший випадок: максимальні витрати. Приклад - пошук елемента, якого немає в масиві: O(n).

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

Показує, що ви вмієте мислити гарантованими межами часу/пам'яті, а не лише «середньою» продуктивністю.
Дозволяє порівнювати структури даних і алгоритми в умовах пікових навантажень (латентність API, зростання трафіку, атакуючі/adversarial входи).
Допомагає пояснити вибір: «Чому тут підійде хеш-таблиця, а не збалансоване дерево?» - з урахуванням найгіршої складності.

Типові приклади «найгіршого випадку»

Лінійний пошук у несортованому масиві: O(n) - якщо елемента немає (пройти весь масив).
Швидке сортування: O(n^2) - якщо щоразу обирати найгірший опорний елемент (наприклад, вже відсортований масив і поганий вибір півота).
Пошук у хеш-таблиці: O(n) - за численних колізій (усі ключі в одному кошику).
Регулярні вирази з поверненням (backtracking): експоненційне зростання часу на певних рядках (катастрофічний backtracking) - важливо при фільтрації користувацького вводу.

Зв'язок із просторовою складністю

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

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

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

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

У несортованому масиві лінійний пошук у найгіршому випадку вимагає переглянути всі елементи: O(n). Найкращий випадок - елемент знайдено на першому місці: O(1). Середній - приблизно половина проходу: O(n).

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

// Демонстрація: найкращий, середній і найгірший випадки
const arr = Array.from({ length: 100000 }, (_, i) => i); // [0, 1, 2, ...]

console.time('best');
linearSearch(arr, 0); // найкращий випадок: елемент на початку → O(1)
console.timeEnd('best');

console.time('average');
linearSearch(arr, Math.floor(arr.length / 2)); // середній випадок → ≈O(n)
console.timeEnd('average');

console.time('worst');
linearSearch(arr, -1); // найгірший випадок: елемента немає → O(n)
console.timeEnd('worst');

Практичні поради для інтерв'ю

Спочатку проговоріть, що оцінюєте верхню межу: «У найгіршому випадку час - O(n), пам'ять - O(1)».
Коротко порівняйте з альтернативою (наприклад, хеш-таблиця проти масиву) і поясніть, що зміниться в найгіршому випадку.
Озвучте припущення: розподіл входів, можливість попередньої обробки (сортування), обмеження за пам'яттю/латентністю.
Якщо є adversarial входи (користувацький ввід, атаки), орієнтуйтеся на гарантії найгіршого випадку.

Короткий чекліст відповіді на співбесіді

Дати визначення: верхня межа часу/пам'яті на найгіршому вводі.
Назвати асимптотику: O(·) за часом і за пам'яттю.
Порівняти з найкращим/середнім випадками одним реченням.
Навести міні-приклад (пошук, сортування) і пояснити, чому це найгірший ввід.

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

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

Premium

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