WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

Корректность работы алгоритма, следующего парадигме «разделяй и властвуй», чаще всего доказывается с помощью метода математической индукции, а время работы можно определить либо непосредственно решив соответствующее рекуррентное уравнение, либо применив Основную теорему о рекуррентных соотношениях.

Примеры

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

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

См. также

Литература

Ссылки

  • «Рекуррентные соотношения (недоступная ссылка)». Видеозапись лекции, посвящённой рекуррентным соотношениям и методу "разделяй и властвуй", в Computer Science центре.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии