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

'''Сортировка сравнениями''' (англ. ''Comparison sort'') {{---}} алгоритм [[Сортировки | сортировки]], который совершает операции сравнения элементов, но никак не использует их внутреннюю структуру.

{{
Теорема
|about=о нижней оценке для сортировки сравнениями
|statement=В худшем случае любой алгоритм сортировки сравнениями выполняет <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), \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 \leqslant a_j</tex> и <tex>a_i > a_j</tex>), значит, каждый узел дерева имеет не более двух сыновей. Всего существует <tex>n!</tex> различных перестановок <tex>n</tex> элементов, значит, число листьев нашего дерева не менее <tex>n!</tex> (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).



Докажем, что двоичное дерево с не менее чем <tex>n!</tex> листьями имеет глубину <tex>\Omega(n \log n)</tex>. Легко показать, что двоичное дерево высоты <tex>h</tex> имеет не более чем <tex>2^h</tex> листьев. Значит, имеем неравенство <tex>n! \leqslant l \leqslant 2^h</tex>, где <tex>l</tex> {{---}} число листьев. Прологарифмировав его, получим:

<tex> h \geqslant \log_2 n! = \log_2 1 + \log_2 2 + \ldots + \log_2 n ></tex> <tex> \dfrac{n}{2} \log_2 (\dfrac{n}{2}) = \dfrac{n}{2}(\log_2 n - 1) = \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> для наихудшего случая из теоремы о нижней границе для сортировки сравнениями.
}}

{{Утверждение
|statement=Любая сортирующая сеть с $n$ нитями имеет размер $\Omega(n \log n)$.
|proof=Каждый компаратор реализует одно сравнение двух элементов.
Поэтому сортирующая сеть является алгоритмом сортировки, который основан на сравнениях, при чем количества компараторов и сравнений в этом алгоритме совпадают. Значит, их $\Omega(n \log n)$
}}

{{Утверждение
|statement=Любая сортирующая сеть с $n$ нитями имеет глубину $\Omega(\log n)$.
|proof=

На каждом слое может быть не более $\dfrac{n}{2}$ компараторов, так как внутри одного слоя гнезда компаратора крепятся к разным нитям, а их $n$.

Пусть $d$ {{---}} количество слоев этой сети. Тогда количество компараторов $k \leqslant \dfrac{n}{2} \cdot d$

Теорема утверждает, что количество сравнений этого алгоритма (то есть количество компараторов) $k = \Omega(n\log n)$.
Это означает, что найдется такая константа $c$, что $k \geqslant c \cdot n \log n$.
Таким образом $c \cdot n \log n \leqslant k \leqslant \dfrac{n}{2} \cdot d \Rightarrow c \cdot n \log n \leqslant \dfrac{n}{2}\cdot d \Rightarrow 2c\log n \leqslant d \Rightarrow d = \Omega(\log n)$
}}

{{Утверждение
|statement=Не существует алгоритма добавления элемента в упорядоченный массив с сохранением порядка, за истинное время $\mathcal{o}(\log n)$, где $n$ {{---}} количество элементов в массиве, 
|proof=Допустим, есть такой алгоритм. Тогда создадим пустой массив и будем последовательно добавлять в него элементы массива, который хотим отсортировать. В итоге на выходе алгоритма получим отсортированный массив.
Тогда сравнений будет $\mathcal{o}(\log 1 + \log 2 + \ldots + \log{(n-1)}) = \mathcal{o}(n\log n)$. Но теорема утверждает, что их должно быть $\Omega(n\log n)$.
}}

{{Утверждение
|statement=Не существует структуры данных, которая одновременно поддерживает добавление элементов и извлечение минимума за амортизированное время <tex> \mathcal{o}(\log n) </tex>. 
|proof=Если бы такая структура существовала, то с её помощью можно было бы отсортировать все элементы за амортизированное время <tex>\mathcal{o}(n \log{n})</tex> {{---}} добавить все элементы,
а затем извлечь минимальный <tex>n</tex> раз. Можно заметить, что теореме даётся оценка на истинную нижнюю границу, а в данном утверждении фигурирует амортизированное время.
Но этот факт не является проблемой, так как амортизированное время <tex> \mathcal{o}(\log n) </tex> на одну операцию в случае <tex> n </tex> операций даст суммарное истинное время <tex> \mathcal{o}(n \log n) </tex>.
}}

== См. также ==
* [[Сортирующие_сети]]
* [[Быстрая_сортировка]]
* [[Двоичная_куча]]

==Источники информации==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с
* [http://da.kalinin.ru/2011/lectures/20110902-1/linear-sort.pdf Андрей Калинин Сортировка за линейное время]
* [http://lectures.stargeo.ru/alg/algorithms.htm#_Toc308850829 Конспект по курсу "Алгоритмы и алгоритмические языки"] (доказательство теоремы через формулу Стирлинга).
* [https://www.lektorium.tv/lecture/13359 Лекториум "Алгоритмы сортировки"]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Сортировки на сравнениях]]