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

Материал из Викиконспекты
Перейти к: навигация, поиск
(+ для рандомизированных алгоритмов)
Строка 14: Строка 14:
 
Пример дерева для алгоритма сортировки <tex>n = 3</tex> элементов:
 
Пример дерева для алгоритма сортировки <tex>n = 3</tex> элементов:
  
−
[[Файл:SortTree.png]]
+
[[Файл:SortTree.png|300px|center|thumb]]
  
  
−
Докажем, что двоичное дерево с <tex>n!</tex> листьями имеет глубину <tex>\Omega(n \log n)</tex>:
+
Докажем, что двоичное дерево с не менее чем <tex>n!</tex> листьями имеет глубину <tex>\Omega(n \log n)</tex>. Очевидно, что двоичное дерево высоты <tex>h</tex> имеет не более чем <tex>2^h</tex> листьев (легко доказать по-индукции). Значит, имеем неравенство <tex>n! \le l \le 2^h</tex>, где <tex>l</tex> {{---}} количество листьев. Прологарифмировав его, получим:
  
 
<tex> h \geq \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 \geq \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>
Строка 24: Строка 24:
 
}}
 
}}
  
−
Если алгоритм сортировки является рандомизированным, то для него справедливо, что нижняя граница матожидания времени работы для сортировки сравнениями <tex>n</tex> элементов ровна <tex> \Omega(n \log n) </tex>. Доказательство этой теоремы можно прочесть в Кормене.
+
Если алгоритм сортировки является рандомизированным, то для него справедливо, что нижняя граница матожидания времени работы для сортировки сравнениями <tex>n</tex> элементов ровна <tex> \Omega(n \log n) </tex>. Доказательство этой теоремы можно прочесть в «Алгоритмы: построение и анализ».
  
 
==Источники==
 
==Источники==

Версия 00:37, 13 мая 2012

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


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

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

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

Пример дерева для алгоритма сортировки [math]n = 3[/math] элементов:

SortTree.png


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

[math] h \geq \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]n[/math] элементов ровна [math] \Omega(n \log n) [/math]. Доказательство этой теоремы можно прочесть в «Алгоритмы: построение и анализ».

Источники

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