Нижняя граница сравнений: почему быстрее n·log n нельзя

Если ты умеешь доказать нижнюю границу Ω(n·log n) деревом решений (n! листьев → высота log(n!) = Θ(n·log n)) и понимаешь, что она относится только к сортировкам сравнениями, листай до «Теперь сам».

Как думаешь, можно ли отсортировать сравнениями быстрее n·log n

Мы видели три сортировки за n·log n - слиянием, быструю, пирамидальную. Естественный вопрос: а вдруг есть ещё умнее, за n или n·log log n? Для сортировок, которые работают ТОЛЬКО через сравнения элементов («какой из этих двух больше?»), ответ строгий и удивительный: НЕЛЬЗЯ. Не «не придумали», а доказано, что нельзя. И доказательство не требует перебирать все алгоритмы - оно смотрит на саму ЗАДАЧУ и считает, сколько информации сравнения способны добыть.

На что это похоже

Игра «угадай число от 1 до 1000» вопросами «да/нет». Каждый вопрос делит оставшиеся варианты надвое, поэтому за k вопросов различишь не больше 2^k вариантов. Чтобы покрыть 1000 вариантов, нужно k ≥ log₂ 1000 ≈ 10 вопросов - меньше физически не хватит информации. Сортировка сравнениями - та же игра: каждое сравнение - вопрос «да/нет», а «вариантов» (возможных исходных порядков) целых n!. Значит вопросов-сравнений нужно хотя бы log₂(n!).

Механизм: дерево решений

Представим ЛЮБОЙ алгоритм сортировки сравнениями как дерево решений. Внутренний узел - это одно сравнение (a[i] < a[j]?), у него два ребёнка: ветка «да» и ветка «нет». Спускаясь от корня, алгоритм задаёт сравнения и в зависимости от ответов идёт влево или вправо. Лист - это конец работы, где алгоритм выдаёт КОНКРЕТНУЮ перестановку как ответ.

Ключевые два факта:

1. Листьев не меньше n!. Вход из n различных элементов может быть в n! порядках, и каждому нужен СВОЙ ответ (своя перестановка, возвращающая порядок). Если бы двух разных входов приводили к одному листу, на одном из них ответ был бы неверен. Значит разных достижимых листьев хотя бы n!.
2. Высота дерева = число сравнений в худшем случае. Самый длинный путь от корня до листа - это самая длинная цепочка сравнений, которую алгоритм может сделать.

Двоичное дерево высоты h имеет не больше 2^h листьев. Раз листьев ≥ n!, то 2^h ≥ n!, откуда h ≥ log₂(n!).

Правило

Любая сортировка СРАВНЕНИЯМИ в худшем случае делает не меньше Ω(n·log n) сравнений. Доказательство: алгоритм - это дерево решений с ≥ n! листьями (по листу на каждый из n! порядков), а двоичное дерево с таким числом листьев имеет высоту ≥ log₂(n!) = Θ(n·log n); высота - это число сравнений в худшем случае. Поэтому слияние, быстрая и пирамидальная - уже оптимальны по порядку роста среди сортировок сравнениями.

Разбор: почему log₂(n!) - это Θ(n·log n)

Нужно показать, что log₂(n!) растёт как n·log n. Сверху: n! ≤ n^n, значит log(n!) ≤ n·log n. Снизу: в произведении n! = 1·2·...·n возьмём только вторую половину множителей - от n/2 до n, их n/2 штук, и каждый ≥ n/2. Тогда n! ≥ (n/2)^(n/2), откуда log(n!) ≥ (n/2)·log(n/2) = Θ(n·log n). Зажали с обеих сторон - значит log₂(n!) = Θ(n·log n). (Строже это даёт формула Стирлинга, но и грубой оценки хватает.) Смысл: n! - астрономически большое число (log от него линеен по n с множителем log n), и чтобы «различить» столько вариантов вопросами да/нет, вопросов нужно порядка n·log n.

Разбор: граница про сравнения, а не про сортировку вообще

Важнейшая оговорка: Ω(n·log n) доказана для алгоритмов, которые узнают о данных ТОЛЬКО через сравнения «больше/меньше». Если разрешить ДРУГИЕ операции - например, использовать сами значения как индексы (адресоваться по значению, а не сравнивать), - граница НЕ действует, и сортировать можно за линейное время. Именно так работают сортировка подсчётом и поразрядная (следующие уроки): они не задают ни одного вопроса «что больше», а раскидывают элементы по ячейкам, соответствующим их значению. Дерево решений к ним неприменимо, потому что их шаги - не двоичные развилки-сравнения. Так что n·log n - это стена для одного класса алгоритмов, а не закон природы для задачи сортировки.

Что ломается без этого

Первая ошибка - искать сортировку сравнениями быстрее n·log n в общем случае: это потерянное время, доказано, что её нет. Понимать это - значит не гнаться за невозможным, а принять n·log n как оптимум и выбирать между слиянием, быстрой и пирамидальной по ДРУГИМ критериям (память, устойчивость, худший случай). Вторая ошибка - обратная: решить, что n·log n - предел для ЛЮБОЙ сортировки, и пройти мимо линейных сортировок подсчётом там, где данные это позволяют. Граница жёсткая, но узкая: она только про сравнения.

Зачем это в работе

Нижняя граница - это редкий и ценный инструмент: она говорит, когда ОСТАНОВИТЬСЯ в оптимизации. Если твоя задача сводится к сортировке сравнениями и ты уже на n·log n - дальше по порядку роста улучшать нечего, доказано; силы надо тратить на константу (кеш, меньше обменов), а не на поиск мифического n. И наоборот: граница подсказывает обходной путь - «а нельзя ли не сравнивать?». Если ключи - целые в разумном диапазоне, ответ «да», и открывается линейная сортировка. Умение доказать нижнюю границу и знать её область действия отличает инженера, который понимает пределы, от того, кто их не видит.

Теперь сам

Почему сортировке трёх различных элементов нужно в худшем случае не меньше 3 сравнений, а не 2? Свяжи ответ с деревом решений.