Разделяй и властвуй (англ. divide and conquer) — это принцип разработки алгоритмов, при котором задачу разбивают на две или более подзадачи того же типа, но меньшего размера. Их комбинируют так, чтобы в результате получить ответ к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными — базовыми. Стратегия «разделяй и властвуй» работает так: 1 Шаг. Определяем простейший случай — базовый. 2 Шаг. Находим способ свести задачу к базовому случаю. Рассмотрим пример: Имеется массив чисел...

Источник: Nuances of Programming Предыдущая часть: “Структуры данных: асимптотический анализ” При подходе «разделяй и властвуй» задача делится на мелкие подзадачи, каждая из которых решается независимо. При их делении на еще более мелкие подзадачи в конце концов настает момент, когда дальнейшее деление невозможно. Эти мельчайшие «атомарные» подзадачи и решаются. Решения всех подзадач в итоге объединяются, и получается решение исходной задачи: В целом подход «разделяй и властвуй» рассматривается как трехэтапный процесс...