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



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

24 февраля 2011





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

Примеры

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

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

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


Просмотров: 842


<<< Разделение ответственности