Интернет магазин китайских планшетных компьютеров

Компьютеры - Разделяй и властвуй (информатика)

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

Примеры

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

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

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