Разделяй и властвуй (программирование)
Материал из Википедии — свободной энциклопедии
Разделяй и властвуй (англ. divide and conquer) — в информатике важная парадигма разработки алгоритмов. Основана на рекурсивном разбиении решаемой задачи на две (или более) подзадачи того же типа, но меньшего размера. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Типичный пример — быстрый алгоритм сортировки. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока не останется отсортировать массивы длины 1 или 2. Время выполнения этого алгоритма пропорционально nlogn, тогде как более простые алгоритмы дают n² где n — размер исходного массива.
[править] Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. — 960 с. ISBN 5-900916-37-5
