Метод декомпозиции (Метод «разделяй и властвуй»)

Метод декомпозиции

(Метод «разделяй и властвуй»)

Метод декомпозиции

• Алгоритмы, основанные на методе декомпозиции, работают в соответствии со следующим планом.
• Экземпляр задачи разбивается на несколько меньших экземпляров той же задачи, в идеале – одинакового размера.
• Решаются меньшие экземпляры задачи (обычно рекурсивно, хотя иногда для небольших экземпляров применяется какой-нибудь другой алгоритм).
• При необходимости решения исходной задачи находится путем комбинации решений меньших размеров.

Метод декомпозиции

В общем случае экземпляр задачи размера n может быть разделен на несколько экземпляров размером n/b, a из которых требуется решить (здесь a и b – константы; a ≥ 1 и b > 1). Полагая для упрощения анализа, что размер n равен степени b, получаем следующее рекуррентное соотношение для времени работы алгоритма: T(n) = a*T(n/b) + f(n), где f(n) – функция, учитывающая затраты на разделение задачи на меньшие подзадачи и комбинирование решений подзадач. Рекуррентное соотношение называется обобщенным рекуррентным уравнением декомпозиции (general divide-and-conquer recurrence).

Метод декомпозиции

Очевидно, что порядок роста его решения T(n) зависит от значений констант a и b и порядка роста функции f(n). Анализ эффективности множества алгоритмов, основанных на декомпозиции, существенно упрощается следующей теоремой. ОСНОВНАЯ ТЕОРЕМА. Если в рекуррентном уравнении f(n) Є Θ(n↑d), где d ≥ 0, то Θ(n↑d), если a < b↑d T(n) Є Θ((n↑d) *log n), если a = b↑d Θ(n↑(logba)), если a > b↑d Мы можем указать класс эффективности алгоритма, не решая само уравнение.

Метод декомпозиции

Метод декомпозиции мы уже применяли для решения большого количества задач: бинарный поиск, быстрая сортировка Хоара, обход бинарного дерева. Здесь рассмотрим сортировку слиянием (mergesort), представляющую собой превосходный пример успешного применения метода декомпозиции. Она сортирует заданный массив путем его разделения его на две половины, рекурсивной сортировки каждой половины и слияния двух отсортированных половин в один отсортированный массив. Сортировка слиянием была предложена фон-Нейманом.

Метод декомпозиции

Слияние двух отсортированных массивов можно выполнить следующим образом. Два указателя (индекса массивов) после инициализации указывают на первые элемента сливаемых массивов. Затем элементы, на которые указывают указатели, сравниваются, и меньший из них добавляется в новый массив. После этого индекс меньшего элемента увеличивается, и он указывает на элемент, непосредственно следующий за только что скопированным. Эта операция повторяется до тех пор, пока не будут исчерпан один из сливаемых массивов, после чего оставшиеся элементы второго массива просто добавляются в конец нового массива.

Метод декомпозиции

Merge(B[p], C[q], A[p+q]) { int i = 0, j = 0, k = 0; while(k < p+q) ( while((i < p) && (j < q)) ( if(B[i] <= C[j]) {A[k] = B[i]; i = i + 1;} else {A[k] = C[j]; j = j + 1;} k = k+1; ) if(i == p) Копировать C[j, … , q-1] в А[k, … , p+q-1]; if(j == q) Копировать B[i, … , p-1] в A[k, … , p+q-1]; ) }

Метод декомпозиции

Mergesort(A[n]) { if(текущее n > 1) { Копировать A[n/2-1] в B[n/2-1]; Копировать A[n/2-1] в C[n/2-1]; Mergesort(B[n/2-1]); Mergesort(C[n/2-1]); Merge(B, C, A); } }

Метод декомпозиции

Насколько эффективна сортировка слиянием? Положим для простоты, что n является степенью 2. Рекуррентное соотношение для количества выполняемых сравнений C(n) выглядит следующим образом: C(n) = 2*C(n/2) + Cmerge(n) для n>1, C(1)=0. Давайте проанализируем величину Cmerge(n), равную количеству сравнений ключей в процессе слияния. На каждом шаге выполняется в точности одно сравнение, после которого общее количество элементов в двух сливаемых массивах уменьшается на 1.

Метод декомпозиции

В худшем случае ни один из массивов не исчерпывается до самого конца, пока в другом массиве не останется только один элемент (например, наименьшие элементы поступают из двух массивов поочередно). Следовательно, в наихудшем случае Cmerge = n-1, и мы получаем рекуррентное соотношение Cworst(n) = 2*Cworst(n/2) + n -1 для n>1, C(1) = 0. Согласно основной теореме, Cworst(n) ЄΘ(n*log2n) Несложно найти и точное решение приведенного рекуррентного соотношения для n = 2↑k: Cworst(n) = n*log2n - n +1.