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

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

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

Корректность работы алгоритма, следующего парадигме «разделяй и властвуй», чаще всего доказывается с помощью метода математической индукции, а время работы можно определить либо непосредственно решив соответствующее рекуррентное уравнение, либо применив Основную теорему о рекуррентных соотношениях.

Примеры[править | править код]

Типичный пример — алгоритм сортировки слиянием. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока сортируемая часть массива содержит хотя бы два элемента (чтобы можно было её разбить на две части). Время работы этого алгоритма составляет операций, тогда как более простые алгоритмы требуют времени, где  — размер исходного массива.

Другие примеры важных алгоритмов, в которых применяется парадигма «разделяй и властвуй»:

См. также[править | править код]

Литература[править | править код]

Ссылки[править | править код]

  • «Рекуррентные соотношения (недоступная ссылка)». Видеозапись лекции, посвящённой рекуррентным соотношениям и методу "разделяй и властвуй", в Computer Science центре.