Разделяй и властвуй в информатике — важная парадигма разработки алгоритмов,
заключающаяся в рекурсивном разбиении решаемой задачи на две или
более подзадачи того же типа, но меньшего размера, и комбинировании их решений
для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока
все подзадачи не окажутся элементарными.
Корректность
работы алгоритма, следующего парадигме "разделяй и властвуй" чаще
всего доказывается с помощью метода математической индукции. А время работы
можно определить, решив соответствующее реккурентное уравнение.
Пример: сортировка слиянием.
Анализ сложности – учебник Королев-Миков страница 122.
