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

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

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

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

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

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

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

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

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