«Розділяй і володарюй» — це алгоритмічний шаблон. В алгоритмічних методах проект полягає в тому, щоб взяти суперечку про величезний вхід, розбити вхідні дані на незначні частини, вирішити проблему на кожній з маленьких частин, а потім об’єднати часткові рішення в глобальне рішення. Такий механізм вирішення проблеми називається «Стратегія розділяй і володарюй».

Алгоритм «Розділяй і володарюй» складається зі суперечки за допомогою наступних трьох кроків.

Розділитивихідну проблему на набір підпроблем.перемогти:Вирішуйте кожну підзадачу окремо, рекурсивно.об'єднати:З’єднайте розв’язки підзадач, щоб отримати розв’язок усієї проблеми.

Загалом, ми можемо слідувати розділяй і володарюй підхід у триетапний процес.

Приклади: Конкретні комп’ютерні алгоритми засновані на підході «Розділяй і володарюй»:

1. Проблема максимуму та мінімуму
2. Двійковий пошук
3. Сортування (сортування злиттям, швидке сортування)
4. Ханойська вежа.

Основи стратегії «Розділяй і володарюй»:

Стратегія «Розділяй і володарюй» має два основні принципи:

1. Реляційна формула
2. Умова зупинки

1. Формула відношення: Це формула, яку ми генеруємо з даної техніки. Після генерації формули ми застосовуємо стратегію D&C, тобто рекурсивно розбиваємо проблему та вирішуємо несправні підпроблеми.

2. Умова зупинки: Коли ми вирішуємо проблему за допомогою стратегії «Розділяй і володарюй», нам потрібно знати, протягом якого часу нам потрібно застосовувати «Розділяй і володарюй». Отже, умова, коли потрібно зупинити наші кроки рекурсії D&C, називається умовою зупинки.

Застосування підходу «Розділяй і володарюй»:

Наступні алгоритми базуються на концепції техніки розділяй і володарюй:

Двійковий пошук:Алгоритм бінарного пошуку — це алгоритм пошуку, який також називають напівінтервальним пошуком або логарифмічним пошуком. Він працює шляхом порівняння цільового значення з середнім елементом, наявним у відсортованому масиві. Після порівняння, якщо значення відрізняється, тоді половина, яка не містить ціль, зрештою буде усунена, а потім продовжиться пошук іншої половини. Знову розглянемо середній елемент і порівняємо його з цільовим значенням. Процес повторюється, доки не буде досягнуто цільове значення. Якщо ми виявили, що інша половина порожня після завершення пошуку, то можна зробити висновок, що ціль відсутня в масиві.Швидке сортування:Це найефективніший алгоритм сортування, який також відомий як сортування за розділами. Він починається з вибору опорного значення з масиву, а потім розділення решти елементів масиву на два підмасиви. Поділ виконується шляхом порівняння кожного з елементів із опорним значенням. Він порівнює, чи має елемент більше чи менше значення, ніж опорна точка, а потім рекурсивно сортує масиви.Сортування злиттям:Це алгоритм сортування, який сортує масив шляхом порівняння. Він починається з поділу масиву на підмасив, а потім рекурсивного сортування кожного з них. Після завершення сортування вони об’єднуються назад.Найближча пара точок:Це проблема обчислювальної геометрії. Цей алгоритм наголошує на пошуку найближчої пари точок у метричному просторі за n точок так, щоб відстань між парою точок була мінімальною.Алгоритм Штрассена:Це алгоритм множення матриць, названий на честь Фолькера Штрассена. Виявилося, що він набагато швидший, ніж традиційний алгоритм, коли працює на великих матрицях.Алгоритм швидкого перетворення Фур’є (ШПФ) Кулі-Тьюкі:Алгоритм швидкого перетворення Фур’є названий на честь Дж. В. Кулі та Джона Турка. Він відповідає підходу «розділяй і володарюй» і накладає складність O(nlogn).Алгоритм Карацуби для швидкого множення:Це один із найшвидших традиційних алгоритмів множення, винайдений Анатолієм Карацубою наприкінці 1960 року та опублікований у 1962 році. Він множить два n-значних числа таким чином, зводячи їх до однозначного.

Переваги розділяй і володарюй

• Розділяй і володарюй, як правило, успішно розв’язує одну з найбільших проблем, наприклад, математичну головоломку Ханойської вежі. Важко розв’язувати складні проблеми, про які ви не маєте базового уявлення, але за допомогою підходу «розділяй і володарюй» це зменшило зусилля, оскільки він працює над розділенням основної проблеми на дві половини, а потім рекурсивним вирішенням. Цей алгоритм набагато швидший за інші алгоритми.
• Він ефективно використовує кеш-пам’ять, не займаючи багато місця, оскільки вирішує прості підпроблеми в кеш-пам’яті замість доступу до повільнішої основної пам’яті.
• Це більш досвідчений метод, ніж його колега Brute Force.
• Оскільки ці алгоритми перешкоджають паралелізму, він не передбачає жодних модифікацій і обробляється системами, що включають паралельну обробку.

Недоліки «Розділяй і володарюй».

• Оскільки більшість його алгоритмів розроблено з використанням рекурсії, це вимагає високого управління пам’яттю.
• Явний стек може надмірно використовувати простір.
• Це може навіть привести до збою системи, якщо рекурсія виконується значно більше, ніж стек, наявний у ЦП.