Алгоритм «розділюй та володарюй»

У Вікіпедії є статті про інші значення цього терміна: Розділяй та володарюй (значення).

«Розділя́й та володарю́й» (англ. divide and conquer) в інформатиці — важлива парадигма розробки алгоритмів, що полягає в рекурсивному розбитті розв'язуваної задачі на дві або більше підзадачі того ж типу, але меншого розміру, і комбінуванні їх розв'язків для отримання відповіді до вихідного завдання. Розбиття виконуються доти, поки всі підзавдання не стануть елементарними.

Приклади

Розділяй і володарюй підхід для сортування списку (38, 27, 43, 3, 9, 82, 10) у порядку зростання. Верхня половина: поділ на підсписки; середина: одноелементний список тривіально сортується; нижня половина: створення відсортованих підсписків.

Типовий приклад — алгоритм сортування злиттям. Щоб відсортувати масив чисел за зростанням, його розбивають на дві рівні частини; кожну сортують, потім відсортовані частини зливають в одну. Ця процедура застосовується до кожної з частин доти, поки сортовані частини масиву містять хоча б два елементи (щоб можна було її розбити на дві частини).

Час роботи цього алгоритму складає ${\displaystyle \Theta (n\log n)}$ операцій, тоді як простіші алгоритми вимагають ${\displaystyle \Theta (n^{2})}$ часу, де ${\displaystyle n}$ — розмір вихідного масиву.

Інші приклади важливих алгоритмів, в яких застосовується парадигма «розділяй та володарюй»:

• Двійковий пошук
• Метод бісекції
• Швидке сортування
• Швидке перетворення Фур'є
• Множення Карацуби та інші ефективні алгоритми для множення великих чисел.

Див. також

• Динамічне програмування
• Майстер-метод

Посилання

• Алгоритмы «разделяй и властвуй». «Жадный» алгоритм (рос.)^{[недоступне посилання з липня 2019]}
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 4 Розділяй і володарюй. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .