Разделяй и властвуй (программирование)

Материал из Википедии — свободной энциклопедии

У этого термина существуют и другие значения, см. Разделяй и властвуй.

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

Типичный пример — быстрый алгоритм сортировки. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока не останется отсортировать массивы длины 1 или 2. Время выполнения этого алгоритма в среднем пропорционально $n log n$ , тогда как более простые алгоритмы дают n², где $n$ — размер исходного массива.