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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Теорема (о нижней оценке для сортировки сравнениями):
В худшем случае любой алгоритм сортировки сравнениями выполняет \Omega(n \log n) сравнений, где n — число сортируемых элементов.
Доказательство:
\triangleright
Пример дерева для алгоритма сортировки трех элементов.
Внутренний узел, помеченный как i:j, указывает сравнение между a_{i} и a_{j}. Лист, помеченный перестановкой \left \langle \pi(1), \pi(2), \ldots , \pi(n) \right \rangle, указывает упорядочение a_{\pi(1)} \leqslant a_{\pi(2)} \leqslant \ldots \leqslant a_{\pi(n)}.

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

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


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

h \geqslant \log_2 n! = \log_2 1 + \log_2 2 + \ldots + \log_2 n > \dfrac{n}{2} \log_2 \left(\dfrac{n}{2}\right) = \dfrac{n}{2}(\log_2 n - 1) = \Omega (n \log n)

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

[править] Следствия

Утверждение:
Пирамидальная сортировка и сортировка слиянием являются асимптотически оптимальными сортировками сравнением.
\triangleright
Верхние границы O(n \log n) времени работы пирамидальной сортировки и сортировки слиянием совпадают с нижней границей \Omega(n \log n) для наихудшего случая из теоремы о нижней границе для сортировки сравнениями.
\triangleleft
Утверждение:
Не существует структуры данных, которая одновременно поддерживает добавление элементов и извлечение минимума за амортизированное время O(1).
\triangleright
Если бы такая структура существовала, то с её помощью можно было бы отсортировать все элементы за амортизированное время O(n) — добавить все элементы, а затем извлечь минимальный n раз. Можно заметить, что теореме даётся оценка на истинную нижнюю границу, а в данном утверждении фигурирует амортизированное время. Но этот факт не является проблемой, так как амортизированное время O(1) на одну операцию в случае n операций даст суммарное истинное время O(n).
\triangleleft

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты