разделяй и властвуй

Разделяй и властвуй (англ. divide and conquer) в информатике — парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными. Понимание и разработка алгоритмов "Разделяй и властвуй" — это сложный навык, который требует хорошего понимания природы основной проблемы, подлежащей решению. Как и при доказательстве теоремы с помощью математической индукции, часто необходимо заменить исходную задачу более общей или сложной задачей для инициализации рекурсии, и нет никакого систематического метода для нахождения правильного обобщения. Такие сложности метода "Разделяй и властвуй" видны при оптимизации вычисления числа Фибоначчи с эффективной двойной рекурсией. Корректность работы алгоритма, следующего парадигме "Разделяй и властвуй", чаще всего доказывается с помощью метода математической индукции, а время работы определяется либо путем непосредственного решения соответствующего рекуррентного уравнения, либо применением основной теоремы о рекуррентных соотношениях.