Рубрики

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

Проблему сортировки можно рассматривать следующим образом.

Ввод: последовательность из n чисел < a 1 , a 2 ,. , , , п >.
Вывод: перестановка (переупорядочение) < a ' 1 , a ' 2 ,. , , , a ' n > входной последовательности, такой что a ' 1 a ' 2 … ..' n .

Алгоритм сортировки основан на сравнении, если он использует операторы сравнения, чтобы найти порядок между двумя числами. Сорта сравнения можно рассматривать абстрактно в терминах деревьев решений. Дерево решений — это полное двоичное дерево, которое представляет сравнения между элементами, которые выполняются определенным алгоритмом сортировки, работающим с входом заданного размера. Выполнение алгоритма сортировки соответствует трассировке пути от корня дерева решений до листа. На каждом внутреннем узле проводится сравнение a i a j . Затем левое поддерево диктует последующие сравнения для a i a j , а правое поддерево диктует последующие сравнения для a i > a j . Когда мы подходим к листу, алгоритм сортировки установил порядок. Таким образом, мы можем сказать следующее о дереве решений.

1) Каждый из п ! перестановки на n элементах должны появляться в качестве одного из листьев дерева решений для правильной сортировки алгоритмом сортировки.

2) Пусть x будет максимальным числом сравнений в алгоритме сортировки. Максимальная высота дерева решений будет х. Дерево с максимальной высотой х имеет не более 2 ^ х листьев.

Объединив два приведенных выше факта, мы получим следующее соотношение.

  
      n!  <= 2^x

 Taking Log on both sides.
      log2(n!)  <= x

 Since log2(n!)  = Θ(nLogn),  we can say
      x = Ω(nLog2n)

Следовательно, любой алгоритм сортировки, основанный на сравнении, должен выполнить как минимум nLog 2 n сравнений для сортировки входного массива, а сортировка по типу Heaps и сортировка слиянием являются асимптотически оптимальными сортировками сравнения.

Ссылки:
Введение в алгоритмы, Томас Х. Кормен, Чарльз Э. Лизерсон, Рональд Л. Ривест и Клиффорд Стейн

Рекомендуемые посты:

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

0.00 (0%) 0 votes