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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
|proof=Во-первых, будем считать целью нашего алгоритма определить исходную перестановку, после её определения сортировка сведется к нахождению обратной перестановки. Будем искать наихудший случай для алгоритма среди всех возможных перестановок чисел от 1 до <tex>n</tex>, таким образом у каждого сравнения всего два возможных исхода - <tex>a_i < a_j</tex> или <tex>a_i > a_j</tex>.
 
|proof=Во-первых, будем считать целью нашего алгоритма определить исходную перестановку, после её определения сортировка сведется к нахождению обратной перестановки. Будем искать наихудший случай для алгоритма среди всех возможных перестановок чисел от 1 до <tex>n</tex>, таким образом у каждого сравнения всего два возможных исхода - <tex>a_i < a_j</tex> или <tex>a_i > a_j</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)=O(n \log 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)=O(n \log n)</tex>

Версия 00:04, 8 июня 2011

В этой статье рассматриваются алгоритмы сортировки сравнением. В таких алгоритмах единственным действием с элементами массива является их сравнение. Значения самих элементов или иная информация о них не доступна.

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

Во-первых, будем считать целью нашего алгоритма определить исходную перестановку, после её определения сортировка сведется к нахождению обратной перестановки. Будем искать наихудший случай для алгоритма среди всех возможных перестановок чисел от 1 до [math]n[/math], таким образом у каждого сравнения всего два возможных исхода - [math]a_i \lt a_j[/math] или [math]a_i \gt a_j[/math].

Рассмотрим некоторое состояние нашего алгоритма. В этом состоянии уже известны результаты каких-то сравнений, и в зависимости от них делается следующее, после чего алгоритм переходит в одно из двух состояний. Кроме того, алгоритм может остановиться, если исходная перестановка будет однозначно установлена. Заметим, что этот процесс можно описать двоичным деревом, узлы которого будут соответствовать состояниям, листья - определенным входным перестановкам, а ребра - результатам сравнений.

Вот пример такого дерева для [math]n = 3[/math]:

DecisionTree.png

Заметим так же, что число листьев у этого дерева должно быть не меньше [math]n![/math], иначе одна из перестановок не сможет быть определена.

Число сравнений в наихудшем случае будет равно глубине этого дерева, поэтому осталось показать, что эта глубина есть [math]\Omega(n \log n)[/math]. Для этого заметим, что у двоичного дерева глубины [math]n[/math] листьев не больше [math]2^n[/math] (в случае полного двоичного дерева), т. е. у двоичного дерева с [math]n[/math] листьям глубина по крайней мере [math]\lceil \log_2 n \rceil[/math]. Осталось оценить [math]\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)=O(n \log n)[/math]

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

Источники

  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с