Лучший, средний, худший случай
Best case, average case, worst case — три сценария анализа сложности алгоритма, описывающие его поведение при наилучших, типичных и наихудших входных данных соответственно.
Зачем нужно
Знание только worst case может дать пессимистичную оценку, а только best case — оптимистичную. Полная картина — все три сценария — помогает правильно выбрать алгоритм для конкретного приложения. Например, Quick Sort имеет O(n log n) в среднем, но O(n^2) в худшем случае — что критично для систем реального времени.
Где используется
- Выбор алгоритма сортировки в зависимости от ожидаемых данных
- Анализ производительности алгоритмов на собеседованиях
- Проектирование систем с гарантиями по времени отклика
- Сравнительный анализ алгоритмов поиска
Основной контент
Определения
- Best case (O — нотация Ω): минимальное число операций на любом входе размера n.
- Average case (нотация Θ): среднее число операций по всем равновероятным входам размера n.
- Worst case (Big O): максимальное число операций на любом входе размера n.
На практике Big O чаще всего подразумевает worst case.
Линейный поиск: три случая
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// Best case: O(1) — target первый элемент
// Average case: O(n/2) = O(n) — target в середине
// Worst case: O(n) — target последний или отсутствует
Quick Sort: три случая
// Best case: O(n log n) — pivot делит массив пополам каждый раз
// Average case: O(n log n) — случайный pivot
// Worst case: O(n²) — отсортированный массив, pivot = последний элемент
// [1, 2, 3, 4, 5] с pivot = arr[hi]:
// pivot=5, left=[1,2,3,4], right=
// pivot=4, left=[1,2,3], right= → высота рекурсии = n → O(n²)
Бинарный поиск
// Best case: O(1) — target в середине
// Average case: O(log n)
// Worst case: O(log n) — target в краях или отсутствует
Сводная таблица алгоритмов
| Алгоритм | Best | Average | Worst |
|---|---|---|---|
| Линейный поиск | O(1) | O(n) | O(n) |
| Бинарный поиск | O(1) | O(log n) | O(log n) |
| Bubble Sort | O(n) | O(n²) | O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) |
| Hash Table (lookup) | O(1) | O(1) | O(n) |
Average case vs амортизированный анализ
Average case: среднее по всем возможным входным данным
(предполагает распределение вероятностей)
Amortized: среднее по серии операций в худшем случае
(нет предположений о входных данных)
Пример: Array.push
Average case: O(1) — при случайных операциях
Amortized: O(1) — гарантированно для любой последовательности push
Частые ошибки
- Использовать только worst case для принятия решений — Quick Sort часто быстрее Merge Sort на практике, несмотря на O(n^2) в худшем.
- Путать average case с амортизированным анализом — это разные понятия.
- Игнорировать best case: Insertion Sort при почти отсортированных данных — O(n), что лучше Merge Sort.
- Не указывать, какой случай описывает Big O в ответе на собеседовании — уточняйте явно.