Изменения

Перейти к: навигация, поиск

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

61 байт убрано, 21:21, 7 мая 2012
Статься переписана, добавлены источники, категории, шаблон "определение"
В этой статье рассматриваются алгоритмы {{Определение|definition=Сортировка сравнениями {{---}} алгоритм сортировки сравнением. В таких алгоритмах единственным действием с элементами массива является их сравнение. Значения самих , который совершает операции сравнения элементов или иная информация о них , но никак не доступнаиспользует их внутреннюю структуру. }}
{{
Теорема
|about=о нижней оценке для сортировки сравнениями
|statement=В наихудшем худшем случае в ходе выполнения любого алгоритма любой алгоритм сортировки сравнением выполняется сравнениями выполняет <tex>\Omega(n \log n)</tex> сравнений, где <tex>n</tex> {{--- }} число сортируемых элементов массива. (Теорема справедлива и для рандомизированных алгоритмов сортировки, но в статье не приводится доказательство этого факта).
|proof=ВоЛюбому алгоритму сортировки сравнениями можно сопоставить дерево. В нем узлами являются операции сравнения элементов, ребрами {{-первых, будем считать целью нашего --}} переходы между состояниями алгоритма определить исходную перестановку, после её определения сортировка сведется к нахождению обратной а листьями {{---}} конечные перестановкиэлементов (соответствующие завершению алгоритма сортировки). Будем искать наихудший случай Необходимо доказать, что высота такого дерева для любого алгоритма среди всех возможных перестановок чисел от 1 до сортировки сравнениями не меньше чем <tex>O(n\log n)</tex>, таким образом у каждого сравнения всего два возможных исхода - где <tex>a_i < a_j</tex> или <tex>a_i > a_jn</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 = 3</tex>элементов:
[[Файл:DecisionTree.png]]
Заметим так же, что число листьев у этого дерева должно быть не меньше <tex>n!</tex>, иначе одна из перестановок не сможет быть определена.
Число сравнений в наихудшем случае будет равно глубине этого дерева, поэтому осталось показатьДокажем, что эта глубина есть <tex>\Omega(n \log n)</tex>. Для этого заметим, что у двоичного дерева глубины <tex>n</tex> листьев не больше <tex>2^n</tex> (в случае полного двоичного дерева), т. е. у двоичного дерева двоичное дерево с <tex>n</tex> листьям глубина по крайней мере <tex>\lceil \log_2 n \rceil</tex>. Осталось оценить <tex>\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> h = \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> сравнений, ч. т. д.
}}
==Источники==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 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 Конспект по курсу "Алгоритмы и алгоритмические языки"] (доказательство теоремы через формулу Стирлинга).
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
Qwerty787788
81
правка
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/22002»

Навигация