2 Алгоритмічні стратегії
2.1 Принцип «розділяй і володарюй»
Багато алгоритмів за своєю природою рекурсивні, розв’язуючи деяку задачу вони визивають самих себе для розв’язку її підзадач. Ідея методу «розділюй і володарюй» як раз і полягає у цьому. Спочатку задача розбивається на декілька задач меншого розміру. Потім ці задачі розв’язуються за допомогою рекурсивного виклику – або безпосередньо, якщо розмір задачі невеликий. Нарешті, розв’язки часткових задач комбінуються і отримують розв’язок задачі у цілому.
Як приклад, розглянемо задачу знаходження найбільшого (найменшого) елементу множини , яка вміщує елементів. Очевидний шлях пошуку найбільшого елементу полягає у тому, щоб шукати його як результат порівняння певного елементу з іншими і запам’ятовувати кожний раз більший із них. Наступна процедура Max находить найбільший елемент множини , зробивши порівнянь:
Max
1 n=length(S)
2 Вибираємо довільний елемент із множини S
3 max=S(1)
4 for i=2 to n
5 if x>max
6 then max=x
7 end if
8 end for
Аналогічно можна знайти найменший елемент із елементів, що залишитись, здійснивши порівнянь.
Таким чином, для знаходження найбільшого і найменшого елементів із множини необхідно виконати порівнянь.
Застосуємо до задачі знаходження найбільшого і найменшого елементів із множини принцип «розділюй і володарюй». Для цього множину розіб’ємо на дві підмножини і . Для простоти допустимо, що у кожній із підмножин є по елементи. Тоді описаний вище алгоритм знайшов би найменший і найбільший елементи у кожній із підмножин і . Найбільший і найменший елемент множини можна визначити провівши ще два порівняння найбільших і найменших елементів із множин і .
Отже, матимемо наступну процедуру:
procedure Max_Min(S):
n=length(S)
if n=2 then
нехай S={a,b}
return (Max(a,b), Min(a,b))
else
6. розбити на дві рівні підмножини і
виклик процедури MaxMin
5. (max1,min1)= MaxMin( )
6. (max2,min2)= MaxMin( )
7. return (Max(max1,max2), Min(min1,min2))
8 end if
Аналізуючи процедуру Max_Min можна зробити висновок, що порівняння елементів множити відбувається тільки на кроці 3, де порівнюються два елементи множини , із яких вона складається, і на кроці 7, де порівнюються max1,max2 та min1,min2. Очевидно, що (одне порівняння). Якщо , то - загальне число порівнянь отриманих у двох викликах процедури MaxMin (рядки 5 і 6), які працюють на множинах розміром , і ще два порівняння у рядку 7. Таким чином,
(2.1)
Знайдемо розв’язок рекурентного співвідношення (2.1) Нехай у (2.1) приймає довільне значення. Тоді
,
, .
Допустимо, що . Тоді
,
,
,
…………………….. .
Шляхом послідовної підстановки знаходимо, що
,
,
,
…………………………………………………………………………………….
Останній вираз подамо у такому вигляді:
.
Узагальнюючи отриманий результат для довільного , де - множина натуральних чисел, будемо мати
.
Допустимо, що . Тоді . Оскільки , то при
.
Перший доданок суми, яка є правою частиною останнього співвідношення - , а другий доданок – це геометрична прогресія, в якої перший член ; знаменник прогресії - , а кількість її членів дорівнює . Тому
.
Враховуючи значення , маємо
.
Таким чином, розв’язком рекурентних співвідношень (2.1) є функція
за умови, що , де - ціле додатне число.
Рисунок 2.1 дає наочне уявлення про те, що алгоритм, який побудований за стратегією «розділяй і володарюй», потребує меншого числа кроків ніж алгоритм, який здійснює пошук максимального і мінімального елементів шляхом перебору елементів масиву.
Ще одним прикладом застосування стратегії «володарюй і розділяй» може служити алгоритм сортування злиттям. Суть алгоритму у тому, що початкова множина елементів розбивається на підмножини , , …, . Кожна із множин , , у принципі, може вміщувати лише один елемент. У такому разі кожен із списків уже відсортований. Тепер задача полягає у тому, щоб певним чином списки , , …, злити.
Рисунок 2.1 – Порівняння ефективності двох алгоритмів
Нижче наведена процедура MergeSort, яка виконує сортування елементів множини злиттям.
1 procedure MergeSort
list список елементів, що підлягає сортуванню
first номер першого елементу у списку, що підлягає сортуванню
last номер останнього елементу у списку, що підлягає сортуванню
2 while first<last then
3 middle=(first+last)/2
4 MergeSort(list,first,middle)
5 MergeSort(list,middle+1,last)
6 MergeLists(list,first,middle,middle+1,last)
7 end while
Наведений алгоритм розбиває список на дві половини до тих пір, поки номер першого елемента куска менше останнього у ньому номера. Якщо у черговому куску указана умова не виконується, то це означає, що отримали список із одного елементу, який уже відсортований. Після двох викликів процедури MergeSort викликається процедура MergeLists, яка зливає два куски, у результаті отримаємо злитий список із двох елементів. На наступному кроці два списки, що вміщують по два елементи, зливаються в один довжиною чотири. Цей процес продовжується до тих пір, поки дві відсортовані половини загального списку зіллються в один. Таким чином, процедура MergeSort розбиває список на половину при русі по рекурсії вниз, а потім на зворотному шляху зливає відсортовані половинки списку.
Операцію по злиття списків в один виконує процедура MergeLists, яку розглянемо детальніше.
Нехай і два списки, які вже відсортовані у порядку зростання елементів. При злитті двох списків в один найменший елемент у загальному списку може бути першим або у списку або – у , а найбільший елемент в об’єднаному списку повинен бути останнім в одному із списків чи . Створимо новий список , який буде вміщувати елементи як списку , так і елементи - . Створювати список почнемо з того, що в нього перенесемо менший із двох елементів і . Якщо , наступним елементом може бути або . І перший і другий варіанти можливі оскільки нам невідомі співвідношення між величинами списку і списку . Для спрощення процесу злиття слід обзавестись двома індикаторами списків та і збільшувати той індикатор того списку, черговий елемент у якому виявиться меншим. Процедура MergeLists продовжує порівнювати елементи ще не переглянутих частин списків і та переміщувати менший із них у список . У певний момент елементи в одному із списків закінчаться. В другому списку залишаться елементи, які більші останнього елементу у списку .На закінчення, необхідно перемістити елементи, що залишились у кінець списку .
procedure MergeLists
list список елементів, що підлягає упорядкуванню
start1 початок списку
end1 кінець списку
start2 початок списку
end2 кінець списку
finalStart=start1
finalEnd=end2
indexP=1
while (start1<=end1) and (start2<=end2)
if list(start1)<list(start2)
result(indexP)=list(start1)
start1=start1+1
else
result(indexP)=list(start2)
start2=start2+1
end if
indexP= indexP=1
end while
перенос частини списку, що залишилась
if (start1<=end1) then
for i=start1 to end1
result(indexP)=list(i)
indexP=indexP+1
else
for i=start2 to end2
result(indexP)=list(i)
indexP=indexP+1
end for
end if
повернення результату у список
indexP=1
for i=finalStart1 to finalEnd
list(i)=result(indexP)
indexP=indexP+1
end for
Проаналізуємо отриманий алгоритм. Почнемо з процедури MergeLists. Допустимо, що всі елементи списку менші всіх елементів списку . Оскільки , (допускається, що кількість елементів у обох списках однакова), то процедура MergeLists розмістить всі елементи списку у список . Це означає, що процедура MergeLists виконає ( - кількість елементів списку ) операцій порівняння. У випадку протилежної ситуації, коли , процедура MergeLists перемістить всі елементи із списку у список , виконавши при цьому операцій порівняння.
Приклад 2.1. Розглянемо два списки і . Необхідно списки і злити в один список .
У випадку, що розглядається, відбувається порівняння елемента з елементом . Оскільки , то у список переміщається елемент . Знову порівнюємо елемент з елементом . Має місце співвідношення і елемент переміщаємо у список і т. д. Бачимо, для переміщення всіх елементів списку у список необхідно виконати чотири порівняння ( ).
Розглянемо тепер випадок, коли , але всі елементи списку менші ніж другий елемент списку . ( ) У такій ситуації процедура MergeLists перенесе елемент (1) у список , а потім відбудуться порівняння всіх елементів списку з другим елементом списку . Тому повне число порівнянь буде .
Приклад 2.2. Допустимо, що програмою sort сформовано два масиви і . Маємо випадок , коли , але всі елементи списку менші за ( ). Порівнюємо і . Оскільки , то елемент переміщаємо у список . Потім порівнюємо і . Маємо . Елемент переміщуємо у список і т. д. Неважко підрахувати, що після п’яти порівнянь всі елементи із списку будуть перемішені у список .
Тепер допустимо, що знаходиться між і , а знаходиться між і і т. д. У такому випадку перенос елементів із списків і у список відбувається почергово: спочатку із , потім із , потім знову із і знову із і т. д. до тих пір поки не вичерпаються всі елементи за винятком останнього у списку . Цей випадок є найгіршим: загальне число порівнянь буде - .
Проаналізуємо тепер процедуру MergeSort, яка викликається до тих пір поки first<last. Виконання останньої умови приводить до розбиття загального списку на дві половини, тобто кожний із списків і буде мати по елементи. Це означає, що у найгіршому випадку процедура MergeLists здійснить порівнянь. На виконання операцій сортування у списках і процедура MergeSort затратить операцій. Це означає, що у найгіршому випадку загальне число операцій (складність алгоритму) буде таким:
. (2.2)
Якщо список вміщує тільки один елемент, по він уже відсортований і процедура MergeLists не здійснює порівняння. Тому .
Розв’яжемо рекурентне співвідношення (2.2). Нехай у виразі (2.2) аргумент приймає будь-яке ціле значення , яке , тобто
(2.3)
Тоді у відповідності з (2.3) матимемо при
,
,
,
,
…………………………. .
Здійснюючи послідовну підстановку отриманих значень у вираз (2.2) отримаємо
,
,
,
. (2.4)
Процес підстановки можна продовжувати до досягання у правій частині отриманих послідовностей (2.4) .
Аналіз послідовності (2.4) показує, що , тобто коефіцієнт при співпадає з показником степені числа, яке є знаменником аргументу . Крім того .
Таким чином, маємо
.
Проведений аналіз показав, що при поділі списку кожний раз на половину . Звідси випливає, що . Оскільки , то
. (2.5)
Сума у формулі (2.5) є геометричною прогресією, знаменник якої . Тому
.
Оскільки і , то
.
Таким чином,
.
Це означає, що і сортування злиттям є значно ефективнішою за процедуру сортування вставками, де .