13. Временная сложность сортировки с помощью сравнений.

 

            Если о ключах сортируемой последовательности ничего не известно или если максимальный ключ во много раз больше, чем количество сортируемых элементов n, то метод МАТСОРТ для упорядочения такой последовательности не годится. В этом случае последовательность можно отсортировать только с помощью  сравнения ее элементов.

            Покажем, что минимальная сложность алгоритмов сортировки с помощью сравнений Tmin(n)=O(n). Для этого составим неориентированный граф, определенный на множестве n элементов последовательности отношением: “элемент i связан с элементом j тогда и только тогда, когда они непосредственно сравниваются в ходе сортировки”. Если последовательность отсортирована, то этот граф обязательно будет связным. Как известно, связный неориентированный граф с минимальным количеством ребер является деревом. В соответствии со свойством дерева количество ребер в нем на единицу меньше количества вершин, т.е. равно n-1. Значит, в ходе сортировки должно быть выполнено, как минимум, n-1 сравнение, что и определяет минимальную сложность Tmin(n)=O(n).

            Покажем теперь, что максимальная сложность алгоритмов сортировки с помощью сравнений не меньше Tmax(n)=O(n log(n)). Для этого составим полное дерево решений, упорядочивающее последовательность из n элементов. На рис. 3.2 представлено такое дерево для n=3 элементов.

     Рис. 3.2. Полное дерево решений, упорядочивающее последовательность из 3 элементов.

 

            Так как результатом упорядочения последовательности из n элементов может оказаться любая из n! перестановок входной последовательности, то в дереве решений будет по крайней мере n! концевых вершин.

            В §8 главы I было доказано, что если бинарное дерево с максимальным количеством вершин имеет n! концевых вершин, то его высоту m можно найти по формуле (1.1):

 m=log2(n!).

Поскольку полное дерево решений не обязательно содержит максимальное количество вершин, то будет справедливо неравенство:

m>=log2(n!).

А так как именно высота m определяет максимальную сложность этого алгоритма, то

T(n)>=log2 (n!).

Воспользовавшись формулой Стирлинга

n! примерно= (n/e)^n,

которая выполняется при достаточно больших n, получим оценку для максимальной сложности:

T(n) >= (log2 ((n/e)n)=(n(log2 n-log2 e))=O(n log2 n)).

 

            Нижняя граница максимальной сложности позволяет судить об эффективности алгоритма сортировки с помощью сравнений: если Tmax(n) большего порядка, чем nlog(n) (например, Tmax(n)=O(n2)), то алгоритм нельзя признать эффективным, если же Tmax(n)=O(nlog(n)), то этот алгоритм годится для использования в практической деятельности.