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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
{{
 
{{
 
Теорема
 
Теорема
−
|about=о нижней оценке для сортировки сравнениями
+
|about=о нижней оценке для сортировки сравнением
 
|statement=В худшем случае любой алгоритм сортировки сравнениями выполняет <tex>\Omega(n \log n)</tex> сравнений, где <tex>n</tex> {{---}} число сортируемых элементов.
 
|statement=В худшем случае любой алгоритм сортировки сравнениями выполняет <tex>\Omega(n \log n)</tex> сравнений, где <tex>n</tex> {{---}} число сортируемых элементов.
  
−
|proof=Любому алгоритму сортировки сравнениями можно сопоставить дерево. В нем узлам соответствуют операции сравнения элементов, ребрам {{---}} переходы между состояниями алгоритма, а листьям {{---}} конечные перестановки элементов (соответствующие завершению алгоритма сортировки). Необходимо доказать, что высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем <tex>\Omega(n \log n)</tex>, где <tex>n</tex> {{---}} количество элементов.
+
 
 +
|proof=[[Файл:G2.png|450px|thumb|Пример дерева для алгоритма сортировки трех элементов.
 +
<br>Внутренний узел, помеченный как <tex> i:j </tex>, указывает сравнение между <tex> a_{i} </tex> и <tex> a_{j} </tex>. Лист, помеченный перестановкой <tex> \left \langle \pi(1), \pi(2), \dots , \pi(n) \right \rangle </tex>, указывает упорядочение <tex> a_{\pi(1)} \leqslant a_{\pi(2)} \leqslant \dots \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> (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).
 
Ограничимся рассмотрением сортировки перестановок <tex>n</tex> элементов. При сравнении некоторых двух из них, существует два возможных исхода (<tex>a_i < a_j</tex> и <tex>a_i > a_j</tex>), значит, каждый узел дерева имеет не более двух сыновей. Всего существует <tex>n!</tex> различных перестановок <tex>n</tex> элементов, значит, число листьев нашего дерева не менее <tex>n!</tex> (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).
  
−
[[Файл:G2.png|450px|thumb|Пример дерева для алгоритма сортировки трех элементов.
 
−
<br>Внутренний узел, помеченный как <tex> i:j </tex>, указывает сравнение между <tex> a_{i} </tex> и <tex> a_{j} </tex>. Лист, помеченный перестановкой <tex> \left \langle \pi(1), \pi(2), \dots , \pi(n) \right \rangle </tex>, указывает упорядочение <tex> a_{\pi(1)} \leqslant a_{\pi(2)} \leqslant \dots \leqslant a_{\pi(n)} </tex>.]]
 
  
  
Строка 19: Строка 21:
  
 
Итак, для любого алгоритма сортировки сравнениями, существует такая перестановка, на которой он выполнит <tex>\Omega(n \log n)</tex> сравнений, ч. т. д.
 
Итак, для любого алгоритма сортировки сравнениями, существует такая перестановка, на которой он выполнит <tex>\Omega(n \log n)</tex> сравнений, ч. т. д.
 +
}}
 +
 +
==Следствие==
 +
 +
{{Утверждение
 +
|statement=Пирамидальная сортировка и сортировка слиянием являются асимптотически оптимальными  сортировками сравнением.
 +
|proof=Верхние границы <tex> O(n \log n) </tex> времени работы пирамидальной сортировки и сортировки слиянием совпадают с нижней границей <tex>\Omega(n \log n)</tex> для наихудшего случая из теоремы о нижней границе для сортировки сравнением.
 
}}
 
}}
  

Версия 22:34, 12 июня 2016

Сортировка сравнениями — алгоритм сортировки, который совершает операции сравнения элементов, но никак не использует их внутреннюю структуру.

Теорема (о нижней оценке для сортировки сравнением):
В худшем случае любой алгоритм сортировки сравнениями выполняет [math]\Omega(n \log n)[/math] сравнений, где [math]n[/math] — число сортируемых элементов.
Доказательство:
[math]\triangleright[/math]
Пример дерева для алгоритма сортировки трех элементов.
Внутренний узел, помеченный как [math] i:j [/math], указывает сравнение между [math] a_{i} [/math] и [math] a_{j} [/math]. Лист, помеченный перестановкой [math] \left \langle \pi(1), \pi(2), \dots , \pi(n) \right \rangle [/math], указывает упорядочение [math] a_{\pi(1)} \leqslant a_{\pi(2)} \leqslant \dots \leqslant a_{\pi(n)} [/math].

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

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


Докажем, что двоичное дерево с не менее чем [math]n![/math] листьями имеет глубину [math]\Omega(n \log n)[/math]. Двоичное дерево высоты [math]h[/math] имеет не более чем [math]2^h[/math] листьев (доказывается индукцией по высоте). Значит, имеем неравенство [math]n! \leqslant l \leqslant 2^h[/math], где [math]l[/math] — количество листьев. Прологарифмировав его, получим:

[math] h \geqslant \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]

Следствие

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

Если алгоритм сортировки является рандомизированным, то для него справедливо, что нижняя граница матожидания времени работы для сортировки сравнениями [math]n[/math] элементов ровна [math] \Omega(n \log n) [/math]. Доказательство этой теоремы можно прочесть в «Алгоритмы: построение и анализ».

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_нижней_оценке_для_сортировки_сравнениями&oldid=55065»