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

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

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

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

Примеры[править | править вики-текст]

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

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

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

Ссылки[править | править вики-текст]

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

Литература[править | править вики-текст]