Теорема о нижней оценке для сортировки сравнениями — различия между версиями
Sokolova (обсуждение | вклад) |
Sokolova (обсуждение | вклад) |
||
Строка 10: | Строка 10: | ||
Ограничимся рассмотрением сортировки перестановок <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>.]] | <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>.]] | ||
Версия 21:58, 12 июня 2016
Сортировка сравнениями — алгоритм сортировки, который совершает операции сравнения элементов, но никак не использует их внутреннюю структуру.
Теорема (о нижней оценке для сортировки сравнениями): |
В худшем случае любой алгоритм сортировки сравнениями выполняет сравнений, где — число сортируемых элементов. |
Доказательство: |
Любому алгоритму сортировки сравнениями можно сопоставить дерево. В нем узлам соответствуют операции сравнения элементов, ребрам — переходы между состояниями алгоритма, а листьям — конечные перестановки элементов (соответствующие завершению алгоритма сортировки). Необходимо доказать, что высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем , где — количество элементов.Ограничимся рассмотрением сортировки перестановок элементов. При сравнении некоторых двух из них, существует два возможных исхода ( и ), значит, каждый узел дерева имеет не более двух сыновей. Всего существует различных перестановок элементов, значит, число листьев нашего дерева не менее (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).
Итак, для любого алгоритма сортировки сравнениями, существует такая перестановка, на которой он выполнит сравнений, ч. т. д. |
Если алгоритм сортировки является рандомизированным, то для него справедливо, что нижняя граница матожидания времени работы для сортировки сравнениями
элементов ровна . Доказательство этой теоремы можно прочесть в «Алгоритмы: построение и анализ».Источники
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с
- Андрей Калинин Сортировка за линейное время
- Конспект по курсу "Алгоритмы и алгоритмические языки" (доказательство теоремы через формулу Стирлинга).