Разделяй и властвуй (информатика)

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

Примеры

Типичный пример — алгоритм сортировки слиянием. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока сортируемая часть массива содержит хотя бы два элемента (чтобы можно было её разбить на две части). Время работы этого алгоритма составляет <math>\Theta(n \log n)</math> операций, тогда как более простые алгоритмы требуют <math>\Theta(n^2)</math> времени, где <math>n</math> — размер исходного массива.

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

См. также

Литература

de:Teile und herrsche (Informatik) el:Διαίρει και βασίλευε (υπολογιστές) en:Divide and conquer algorithm es:Algoritmo divide y vencerás fa:الگوریتم تقسیم و حل fr:Diviser pour régner (informatique) gl:Agoritmo divide e vencerás he:אלגוריתם הפרד ומשול is:Deili- og drottnunarreiknirit it:Divide et impera (informatica) ja:分割統治法 ko:분할 정복 알고리즘 pl:Dziel i zwyciężaj pt:Divisão e conquista ro:Divide et impera (informatică) sl:Deli in vladaj (računalništvo) sr:Подели па владај (информатика) zh:分治法

Личные инструменты

Served in 0.070 secs.