Розділяй та володарюй (інформатика)

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

Приклади

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

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

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

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

Див. також

• Динамічне програмування

Посилання

• Алгоритмы "разделяй и властвуй". "Жадный" алгоритм (рос.)
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4 (рос.)