Алгоритмы - построение и анализ (1021735), страница 14
Текст из файла (страница 14)
Эти две стопки нужно обьединить в одну выходную, в которой карты будут рассортированы и также будут обращены рубашкой вверх. Основной шаг состоит в том, чтобы из двух младших карт выбрать самую младшую, извлечь ее из соответствующей стопки (при этом в данной стопке верхней откажется новая карта) и поместить в выходную стопку. Этот шаг повторяется до тех пор, пока в одной из входных стопок не кончатся карты, после чего оставшиеся в другой стопке карты нужно поместить в выходную стопку.
С вычислительной точки зрения выполнение каждого основного шага занимает одинаковые промежутки времени, так как все сводится к сравнению достоинства двух верхних карт. Поскольку необходимо выполнить, по крайней мере, и основных шагов, время работы процедуры слияния равно 9 (п). Описанная идея реализована в представленном ниже псевдокоде, однако в нем также есть дополнительное ухищрение, благодаря которому в ходе каждого основного шага не приходится проверять, является ли каждая из двух стопок пустой. Идея заключается в том, чтобы поместить в самый низ обеих объединяемых колод так называемую сигнальную карту особого достоинства, что позволяет упростить код.
Для обозначения сигнальной карты используется символ оо. Не существует карт, достоинство которых больше достоинства сигнальной карты. Процесс продолжается до тех пор, пока проверяемые карты в обеих стопках не окажутся сигнальными. Как только это произойдет, это будет означать, что все несигнальные карты уже помещены в выходную стопку. Поскольку заранее известно„что в выходной стопке должно содержаться ровно т — р+ 1 карта, выполнив такое количество основных шагов, можно остановиться: МЕКбЕ(А, р, о, т) 1 п1 — о — р+1 2 пз — т — о 3 Создаем массивы А[1..п1+ 1] н В[1..пэ + 1] Часть !.
Основы 4 !огз -1!оззз 5 з!о Цз] — А[р+ з — 1] 6 !ог 7' — 1 го пз 7 з1о Л[7'] — А[9+,у] 8 з" [зз! + 1] — оо 9 Л[ззя + 1] ~ — оо !О з — 1 !! 7' -1 !2 !ог !з — р го т !3 Йо ИЬ[з] < Л[7] !4 т!зеп А[!з] — Ь[з] !5 з~ — з+1 16 е!яе А[)з] — Л[Я !7 7 -7+1 Подробно опишем работу процедуры Мексн.
В строке 1 вычисляется длина пз подмассива А [р..д], а в строке 2 — длина пз подмассива А [д+ 1..г]. Далее в строке 3 создаются массивы Ь (" левый" — "!ей") и Л ("правый" — "г!8!з!"), длины которых равны пз + 1 и пз + 1 соответственно. В цикле !ог в строках 4 и 5 подмассив А [р..з7] копируется в массив Ь [1..ззз], а в цикле !ог в строках б и 7 подмассив А [д+ 1..г] копируется в массив Л [1..пя].
В строках 8 и 9 последним элементам массивов з' и Л присваиваются сигнальные значения. Как показано на рис. 2.3, в результате копирования и добавления сигнальных карт получаем массив з. с последовательностью чисел (2, 4, 5, 7, оо) и массив Л с последовательностью чисел (1,2,3,6,оо). Светло-серые ячейки массива А содержат конечные значения, а светло-серые ячейки массивов Е и Л вЂ” значения, которые еше только должны быть скопированы обратно в массив А. В светло-серых ячейках находятся исходные значения из подмасснва А [9..16] вместе с двумя сигнальными картами. В темно-серых ячейках массива А содержатся значения, которые будут заменены другими, а в темно-серых ячейках массивов Ь и Л— значения, уже скопированные обратно в массив А.
В частях рисунка а — з показано состояние массивов А, Ь и Л, а также соответствующие индексы lс, з и 7' перед каждой итерацией цикла в строках !2-17. В части и показано состояние массивов и индексов по завершении работы алгоритма. На данном этапе подмассив А [9..16] отсортировал, а два сигнальных значения в массивах Ь и Л вЂ” единственные элементы, оставшиеся в этих массивах и не скопированные в массив А. В строках 10-17, проиллюстрированных на рис. 2.3, выполняется г — р+ 1 основных шагов.
в ходе каждого из которых производятся манипуляции с инвариантом цикла, описанным ниже. Глава 2. Приступаем к изучению 75 Л фф~~~~~~4$~~,'~!-,:»~~Я ~~и[[ 2 3 4 5 !» 2 4 5 я! 2! ЯЩ.'» !» '„. ! яф 2 ! 354 !-1 3 фЯ Я 6»~: 3 ! 2 3 4 5 2 3 4 5 ., ЯЯ< [7 Я Я ~~~~Я» -] » 3 4 5 »,Т"! Рис. 2.3. Операции, выполняемые в строках 10 — 17 процедуры Маков(А, 9, 12, 16), когда в подмасснве А [9..16] содержится последовательность (2,4,5,7,1,2,3,6) Перед каждой итерацией цикла 1ог в строках 12-17, подмассив А [р..»с — Ц содержит »4 — р наименьших элементов массивов Е [1. л3 + 1] и В [1..пэ + 1] в отсортированном порядке. Кроме того, элементы Ь [4] и В [4] являются наименьшими элементами массивов Ь и Я, которые еще не скопированы в массив А. 8 9 !О »! !2 »3 Д »5 !Ь !! 4 [Я"' 2 3 4 5 2 3 4 2 3 4 ! 2 3 4 1 ' 7[ 3» Я " ''.
!»] 1 ! 1 к! 9 и !! »2 !3 !4 !5 »ь 2 3 4 5 ! 2 3 4 я Щь~~ф~'] л! 9 и»! 2 !3 и ь Ф 1! ' )91!фф»,'1, ' '[~[»»»[$Я !»! »! Д !, П;» »4 6»Ь !! 4 ! ![2!2 »' 2, 4 5 !» 3 ! ~ф» ! 3 9 !! !! !2 !3 »4 !.ЯЩ5 ! 1 ~ »2 8 9 Й !3! !2 !3 !415!4 !1 !,2! !» 4 3 4 5 ! 2 3 4 а" 2 ["-» я,; Я~» 76 Часть Е Основы Необходимо показать, что этот инвариант цикла соблюдается перед первой итерацией рассматриваемого цикла 1ог, что каждая итерация цикла не нарушает его, и что с его помощью удается продемонстрировать корректность алгоритма, когда цикл заканчивает свою работу. Инициализация.
Перед первой итерацией цикла 1с = р, поэтому подмассив А [р..1с — 1] пуст. Он содержит 1с — р = О наименьших элементов массивов Ь и Л. Поскольку г = 7' = 1, элементы Т, [1] н В[7] — наименьшие элементы массивов Т, и В, не скопированные обратно в массив А.
Сохранение. Чтобы убедиться, что инвариант цикла сохраняется после каждой итерации„сначала предположим, что Ь [1] ( тс [у]. Тогда Ь [з] — наименьший элемент, не скопированный в массив А. Поскольку в подмассиве А [р..1с — 1] содержится й-р наименьших элементов, после выполнения строки 14, в которой значение элемента Т, [з] присваивается элементу А [1с], в подмассиве А [р..1с] будет содержаться 1с — р+ 1 наименьший элемент. В результате увеличения параметра 1с цикла 1ог и значения переменной з (строка 15), инвариант цикла восстанавливается перед следующей итерацией.
Если же выполняется неравенство Ь [з] > А [7], то в строках 16 и 17 выполняются соответствующие действия, в ходе которых также сохраняется инвариант цикла. Завершение. Алгоритм завершается, когда й = т + 1. В соответствии с инвариантом цикла, подмассив А [р..й — 1] (т.е. подмассив А [р..т]) содержит й— — р = т — р+ 1 наименьших элементов массивов Ь [1..п1 + 1] и В [1..пз + 1] в отсортированном порядке.
Суммарное количество элементов в массивах Т н В равно пт + пз + 2 = т — р+ 3. Все они, кроме двух самых больших, скопированы обратно в массив А, а два оставшихся элемента являются сигнальными. Чтобы показать, что время работы процедуры Мексзе равно 9 (и), где п = т— — р+ 1, заметим, что каждая нз строк 1 — 3 и 8 — 11 выполняется в течение фиксированного времени; длительность циклов 1ог в строках 4 — 7 равна О (пз + пз) = = 9 (п),т а в цикле 1ог в строках 12 — 17 выполняется и итераций, на каждую из которых затрачивается фиксированное время.
Теперь процедуру МЕКОЕ можно использовать в качестве подпрограммы в алгоритме сортировки слиянием. процедура мекое Болт(А, р, т) выполняет сортировку элементов в подмассиве А [р..т]. Если справедливо неравенство р > т, то в этом подмассиве содержится не более одного элемента, и, таким образом, он отсортировал. В противном случае производится разбиение, в ходе которого В главе 3 будет показано, как формально интерпретируются уравнения с Э-обозначениями. Глава 2. Приступаем к изучению 77 Отсортированная последовательность )! 2 2 3 ' Е: 5- 6 2 3 ь .
/~.'лкьпвс"'Ь Исходная последовательность Рнс. 2.4. Процесс сортировки массива А = (5,2,4,7,1,3,2,6) методом сли- яния. Длины подлежащих объединению отсортированных подпоследователь- ностей возрастают по мере работы алгоритма вычисляется индекс д, разделяющий массив А [р..г] на два подмассива: А [р..д] с [и/2] элементами и А [д.ж] с [и/23 элементамиа. Чтобы отсортировать последовательность А = (А [1], А [2],..., А [тз]), вызывается процедура Мексе Зонт(А,1, 1епдгд [А]), где 1епдгй [А] = и.
На рис. 2.4 проиллюстрирована работа этой процедуры в восходящем направлении, если п — это степень двойки. В ходе работы алгоритма происходит попарное объединение одноэлементных последовательностей в отсортированные последовательности длины 2, затем — попарное обьединение двухэлементных последовательностей в отсортированные последовательности длины 4 и т.д., пока не будут "Выражение (х) обозначает наименьшее целое число, которое больше или равно х, а выражение [х) — наибольшее целое число, которое меньше или равно х. Эти обозначения вводятся в главе 3.
Чтобы убелиться в том, что в результате присваивания переменной о значения ((р+ г)/2) длины подмассивов А (р..о) и А [О + 1.х) получаются равными (и/2) и [и/2), достаточно проверить четыре возможных случая, в которых каждое из чисел р и г либо четное, либо нечетное. [л 7 /Слклнпе Ъ МЕКОЕ БОКТ(А, р, г) 1 11р(т 2 Феп д — [(р+ т)/2) 3 Мекке Яокт(А,р,д) Мекпе Бокт(А,д+1,т) 5 МЕКСЕ(А, р, д, г) Гл ч и ам /лХ /у 1 Часть 1. Основы 78 получены две последовательности, состоящие из и/2 элементов, которые объеди- няются в конечную отсортированную последовательность длины и.
2.3.2 Анализ алгоритмов, основанных на принципе "разделяй и властвуй" Если алгоритм рекурсивно обращается к самому себе, время его работы часто описывается с помощью рекуррентного уравнения, или рекуррентного соотношения, в котором полное время, требуемое для решения всей задачи с объемом ввода и, выражается через время решения вспомогательных подзадач. Затем данное рекуррентное уравнение решается с помощью определенных математических методов, и устанавливаются границы производительности алгоритма. Получение рекуррентного соотношения для времени работы алгоритма, основанного на принципе "разделяй и властвуй", базируется на трех этапах, соответствующих парадигме этого принципа.
Обозначим через Т (и) время решения задачи, размер которой равен и. Если размер задачи достаточно мал, скажем, и < с, где с — некоторая заранее известная константа, то задача решается непосредственно в течение определенного фиксированного времени, которое мы обозначим через О (1). Предположим, что наша задача делится на а подзадач, объем каждой из которых равен 1/Ь от объема исходной задачи. (В алгоритме сортировки методом слияния числа а и Ь были равны 2„ однако нам предстоит ознакомиться со многими алгоритмами разбиения, в которых а ~ Ь.) Если разбиение задачи на вспомогательные подзадачи происходит в течение времени Р (и), а объединение решений подзадач в решение исходной задачи — в течение времени С (и), то мы получим такое рекуррентное соотношение: 6 (1) прн и < с, Т(и) = аТ (и/Ь) + Р (и) + С (и) в противном случае. В главе 4 будет показано, как решаются рекуррентные соотношения такого вида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
