Best, Average, and Worst Case

Проблема

Сказать «этот алгоритм - O(n log n)» звучит как законченный факт, но он может быть правдой только в среднем или только в лучшем случае, а в худшем - алгоритм внезапно станет O(n²). Тот, кто не уточнил, какой именно случай имеется в виду, рискует выбрать алгоритм по красивой цифре из статьи и получить неприятный сюрприз в проде на конкретном, неудачно устроенном входе - там, где «редкий» худший случай оказался ровно тем, что регулярно происходит с реальными данными.

Решение

Три случая - это три разных вопроса об одном и том же алгоритме: лучший случай - сколько работы потребуется на самом удачном для алгоритма входе, худший - на самом неудачном, средний - сколько потребуется в ожидании по типичному распределению входов. Когда Big O упоминают без уточнения, по умолчанию имеют в виду худший случай - это негласное соглашение, а не строгое правило, поэтому уточнять явно всё равно стоит. Узнать, какой случай перед вами, можно, спросив: «какое конкретно расположение данных даёт эту цифру?» - если ответ разный для разных входов одного размера n, речь именно о лучшем/среднем/худшем случае, а не о едином классе.

Как это работает

Формально: лучший случай - это минимум объёма работы по всем входам размера n, худший - максимум по всем входам размера n, средний - математическое ожидание объёма работы при заданном распределении входов (обычно предполагается равномерное случайное распределение, если не сказано иное). Это три разных функции от n, и для одного и того же алгоритма они вполне могут иметь разный порядок роста - не просто разные константы, а разные классы Big O целиком.

Числа linearSearch делают разницу наглядной. При n = 1 000: лучший случай - 1 сравнение, средний - около 500, худший - 1 000. При n = 1 000 000: лучший всё так же 1, средний - 500 000, худший - 1 000 000. Лучший случай не меняется вместе с n вообще - он O(1), а не O(n), хотя формально принадлежит тому же самому алгоритму, который называют «O(n) в худшем случае».

Когда Big O упоминают без уточнения - «этот алгоритм O(n log n)» - по молчаливому соглашению почти всегда имеют в виду худший случай. Это соглашение, а не строгое правило языка нотации, и именно поэтому путаница возникает так часто: автор может иметь в виду средний случай, а читатель по умолчанию поймёт это как худший - или наоборот.

Разброс между тремя случаями сильно различается от алгоритма к алгоритму. У бинарного поиска (материал про O(log n)) все три случая совпадают - O(log n) для любого расположения искомого элемента, потому что диапазон поиска всегда делится пополам независимо от входа. У Quick Sort (в разделе сортировок) - самый широкий разрыв из уже реализованных алгоритмов: O(n log n) в среднем и лучшем случае, но O(n²) в худшем при неудачном выборе опорного элемента на уже отсортированных данных.

Лучший случай не всегда встроен в алгоритм изначально - иногда это результат осознанной оптимизации кода. Bubble Sort (в разделе сортировок) с проверкой флага swapped завершает работу за O(n), если очередной проход не произвёл ни одной перестановки - это значит, что массив уже отсортирован. Без этой проверки тот же самый Bubble Sort выполнял бы все проходы всегда, и его лучший случай совпадал бы с худшим - O(n²) в обоих. Лучший случай может зависеть от конкретной реализации не меньше, чем от самого входа.

Средний случай опирается на предположение о распределении входов, и это предположение - самое слабое место всей идеи. Анализ среднего случая обычно берёт равномерно случайные данные, но реальные данные часто устроены совсем не так: логи почти всегда почти отсортированы по времени, пользовательский ввод часто повторяется. Алгоритм с «хорошим средним случаем O(n log n)», рассчитанным на случайные данные, на систематически неслучайных реальных данных может вести себя куда ближе к своему худшему случаю, чем к заявленному среднему.

Инженерная реакция на плохой худший случай - гибридные алгоритмы, которые меняют стратегию на лету. Intro Sort (в разделе сортировок) начинает как Quick Sort, но переключается на Heap Sort, если глубина рекурсии намекает на приближение к худшему случаю - гарантируя O(n log n) даже там, где чистый Quick Sort скатился бы к O(n²). Timsort (в разделе сортировок) устроен похоже: гарантирует O(n log n) в худшем случае, но ускоряется на частично отсортированных данных, приближаясь к O(n) на них.

Нюансы выбора

Гарантия против типичной скорости - системы реального времени и другой код с жёсткими ограничениями по времени нуждаются в гарантии худшего случая, а не в «обычно быстро».

Известное распределение входов - если про реальные данные точно известно, что они почти отсортированы или иначе неслучайны, стоит смотреть на поведение алгоритма именно на таких данных, а не на абстрактный средний случай.

Точная коммуникация сложности - всегда указывать, о каком случае идёт речь, при обсуждении Big O с коллегами - невысказанное соглашение о «худшем случае по умолчанию» слишком часто не срабатывает на практике.

Совпадение всех трёх случаев как сигнал стабильности - если лучший, средний и худший случай у алгоритма совпадают (как у бинарного поиска), это признак того, что его поведение не зависит от конкретных входных данных - предсказуемость без сюрпризов.

Примеры в коде

Timsort (в разделе сортировок, стандарт сортировки в Python и Java) - спроектирован так, чтобы гарантировать O(n log n) в худшем случае и одновременно ускоряться до почти O(n) на частично отсортированных реальных данных.

Intro Sort (в разделе сортировок, используется в реализациях std::sort в C++) - переключается с Quick Sort на Heap Sort при признаках приближения к худшему случаю, устраняя главный недостаток чистого Quick Sort.

Авионика и медицинское оборудование - системы, где редкий, но катастрофически медленный худший случай недопустим в принципе, поэтому выбор алгоритма там определяется именно гарантией худшего случая, а не средней скоростью.

Планировщики запросов в базах данных - выбирают между стратегиями выполнения запроса (например, полное сканирование таблицы против использования индекса), делая ставку именно на предполагаемое типичное распределение данных - то есть буквально на средний случай для конкретной таблицы.

Когда применять

• Когда сравниваются два алгоритма с одинаковой средней сложностью, но разным худшим случаем - разница проявится именно на неудачных входах.
• Когда реальные данные заведомо не случайны (например, часто почти отсортированы) - тогда важнее не абстрактный средний случай, а поведение алгоритма именно на таких данных.

Примеры из практики

• Quick Sort (в разделе сортировок) - O(n log n) в среднем, но O(n²) в худшем случае на неудачно выбранном опорном элементе и уже отсортированном входе.
• Bubble Sort (в разделе сортировок) - с оптимизацией раннего выхода даёт O(n) в лучшем случае на уже отсортированном массиве, но остаётся O(n²) в худшем.