Розділяй та володарюй (інформатика)
«Розділя́й та володарю́й» (англ. divide and conquer) в інформатиці — важлива парадигма розробки алгоритмів, що полягає в рекурсивному розбитті розв'язуваної задачі на дві або більше підзадачі того ж типу, але меншого розміру, і комбінуванні їх розв'язків для отримання відповіді до вихідного завдання. Розбиття виконуються доти, поки всі підзавдання не стануть елементарними.
Приклади
Типовий приклад — алгоритм сортування злиттям. Щоб відсортувати масив чисел за зростанням, його розбивають на дві рівні частини; кожну сортують, потім відсортовані частини зливають в одну. Ця процедура застосовується до кожної з частин доти, поки сортовані частини масиву містять хоча б два елементи (щоб можна було її розбити на дві частини).
Час роботи цього алгоритму складає операцій, тоді як простіші алгоритми вимагають часу, де — розмір вихідного масиву.
Інші приклади важливих алгоритмів, в яких застосовується парадигма «розділяй та володарюй»:
- Двійковий пошук
- Метод бісекції
- Швидке сортування
- Швидке перетворення Фур'є
- Множення Карацуби та інші ефективні алгоритми для множення великих чисел.
Див. також
Посилання
- Алгоритмы «разделяй и властвуй». «Жадный» алгоритм (рос.)[недоступне посилання з липня 2019]
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4 (рос.)