- Разделяй и властвуй (информатика)
-
Разделя́й и вла́ствуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Корректность работы алгоритма, следующего парадигме "разделяй и властвуй" чаще всего доказывается с помощью метода математической индукции. А время работы можно определить решив соответствующее реккурентное уравнение.
Содержание
Примеры
Типичный пример — алгоритм сортировки слиянием. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока сортируемая часть массива содержит хотя бы два элемента (чтобы можно было её разбить на две части). Время работы этого алгоритма составляет операций, тогда как более простые алгоритмы требуют времени, где — размер исходного массива.
Другие примеры важных алгоритмов, в которых применяется парадигма «разделяй и властвуй»:
- двоичный поиск;
- метод бисекции;
- быстрая сортировка;
- быстрое преобразование Фурье;
- алгоритм Карацубы и другие эффективные алгоритмы для умножения больших чисел.
См. также
Ссылки
- «Рекуррентные соотношения». Видеозапись лекции, посвящённой рекуррентным соотношениям и методу "разделяй и властвуй", в Computer Science центре.
Литература
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
Категории:- Алгоритмы
- Разработка программного обеспечения
Wikimedia Foundation. 2010.