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

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

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

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

Примеры

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

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

• двоичный поиск;
• метод бисекции;
• быстрая сортировка;
• быстрое преобразование Фурье;
• алгоритм Карацубы и другие эффективные алгоритмы для умножения больших чисел.

См. также

• Динамическое программирование

Ссылки

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

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4