81
правка
Изменения
м
Нет описания правки
Теорема
|about=о нижней оценке для сортировки сравнениями
|statement=В худшем случае любой алгоритм сортировки сравнениями выполняет <tex>\Omega(n \log n)</tex> сравнений, где <tex>n</tex> {{---}} число сортируемых элементов. (Теорема справедлива и для рандомизированных алгоритмов сортировки, но в статье не приводится доказательство этого факта).
|proof=Любому алгоритму сортировки сравнениями можно сопоставить дерево. В нем узлами являются узлам соответствуют операции сравнения элементов, ребрами ребрам {{---}} переходы между состояниями алгоритма, а листьями листьям {{---}} конечные перестановки элементов (соответствующие завершению алгоритма сортировки). Необходимо доказать, что высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем <tex>O(n \log n)</tex>, где <tex>n</tex> {{---}} количество элементов.
При сравнении двух элементов, существует два возможных исхода (<tex>a_i < a_j</tex> и <tex>a_i \geq a_j</tex>), значит, каждый узел дерева имеет не более двух сыновей. Всего существует <tex>n!</tex> различных перестановок <tex>n</tex> элементов, значит, число листьев нашего дерева не менее <tex>n!</tex> (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).
Докажем, что двоичное дерево с <tex>n!</tex> листьями имеет глубину <tex>\Omega(n \log n)</tex>:
<tex> h = \geq \log_2 n! = \log_2 1 + \log_2 2 + \ldots + \log_2 n ></tex> <tex>n/2 \log_2 (n/2) = n/2(\log_2 n - 1) = \Omega (n \log n)</tex>
Итак, для любого алгоритма сортировки сравнениями, существует такая перестановка, на которой он выполнит <tex>\Omega(n \log n)</tex> сравнений, ч. т. д.
