1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 22
Текст из файла (страница 22)
Выход, Элементы массива А, расположенные в порядке неубывания. Метод. Применяется процедура ПОСТРСОРТДЕРЕВА, т. е. алгоритм З.З. Наш алгоритм выглядит так: Ьеп)п ПОСТРСОРТДЕРЕВА; 1ог( — л а1ер — ! пи(112 до Ьей(п переставить А[1! я Аи; ПЕРЕСЫПКА(1, 1 — 1) епд епд з.а Быстгсоет Теорема 3.6. Алгоритм 3.4 упорядочивает последовательность из и элементов за время 0 (и ! ой и). Д о к а з а т е л ь с т в о, Корректность алгоритма доказывается индукцией по числу выполнений основного цикла, которое обозначим через т.
Предположение индукции состоит в том, что после т итераций список А[п — т+1), ..., А[п! содержит т наибольших элементов, расположенных в порядке неубывания, а список А[1[,..., А[п — т) образует сортирующее дерево. Летали доказательства оставляем в качестве упражнения. Время выполнения процедуры ПЕРЕСЫПКА(1, !) есть 0(1ой 1). Следовательно, алгоритм 3.4 имеет сложность 0(п!ой и). С[ Следствие. Алгоритм Сортдеревам имеет временную сложность Ос(п 1оя и).
5.5. ЕЫСТРСОРТ вЂ” УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ 0(п!ойп) До сих пор мы рассматривали поведение сортирующих алгоритмов только в худшем случае. Для многих приложений более реалистичной мерой временной сложности является усредненное время работы. В случае сортировки с помощью деревьев решений мы видим, что никакой сортирующий алгоритм не может иметь среднюю временную сложность, существенно меньшую п [ой и.
Однако известны алгоритмы сортировки, которые работают в худшем случае сп' времени, где с — некоторая постоянная, но среднее время работы которых относит их к лучшим алгоритмам сортировки. Примером такого алгоритма служит алгоритм Быстрсорт, рассматриваемый в этом разделе. Чтобы можно было рассуждать о среднем времени работы алгоритма, мы должны договориться о вероятностном распределении входов. Для сортировки естественно допустить, что мы и сделаем, что любая перестановка упорядочиваемой последовательности равновероятна в качестве входа. При таком допущении уже можно оценить снизу среднее число сравнений, необходимых для упорядочения последовательности из и элементов.
Общий метод состоит в том, чтобы поставить в соответствие каждому листу о дерева решений вероятность быть достигнутым при данном входе. Зная распределение вероятностей на входах, можно найти вероятности, поставленные в соответствие листьям.
Таким образом, можно определить среднее число сравнений, производимых данным алгоритмом сортировки, если вычислить сумму ~ р,йи взятую по всем листьям дерева решений данного алгоритма, в которой р; — вероятность достижения 1-го листа, а й; — его глубина. Это число называется средней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы 3.4. 4Н гл. з. соэтиэовкл и поэядковыв стлтистики Теорема 3.7.
В предположении, что все перестановки и-эле- ментной последовательности появляются на входе с равными вероят- ностями, любое дерево решений, упорядочивающее последователь- ность из и элементов, имеет среднюю глубину не менее 1оя п!. Д о к а з а тел ь с т в о. Обозначим через 0(Т) сумму глубин листьев двоичного дерева Т. Пусть 0 (Т) — ее иаимеиьшее значение, взятое по всем двоичным деревьям Т с т листьями. Покажем иидук- цией по т, что 0(т))т!ой т. Базис, т. е. случай т=1, тривиален.
Допустим, что предположе- иие индукции верно для всех значений т, меньших А. Рассмотрим дерево решений Т с й листьями. Оио состоит из корня с левым подде- ревом Т; с / листьями и правым поддеревом Т„, с й — 1 листьями при некотором /, 1я '1<1. Ясио„что 0 (Т) = 1+ 0 (Т,) + (й — 1) + 0 (Т„,), Поэтому наименьшее значение 0(Т) дается равенством 0 (й) = М1Х рг+ 0 (1) + 0 (й — 1)1. (3.1) ~<с<ь Учитывая предположение индукции, получаем отсюда 0(й)) й+ М111 !1!ой(+(й- !) 1од(/г — 1)1.
(3.2) 1<1<э Легко показать, что этот минимум достигается при (=й/2. Следовательио, 32 ой Таким образом, 0 (т))т 1ой т для всех т- 1. Теперь мы утверждаем, что дерево решений Т, упорядочивающее и случайных элементов, имеет ие меньше и! листьев. Более того, в точности п1 листьев появляются с вероятностью 1/п1 каждый, а остальные — с вероятностью О.
Не измеияя средней глубины дерева Т можно удалить из него все узлы, которые являются предками только листьев вероятности О. Тогда останется дерево Т' с и! листьями, каждый из которых достигается с вероятностью 1/и!. Так как 0(Т'))п1 1оя п1, то средняя глубина дерева Т' (а значит, и Т) ие меньше (1/п1) п1 1оя п1=1оя п1. П Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сп 1ояп сравнений для некоторой постоянной с)О.
Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией сп!ойп для некоторой постоянной с (как и у всякой сортировки с помощью сравнений), ио составляет лишь часп за зыстосоРТ ргоседцге БЫСТРСОРТ(5): 1. !! 5 содержит не больше одного элемента 1Ьеп ге!цгп 5 е!зе Ьед(п 2. выбрать произвольный элемент а из 5; 3. пусть 5„5, и 5,— последовательности элементов из 5, соответственно меньших, равных и больших а; 4.
ге!игп (БЫСТРСОРТ(5,), затем 5„затем БЫСТРСОРТ (5,)) епд Рис. 3.7. Программа Быстрсорт, времени работы других известных алгоритмов при их реализации на большинстве существующих машин. В худшем случае Быстрсорт имеет квадратичное время работы, но для многих приложений это не существенно. Алгоритм 3.5. Быстрсорт Вход. Последовательность 5 из и элементов а„а„..., а„. Выход.
Элементы последовательности 5, расположенные по порядку. Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове БЫСТРСОРТ(5). П Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из и элементов за среднее время О (и 1од и). Д о к а з а т е л ь с т в о.
Корректность алгоритма 3.5 доказывается прямой нндукцией по длине последовательности 5. Чтобы проще было анализировать время работы, допустим, что все элементы в 5 различны. Это допущение максимизирует размеры последовательностей 5, и 5„которые строятся в строке 3, и тем самым макснмизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (и) — среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из л элементов. Ясно, что Т(0)=Т(1)=Ь для некоторой постоянной Ь. Допустим, что элемент а, выбираемый в строке 2, является бм наименьшим элементом среди и элементов последовательности 5. Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время Т(! — 1) и Т(п — !) соответственно. Так как ! равновероятно принимает любое значение между 1 и п, а итоговое построение последовательности БЫСТРСОРТ(5) очевидно занимает !13 гл.
з. согтивовкл и погядковыв стлтистики время сп для некоторой постоянной с, то л Т(п)(сл-1- — ~~ ~(Т(1 — 1)+Т(л — 1)1 для л)2. (3.3) 1=1 Алгебраические преобразования в (3.3) приводят к неравенству л — 1 Т(л) (сл+ — ~Ч' Т(1). (3.4) " ог О Покажем, что при л)2 справедливо неравенство Т(п)(пп 1п п, где п=2с+2Ь и Ь=Т(6)=Т(1). Для базиса (п=2) неравенство Т(2)«=2с+2Ь непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в виде л-1 Т (п) (~ сл+ — + — ~' й1 1п1.
(3.5) Так как функция 1 1п 1' вогнута, легко показать, что л-1 л' !пл л' 1!п с ( х 1п х о(х ( — — —. 1=1 (3.6) Подставляя (3.6) в (3.5), получаем 4Ь лл Т(п) (сп+ — +йл!пп — —. л 2 ' (3.7) Поскольку п)2 и й=2с+2Ь, то сл+4 Ыл«-Ьл/2. Таким образом, неравенство Т(л)(йл 1п л следует из (3.7). С! Рассмотрим две детали, важные для практической реализации алгоритма. Первая — способ "произвольного" выбора элемента а в строке 2 процедуры БЫСТРСОРТ. При реализации этого оператора может возникнуть искушение встать на простой путь, а именно всегда выбирать, скажем, первый элемент последовательности 5. Подобный выбор мог бы оказаться причиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из (3.3). Последовательность, к которой применяется подпрограмма сортировки, часто бывает уже лкак-тол рассортирована„так что первый элемент мал с вероятностью выше средней.
Читатель может проверить, что в крайнем случае, когда БЫСТРСОРТ начинает работу на уже упорядоченной последовательности без повторений, а в качестве элемента а всегда выбирается первый элемент из 3, в последовательности 5 всегда будет на один элемент меньше, чем в той, из которой она строится. В этом случае БЫСТРСОРТ требует квадратичного числа шагов. З.з.
ныстисОРТ Лучшей техникой для выбора разбивающего элемента в строке 2 было бы использование генератора случайных чисел для порождения целого числа т', 1(1()5) '), и выбора затем тпго элемента из 5 в качестве а. Более простой подход — произвести выборку элементов нз 5, а затем взять ее медиану в качестве разбивающего элемента. Например, в качестве разбивающего элемента можно было бы взять медиану выборки, состоящей из первого, среднего и последнего элементов последовательности 5. Вторая деталь — как эффективно разбить 5 на три последовательности 5„5, и 5,? Можно [и желательно) иметь в массиве А все и исходных элементов.
Так как процедура БЫСТРСОРТ вызывает себя рекурсивно, ее аргумент 5 всегда будет находиться в последовательных компонентах массива, скажем А[)], А[)".+1),... ..., А[1) для некоторых г и 1, 1()(1(п. Выбрав "произвольный" элемент а, можно устроить разбиение последовательности 5 на этом же месте, Иными словами, можно расположить 5, в компонентах А[1), А[)+1),..., А[й)„а 5, [) 5е — в А[Ь+1), А[и+2),..., А)1) при некотором Ь, [()т(1. Затем можно, если нужно, расщепить 5, [) 5„но обычно эффективнее просто рекурсивно вызвать БЫСТР- СОРТ на 5, и 5, [) 5„если оба этих множества не пусты. По-видимому, самый легкий способ разбить 5 на том же месте— это использовать два указателя иа массив, назовем их 1 и 1.
Вначале Ьея[п 1. 2. 3. тчй|1е 1(1 бо Ьед1п 4. теИ!е Аи.=за и 1 и) до 1 — 1 — 1; 8. тоЫ!е Аи ( а и т'(1 до 1 — 1+ 1; 6. И 1 < 1 1Ьеп Ьей)п 7. переставить А[1) и АЦ; 8. Š— 1+1; 9. ! -! — 1 епт[ епс[ епт[ Рис. 3.8. Разбиение 5 на 5, и 5,[)5з на месте их расположения. т) Через 15[ обозначена алина послелоаательностн 5. ГЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
