Алгоритм розділяй і володарюй це стратегія вирішення проблем, яка передбачає розбиття складної проблеми на більш дрібні, легші частини, вирішення кожної частини окремо, а потім комбінування рішень для вирішення вихідної проблеми. Це широко використовувана алгоритмічна техніка в інформатиці та математиці.

приклад: В Сортування злиттям алгоритм, в Розділяй і володарюй Стратегія використовується для сортування списку елементів. На зображенні нижче показано стани поділу та об’єднання для сортування масиву Сортування злиттям .

Зміст

• Що таке розділяй і володарюй?
• Етапи розділяй і володарюй
• Застосування розділяй і володарюй
• Основи розділяй і володарюй
• Стандартні алгоритми розділяй і володарюй
• Проблеми на основі двійкового пошуку
• Практичні завдання на тему «Розділяй і володарюй».

Що таке алгоритм «Розділяй і володарюй»?

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

Етапи алгоритму «Розділяй і володарюй»:

Алгоритм «Розділяй і володарюй» можна розділити на три етапи: Розділити , завоювати і Об’єднати .

1. Розділіть:

• Розбийте вихідну проблему на менші підпроблеми.
• Кожна підпроблема повинна представляти частину загальної проблеми.
• Мета полягає в тому, щоб розділити проблему, доки подальший поділ не стане можливим.

2. Перемагай:

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

3. Об'єднати:

• Об’єднайте підпроблеми, щоб отримати остаточне рішення всієї проблеми.
• Коли менші підпроблеми розв’язані, ми рекурсивно комбінуємо їхні розв’язки, щоб отримати розв’язок більшої проблеми.
• Мета полягає в тому, щоб сформулювати рішення вихідної проблеми шляхом об’єднання результатів підпроблем.

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

• Сортування злиттям: Сортування злиттям є класичним прикладом алгоритму сортування «розділяй і володарюй». Він розбиває масив на менші підмасиви, сортує їх окремо, а потім об’єднує, щоб отримати відсортований масив.
• Середній результат: Медіану набору чисел можна знайти за допомогою підходу «розділяй і володарюй». Шляхом рекурсивного поділу набору на менші підмножини можна ефективно визначити медіану.
• Мінімальний і максимальний висновок: Алгоритм «Розділяй і володарюй» можна використовувати для одночасного знаходження мінімального та максимального елементів у масиві. Розділивши масив навпіл і порівнявши пари min-max з кожної половини, загальні min і max можна визначити в логарифмічній часовій складності.
• Матричне множення: Алгоритм Штрассена для множення матриць — це техніка «розділяй і володарюй», яка зменшує кількість множень, необхідних для великих матриць, розбиваючи матриці на менші підматриці та об’єднуючи їхні продукти.
• Проблема найближчої пари: Проблема найближчої пари передбачає пошук двох найближчих точок у наборі точок у багатовимірному просторі. Алгоритм розділяй і володарюй, такий як алгоритм найближчої пари розділяй і володарюй, може ефективно вирішити цю проблему шляхом рекурсивного поділу точок і об’єднання розв’язків із підпроблем.

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

• Вступ до розділяй і володарюй
• Динамічне програмування проти розділяй і володарюй
• Зменшуй і перемагай
• Удосконалена головна теорема для повторень розділяй і володарюй

Стандартні алгоритми включені Алгоритм розділяй і володарюй :

• Двійковий пошук
• Сортування злиттям
• Швидке сортування
• Обчислити pow(x, n)
• Алгоритм Карацуба для швидкого множення
• Множення матриці Штрассена
• Опукла оболонка (простий алгоритм розділяй і володарюй)
• Алгоритм Quickhull для опуклої оболонки

Проблеми на основі бінарного пошуку:

• Знайдіть піковий елемент у заданому масиві
• Перевірити елемент більшості у відсортованому масиві
• K-й елемент двох відсортованих масивів
• Знайдіть кількість нулів
• Знайдіть кількість обертів у масиві Rotated Sorted
• Знайдіть точку, де монотонно зростаюча функція вперше стає додатною
• Медіана двох відсортованих масивів
• Медіана двох відсортованих масивів різного розміру
• Проблема розділу художника за допомогою бінарного пошуку

Тренувальні задачі на Алгоритм розділяй і володарюй :

• Квадратний корінь із цілого числа
• Максимум і мінімум масиву з використанням мінімальної кількості порівнянь
• Знайдіть частоту кожного елемента в масиві з обмеженим діапазоном за час, менший ніж O(n).
• Проблема плитки
• Лічити інверсії
• Проблема Skyline
• Пошук у двовимірному масиві, відсортованому по рядках і стовпцях
• Виділіть мінімальну кількість сторінок
• Модульне піднесення до степеня (потужність у модульній арифметиці)

Швидкі посилання:

• Вивчіть структуру даних і алгоритми | Підручник DSA
• «Практичні завдання» на тему «Розділяй і володарюй».
• «Вікторини» на тему «Розділяй і володарюй».