635
правок
Изменения
Нет описания правки
<br>Внутренний узел, помеченный как <tex> i:j </tex>, указывает сравнение между <tex> a_{i} </tex> и <tex> a_{j} </tex>. Лист, помеченный перестановкой <tex> \left \langle \pi(1), \pi(2), \ldots , \pi(n) \right \rangle </tex>, указывает упорядочение <tex> a_{\pi(1)} \leqslant a_{\pi(2)} \leqslant \ldots \leqslant a_{\pi(n)} </tex>.]]
Любому алгоритму сортировки сравнениями можно сопоставить [[Дерево поиска, наивная реализация|дерево]]. В нем узлам соответствуют операции сравнения элементов, ребрам {{---}} переходы между состояниями алгоритма, а листьям {{---}} конечные перестановки элементов (соответствующие завершению алгоритма сортировки). Необходимо доказать, что высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем <tex>\Omega(n \log n)</tex>, где <tex>n</tex> {{---}} количество элементов.
Ограничимся рассмотрением сортировки перестановок <tex>n</tex> элементов. При сравнении некоторых двух из них, существует два возможных исхода (<tex>a_i < a_j</tex> и <tex>a_i > a_j</tex>), значит, каждый узел дерева имеет не более двух сыновей. Всего существует <tex>n!</tex> различных перестановок <tex>n</tex> элементов, значит, число листьев нашего дерева не менее <tex>n!</tex> (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).
