§7. Стратегия декомпозиции. Анализ сложности алгоритмов декомпозиции.

Метод декомпозиции (метод разбиения, стратегия «разделяй и властвуй») – метод разработки алгоритмов, при котором задача размера разбивается на более мелкие задачи, той же структуры, на основе решения которых получается решение исходной задачи.

Примеры – сортировка слиянием (см §6 mergesort), алгоритм Карацубы умножения целых чисел (см. практические занятия).

Оценка сложности алгоритмов декомпозиции требует оценки решения рекуррентных соотношений особого вида.

Пусть исходная задача разбивается на подзадач, каждая размера . Для определенности будем считать, что

а) выполнение задачи размера 1 требует с единиц времени, то есть (1)

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

Тогда время выполнения задачи размера выражается так

(1)

Для решения применим метод подстановки

В (1) подставим вместо выражение , получим

(2)

Будем подставлять в (1) выражения вида (2) последовательно для

Предположим, что размер исходной задачи (в противном случае см. замечание 1 §6), то есть . Тогда при получим

(3)

В (3) выражение называется однородным решением рекуррентного соотношения (1). Это точное решение соотношения (1), в случае, когда (то есть временная «стоимость» исходной задачи складывается только из «стоимости» решения подзадач, а объединять из можно «бесплатно»).

Заметим, что так как , то, применяя свойство логарифмов .

Таким образом, оценка однородного решения

Чем больше (больше количество подзадач), тем больше , тем больше однородное решение. Чем больше (меньше размер подзадач), тем меньше , тем меньше однородное решение.

В формуле (3) сумма называется частным решением рекуррентного соотношения (1). Оценить его достаточно трудно, даже зная вид функции . Рассмотрим некоторые наиболее важные случаи.

I. Мультипликативные управляющие функции

Определение 1. Функция называется мультипликативной, если .

Наибольший интерес представляют мультипликативные функции вида Очевидно, что для них выполняется условие определения 1: .

Пусть в (1) функция мультипликативна, тогда в (3)

Рассмотрим частное решение из (3)

Получили под знаком суммы геометрическую прогрессию, где знаменатель , тогда ее сумма (за исключением случая, когда , этот случай будет рассмотрен далее). Таким образом исходное равенство примет вид

(4).

Возможны следующие случаи

1. если , то при (т. е. .

(4) .

Значит, в случае оценка частного решения

Тогда в (3) однородное решение и частное решение имеют одинаковый порядок роста зависящий только от и и независящий от управляющей функции. Уменьшения можно достичь, только если уменьшается, увеличивается.

2. если , тогда и частное решение (4) имеет порядок роста . Таким образом, при оценка частного решения Верхний порядок роста частного решения превышает порядок роста однородного . Для уменьшения необходимо изменить управляющую функцию с целью уменьшения, а также уменьшать и увеличивать .

В частности, если , , то и частное решение имеет порядок роста .

3. если то при получении (4) формула суммирования членов геометрической прогрессии неприменима. Вернемся к частному решению в формуле (3):

=

При оценка частного решения

Функция за счет множителя превосходит в росте однородное решение . Необходимо уменьшать для уменьшения .

В частности, при , частное решение имеет порядок

Пример 1. Рассмотрим рекуррентные соотношения с начальным значением .

1. 

2. 

3. 

Во всех случаях

Однородное решение в (3) имеет вид

Рассмотрим частное решение в (3)

1. , , частное решение имеет порядок роста тот же, что у однородного, то есть .

Итого

2. , порядок роста частного решения

Итого

3. , частное решение имеет порядок роста

Итого