Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 15
Текст из файла (страница 15)
В темно-серых ячейках массива А содержатся значения, которые будут заменены другими, а в темно-серых ячейках массивов Ь и Л— значения, уже скопированные обратно в массив А. В частях рисунка а — з показано состояние массивов А, Ь и Л, а также соответствующие индексы lс, з и 7' перед каждой итерацией цикла в строках !2-17. В части и показано состояние массивов и индексов по завершении работы алгоритма.
На данном этапе подмассив А [9..16] отсортировал, а два сигнальных значения в массивах Ь и Л вЂ” единственные элементы, оставшиеся в этих массивах и не скопированные в массив А. В строках 10-17, проиллюстрированных на рис. 2.3, выполняется г — р+ 1 основных шагов. в ходе каждого из которых производятся манипуляции с инвариантом цикла, описанным ниже. Глава 2. Приступаем к изучению 75 Л фф~~ф~4$~~,'~!»4~~$ ~~и[[ 2 3 4 5 !» 2 4 5 я! л ЯЩ.'» !» '„. ! яЯ 2 ! 334 !-1 3 фЯ Я 6»~:1 ! 2 3 4 5 2 3 4 5 ., ЯЯ< [7 Я Я ~~~~Я 4 -] !,Т"! Рис. 2.3.
Операции, выполняемые в строках 10 — 17 процедуры Маков(А, 9, 12, 16), когда в подмасснве А [9..16] содержится последовательность (2,4,5,7,1,2,3,6) Перед каждой итерацией цикла 1ог в строках 12-17, подмассив А [р..24 — Ц содержит 24 — р наименьших элементов массивов Е [1. л2 + 1] и В [1..пэ + 1] в отсортированном порядке. Кроме того, элементы Ь [4] и В [4] являются наименьшими элементами массивов Ь и Я, которые еще не скопированы в массив А. 8 а !О »! !2 »3 Д !5 !Ь !! 4 [Я"' 2 3 4 5 ! 2 3 4 2 3 4 ! 2 3 4 1 ' 7[ 3» Я " ''. !»] 1 ! 1 к! 4 И !! !2 !3 !4 !5 !Ь 2 3 4 5 ! 2 3 4 я Щь~~ф~'] л! ! , ')5!$$2,"..,: !»! »! Д !, П;» !4 6»Ь !! 4 ! ![2!2 »' 2, 4 5 !» 3 ! ~ф4 ! 5 Л !! !! !2 !3 »4 !.ЯЩ5 ! ~ ~ »2 8 9 !33 !3! !2 !3 !4 15 !4 !1 !,2! !» 4 3 4 5 ! 2 3 4 а" 2 ["-! я,; ЯЯ:3 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 будет показано, как решаются рекуррентные соотношения такого вида. Анализ алгоритма сортировки слиянием Псевдокод Мнкон Бокт корректно работает для произвольного (в том числе и нечетного) количества сортируемых элементов. Однако если количество элементов в исходной задаче равно степени двойки, то анализ рекуррентного уравнения упрощается. В этом случае на каждом шаге деления будут получены две подпоследовательности, размер которых точно равен и/2. В главе 4 будет показано, что это предположение не влияет на порядок роста, полученный в результате решения рекуррентного уравнения.
Чтобы получить рекуррентное уравнение для верхней оценки времени работы Т (и) алгоритма, выполняющего сортировку и чисел методом слияния, будем Глава 2. Приступаем к изучению 79 рассуждать следующим образом. Сортировка одного элемента методом слияния длится в течение фиксированного времени. Если и > 1, время работы распреде- ляется таким образом. Разбиение.
В ходе разбиения определяется, где находится средина подмассива. Эта операция длится фиксированное время, поэтому Р (п) = 0 (1). Покорение. Рекурсивно решаются две подзадачи, объем каждой из которых составляет гз/2. Время решения этих подзадач равно 2Т (гз/2). Комбинирование.
Как уже упоминалось, процедура Мбкгзб в п-элементном подмассиве выполняется в течение времени 9 (гт), поэтому С (и) = с1 (и). Сложив функции Р (гг) и С (и), получим сумму величин О (и) и О (1), которая является линейной функцией от и, те. 0 (и). Прибавляя к этой величине слагаемое 2Т (гг/2), соответствующее этапу "покорения*'„получим рекуррентное соотношение для времени работы Т (гь) алгоритма сортировки по методу слияния в наихудшем случае: 0 (1) при гь = 1, 2Т(гг/2) + 0(гг) при гг > 1. (2.1) В главе 4 мы ознакомимся с теоремой, с помощью которой можно показать, что величина Т (гг) представляет собой 6 (гз 1я и), где 1к п обозначает 1кз и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
