Главная » Java, Структуры данных и алгоритмы » Нижняя граница сравнительной сортировки

0

До настоящего момента рассмотрено несколько методов с различным временем выполнения в последовательности из п элементов, в том числе в этой главе сортировка слиянием и быстрая сортировка, а также пирамидальная сортировка, описанная в п. 7.3.4. Естественно возникает вопрос о возможности проведения сортировки за время, меньшее 0(п log п).

Докажем, что при использовании в качестве основы алгоритма сортировки операций сравнения двух элементов время такой сравнительной сортировки в крайнем случае будет Q.(n log п) (вспомните понятие QQ из п. 3.6.2). Для определения затрат времени на сравнительную сортировку будем принимать во внимание только сравнения, выполняемые алгоритмом сортировки. Поскольку требуется определить нижнюю границу, этого будет вполне достаточно.

Предположим, имеется последовательность S = (xq, х\, хп _ \), которую следует упорядочить. Допустим, что все элементы в S уникальны (это не ограничение, поскольку определяется нижняя граница). Каждый раз при сравнении двух элементов х/ и Xj (то есть алгоритм сортировки спрашивает «х\ < х/?») имеются два варианта ответа: «да» и «нет». По результату этого сравнения алгоритм сортировки может выполнить несколько своих внутренних вычислений (здесь не учитываются) и перейти к следующему сравнению двух других элементов из S, в результате чего также могут быть только два варианта ответа. Исходя из этого, представим алгоритм сравнительной сортировки с помощью дерева решений Г (вспомните пример 6.4). Это означает, что каждый составной узел v дерева Гсоот- ветствует сравнению, а соединительные линии из v’ к его дочерним элементам — результатам -сравнения (утвердительный или отрицательный ответ) (см. рис. 10.15).

Рис. 10.15. Отображение нижней границы сравнительной сортировки

Важно заметить, что гипотетический алгоритм сортировки в принципе может ничего не знать о дереве Т. Дерево Т просто представляет все возможные последовательности сравнений, которые осуществляет данный алгоритм, начиная с первого сравнения (соответствующего корню) и заканчивая последним (соответствующим родительскому элементу простого узла).

Любое изначальное упорядочение или перестановка элементов в S может заставить этот гипотетический алгоритм выполнить серию сравнений по ходу движения от корня к некоторому простому узлу. В таком случае свяжем с каждым узлом v дерева Г серию перестановок в S, в результате которых алгоритм сортировки заканчивается в v. Наиболее важным

наблюдением в поиске нижнего предела является то, что каждый простой узел v в дереве Г может представлять последовательность сравнений для максимум одной перестановки. Доказательство такого утверждения выглядит просто: если две разные перестановки Р\ и Р2 в S ассоциируются с одним и тем же простым узлом, то имеются как минимум два объекта х, и Xj, где х, расположен перед Xj в Pj, но х, следует за xj в Р2. Таким образом, в результате получим такой порядок, при котором х, и ху располагаются друг перед другом. Но наличие такого порядка в Р\ и Р2 означает возможность «обмануть» алгоритм, то есть расположить х, и Xj в неверном порядке. А поскольку в верном алгоритме сортировки это недопустимо, то каждый простой узел должен содержать только одну перестановку. Воспользуемся этим свойством дерева решений, представляющего алгоритм сортировки, для подтверждения следующего.

Утверждение 10.6. Время выполнения любого сравнительного алгоритма сортировки «-элементной последовательности в наихудшем случае составляет Q(n log п). ,

Доказательство. Время выполнения алгоритма сравнительной сортировки должно быть больше или равно высоте соответствующего ему дерева решений Г (рис. 10.15). Согласно вышеприведенному утверждению, в каждом простом узле дерева Т осуществляется одна перестановка в последовательности S. Более того, результат такой перестановки должен отображаться в новом простом узле дерева Т. Количество перестановок п объектов будет равно п! = п(п -1 ){п – 2)… 2 • 1. Таким образом, в Т будет как минимум п\ простых узлов. Согласно утверждению 6.10, высота Тсоставляет как минимум log(«!). Это сразу же доказывает требуемое, так как П\ содержит как минимум я/2 выражений, больших или равных я/2. Следовательно

 

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии