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