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

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

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

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

Контент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

```js
// Лінійний пошук: повертає індекс або -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(·) за часом і за пам'яттю.
- Порівняти з найкращим/середнім випадками одним реченням.
- Навести міні-приклад (пошук, сортування) і пояснити, чому це найгірший ввід.

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

Для рев’юера

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

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