Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 12

т). Мы создаем массивы Е и В (" левый" и "правый'*) с длинами п1+ 1 и пз + 1 соответственно в строке 3; дополнительная ячейка в каждом массиве будут содержать ограничитель. Цикл Гог в строках 4 и 5 копирует подмассив А[р., д] в Г [1., п1), а цикл Гог в строках 6 и 7 копирует подмассив А[о + 1., т) в ГГ[! .. пз). Строки 8 и 9 помещают ограничители в последние ячейки Г и ГГ. Строки 10 — 17, проиллюстрированные на рис.2.3, выполняют т — р+ 1 базовый шаг, сохраняющий инвариант цикла. В начале каждой итерации цикла Гог в строках 12 — 17 подмассив А[р .. !с — Ц содержит /с — р наименьших элементов 1[1 ..

п1 + Ц Глава 2 Приступали к изучению и В[1 .. па+1] в отсортированном порядке. Кроме того, Г [т] и ВЦ являются наименьшими элементами соответствующих массивов, которые еще не были скопированы назад в А. Необходимо показать, что этот инвариант цикла соблюдается перед первой итерацией рассматриваемого цикла Гог в строках 12-17, что каждая итерация цикла его сохраняет и что с его помощью можно продемонстрировать корректность алгоритма, когда цикл заканчивает свою работу, Инициализации. Перед первой итерацией цикла к = р, так что подмассив А [р..тс — 1] пуст, Он содержит )е — р = О наименьших элементов массивов Х, и В, а поскольку Г = 7' = 1, элементы Ь [Г] и В Ц вЂ” наименьшие элементы массивов Г, и В, не сюпированные обратно в массив А. Сохранение. Чтобы убедиться, что инвариант цикла сохраняется после каждой итерации, сначала предположим, что Г [1] < Щ.

Тогда Г [т] — наименьший элемент, пока еще не скопированный в массив А. Поскольку в подмассиве А[р .. )б — 1] содержится к — р наименьших элементов, после юпирования в строке 14 Е[з] в А[к] в подмассиве А[р .. )с] будет содержаться lг — р+ 1 наименьших элементов. В результате увеличения параметра )с цикла Гог и значения переменной з' (строка 15), инвариант цикла восстанавливается перед следующей итерацией. Если же выполняется неравенство Г [з] > В[7], то в строках 16 и 17 выполняются соответствующие действия, в ходе которых также сохраняется инвариант цикла. Завершение.

Алгоритм завершается, когда lе = г + 1. В соответствии с инвариантом цикла подмассив А[р.. к — 1] (т.е. подмассив А[р.. г]) содержит lс — р = т — р+1 наименьших элементов массивов Г[1 .. пг+1] и В[1.. па+1] в отсортированном порядке. Суммарное юличество элементов в массивах Ь и В равно пт + пз + 2 = г — р+ 3. Все онн, кроме двух самых больших, сюпированы обратно в массив А, а два оставшихся элемента являются сигнальными. Чтобы убедиться, что время работы процедуры Мпксп равно 9(п), где и = г — р+ 1, заметим, что каждая из строк 1-3 и 8-11 выполняется за константное время; длительность циклов Гог в строках 4-7 равна 9(пг+ пз) = 9(п),б а в цикле Гог в строках 12 — 17 выполняются п итераций, на каждую из которых затрачивается константное время.

Теперь процедуру Меийп можно использовать в качестве подпрограммы в алгоритме сортировки слиянием. Процедура Мцксп-Бокт(А, р, г) выполняет сортировку элементов в подмассиве А[р..г]. Если справедливо неравенство р > г, то в этом подмассиве содержится не более одного элемента, и, таким образом, он является уже отсортированным.

В противном случае производится разбиение, ЯВ главе 3 будет показано, как формально интерпретируются уралнения с Э-обозначениями. )хааа 2. Иристуваеи киэуиеиию 57 э т )! ! (э )4 ! )и (1 (я) Э 5 (О Н( Ы (! (7) )э Ц А ... !' ) ! 2 ! 2 , '3 (, А э~~2$~~~!фЯ э 4 э а 5 ~ 7 1, ° ! л )1)22!Я~~~ 6 ! ! 7 (с) х ч ((! (! Ц (э !' !" э( (5 А ...

~1.'! и ~.2 ЯА )! 5;. б 1~~' ! " " -! 5 е т(Я' Дф~ 7;:,-:: я М~~Н~Р,:,;. - ( ! эо (! !' )! ы А ...: );" 2: э *' 3 ( А ( 5 ф~~!ф'~ (э) 5 !, и )! (э г! (4 (э (6 г! А ... ', ) ! 2 1 2 ) 3 ) 4 ! 5 !('б ) 7 ! э э (и) вательности длиной 2, затем — попарное объединение двухзлементных последовательностей в отсортированные последовательности длиной 4 и так до тех пор, пока не будут получены две последовательности, состоящие из и/2 элементов, которые объединяются в конечную отсортированную последовательность длиной т(.

2З.2. Анализ алгоритмов, основанных иа принципе "разделяй и властвуй" Когда алгоритм рекурсивно вызывает сам себя, зачастую время его работы можно описать с помощью рекурренаннвго уравнения 1или рекурренавносанн), которое выражает полное время, требующееся для решения всей задачи размером и, через время решения задач для меньших входных данных. Затем можно прибегнуть к соответствующему математическому аппарату для решения рекуррентности и получить границы производительности алгоритма.

Получение рекуррентного соотношения для времени работы алгоритма, основанного на принципе "разделяй и властвуй", базируется на трех этапах, соответствующих парадигме этого принципа. Как и ранее, обозначим через Т(п) время решения задачи, размер которой равен ц. Если размер задачи достаточно мал, свяжем, и < с для некоторой заранее известной константы с, то задача решается непосредственно в течение определенного константного времени, которое мы обозначим через сэ(1). Предположим, что наша задача делится на и подзадач, Рнс. 2З (продолжение).

(н) Массивы и индексы прн эавергпеннн пропедуры. В этот момент подмасснв А(9 .. 16! отсоргнроаан, а два ограничителя в Ь н )( яввяются едннстаеннымн элементами в этих массивах, которые не были скопированы в А. 5о 'тлеть й Ослаем Отсортнрованная последовательность ~ '1,.:,с 2'': ~" 2 .. '::3".,' 4'' .' 5 . т "6'" -'-'7'- ') Слияние ! 2 - '4'.::,";5";:,:-:,7' Слияние ~ 4.".. с ~ ~ /'-А ГЫ ф' (.~':~ ~Я );1'" .(з 1, ~2 ~ Я~ Исходная последовательность Рнс. 2.4.

Процесс сортнрован слняннем массива А = (б, 2, 4, 7, 1, 3, 2, 6). Длины псдлежмцнх слиянию стсортнрованных последовательностей возрастают в ходе работы ааторнтма. объем каждой из которых равен 1/Ь от объема исходной задачи. (В алгоритме сортировки методом слияния числа а и Ь были равны 2, однако нам предстоит ознакомиться со многими алгоритмами разбиения, в которых а ф Ь.) Для решения подзадачи размером и/Ь требуется время Т(п/Ь), а лля решения а таких подзадач требуется время аТ(п/Ь). Если разбиение задачи на вспомогательные подзадачи происходит за время Р(п), а объединение решений подзадач в решение исходной задачи — в течение времени С(п), то мы получим следующее рекуррентное соотношение: 9 (Ц, если п < с, аТ(п/Ь) + Р(п) + С(п) в противном случае .

В главе 4 рассмотрим методы решения рекуррентных уравнений такого вида. Анализ алгоритма сортировки слиянием Хотя псевдокод Микпи-Боит корректно работает для нечетного количества сортируемых элементов, анализ рекуррентного уравнения упрощается, если количество элементов в исходной задаче представляет собой степень двойки.

В этом случае на каждом шаге деления будут получены две подпоследовательности, размер которых точно равен и/2. В главе 4 будет показано, что это предположение не влияет на порядок роста, полученный в результате решения рекуррентного уравнения. Чтобы получить рекуррентное уравнение для верхней оценки времени работы Т(п) алгоритма, выполняющего сортировку и чисел методом слияния, будем рассуждать следующим образом. Сортировка одного элемента методом слияния Гланэ 2. Приступаем к изучению 59 выполняется за константное время. Если п ) 1, время работы распределяется следующим образом. Разйелсние.

В ходе разбиения определяется, где находится средина подмассива. Зта операция выполняется за константное время, поэтому В(а) = ту(1). Властвование. Рекурсивно решаются две подзадачи, размер каждой из которых составляет и/2. Время решения этих подзадач равно 2Т(п/2). Комбинирование. Как уже упоминалось, процедура МЕККЕ при работе с и-эле- ментным подмассивом выполняЕтся за время сэ(п), так что С(п) = 9(п). Складывая функции Р(п) и С(п) для анализа алгоритма сортировки слиянием, мы складываем функции, которые представляют собой сэ(п) и сэ(1).

Зта сумма является линейной функцией от и, т.е. сэ(п). Добавление ее к члену 2Т(п/2) из шага "Властвование" дает следующее рекуррентное соотношение для времени работы сортировки слиянием в наихудшем случае: с э(1), если п = 1, Т(п) = 2Т(п/2) + сэ(п), если и > 1 . (2.1) В главе 4 вы познакомитесь с теоремой, которую можно использовать для того, чтобы показать, что Т(п) представляет собой ту(п 1я и), где 1к и означает 1окз и. Поскольку логарифмическая функция растет медленнее любой линейной функции, для достаточно больших входных данных сортировка слиянием со временем работы ст(п 1й и) превзойдет в наихудшем случае сортировку вставкой, время работы которой равно ~Э(пз). Конечно, можно и без упомянутой теоремы интуитивно понять, почему решением рекуррентного соотношения (2.1) является выражение Т(п) = 9(п 1я и).

Давайте перепишем рекуррентное соотношение (2.1) в виде с , если п = 1, 2Т(п/2) + сп, если и ) 1, (2.2) зомаловероятна, чтобы одна и та же константа представлвла и время, необходимое для решения задачи, размер мпорый равен ц н приходящееся на один элемент время, в течение ноторопэ выполняютсв этапы разбиения и обьединення. Чтобы обойти эту проблему, достаточно предположизь, что с — максимальный нз перечисленных промежупюв времени. В таком случае мы получим верхнюю эрвницу времени работы алгоритма Если же в качестве с выбрать наименьший из всех перечисленных лромежупюв времени, то в реомьтате решения рекуррентнопэ стютношенил можно получить нижнюю зраницу времени работы алторитма.

Принимая во внимание, чю обе границы имени порядок п!й и, делаем вывод, что време работы влторнтма ведет себя, как 91п!ли). где константа с обозначает время, которое требуется для решения задачи, размер который равен 1, а также удельное (приходящееся на один элемент) время, требуемое для разделения и комбинирования.'с На рис. 2.5 показано решение рекуррентного соотношения (2.2).

Для удобства мы считаем, что п представляет собой точную степень 2. В части (а) рисунка бО Чаешь / Ословы Т(л) й т(лд Т(л/2) Т(л/4) Т(л/4) Т(л/4) Т(л/4) (а) (а) (б ) сл Г' слй й й сл/4 сл/4 сл/4 сл/4 ~ сл с с )ь сл с с с с с Всепк сл 1б л + сл (г) Рнщ 2.5. Построение дерева рекурсии для рекуррентного соотношения Т(п) = 2Т(п/2) + сп.

В части (а) показано время Т(п), которое постепенно раскрывается в частях (б)-(г), образуя дерево рекурсии. Полностью раскрьпое дерево в части (г) имеет 1б п + 1 уровней (т.е, его высота, как и указано, равна )й п), а вклад каидого уровня в стоимость равен сп. Таким образом, общая стоимость равна сп 1б п + сп, что представляет собой ст(п 1б п). 6! Глава 2. Приетуааеи к изучению показано время Т(п), которое в части (б) представлено в виде эквивалентного дерева, юторое представляет рекуррентное уравнение. Корнем дерева является член сп (стоимость на верхнем уровня рекурсии), и от него идут два поддерева, представляющие меньшие рекуррентности Т(п/2). В части (в) показан очередной шаг рекурсии, состоящий в раскрытии Т(п/2).