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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Приклади[ред.ред. код]

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

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

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]