Теорема о нижней оценке для сортировки сравнениями

Материал из Викиконспекты
Версия от 21:21, 7 мая 2012; Qwerty787788 (обсуждение | вклад) (Статься переписана, добавлены источники, категории, шаблон "определение")
Перейти к: навигация, поиск
Определение:
Сортировка сравнениями — алгоритм сортировки, который совершает операции сравнения элементов, но никак не использует их внутреннюю структуру.


Теорема (о нижней оценке для сортировки сравнениями):
В худшем случае любой алгоритм сортировки сравнениями выполняет [math]\Omega(n \log n)[/math] сравнений, где [math]n[/math] — число сортируемых элементов. (Теорема справедлива и для рандомизированных алгоритмов сортировки, но в статье не приводится доказательство этого факта).
Доказательство:
[math]\triangleright[/math]

Любому алгоритму сортировки сравнениями можно сопоставить дерево. В нем узлами являются операции сравнения элементов, ребрами — переходы между состояниями алгоритма, а листьями — конечные перестановки элементов (соответствующие завершению алгоритма сортировки). Необходимо доказать, что высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем [math]O(n \log n)[/math], где [math]n[/math] — количество элементов.

При сравнении двух элементов, существует два возможных исхода ([math]a_i \lt a_j[/math] и [math]a_i \geq a_j[/math]), значит, каждый узел дерева имеет не более двух сыновей. Всего существует [math]n![/math] различных перестановок [math]n[/math] элементов, значит, число листьев нашего дерева не менее [math]n![/math] (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).

Пример дерева для алгоритма сортировки [math]n = 3[/math] элементов:

DecisionTree.png


Докажем, что двоичное дерево с [math]n![/math] листьями имеет глубину [math]\Omega(n \log n)[/math]:

[math] h = \log_2 n! = log_2 1 + \log_2 2 + \ldots + \log_2 n \gt [/math] [math]n/2 \log_2 (n/2) = n/2(\log_2 n - 1) = \Omega (n \log n)[/math]

Итак, для любого алгоритма сортировки сравнениями, существует такая перестановка, на которой он выполнит [math]\Omega(n \log n)[/math] сравнений, ч. т. д.
[math]\triangleleft[/math]

Источники