4.3.2. Приём “разделяй и властвуй”

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

Рассмотрим для примера задачу нахождения наибольшего (MAXEL) и наименьшего (MINEL) элементов массива S, содержащего n элементов. Для простоты будем считать, что n есть степень числа 2. Очевидно, что MAXEL и MINEL следует искать по отдельности. Например, следующая процедура находит MAXEL множества S, производя n-1 сравнений его элементов:

begin

MAXEL := произвольный элемент из S;

for все другие элементы из S do

if x> MAXEL then MAXEL := x

end.

Аналогично можно найти MINEL из остальных n-1 элементов, произведя n-2 сравнений. Итак, для нахождения максимального и минимального элементов при n2 потребуется 2n-3 сравнений.

Применяя прием "разделяй и властвуй", можно было бы разбить множество S на два подмножества S1 и S2 по n/2 элементов в каждом. Тогда описанный выше алгоритм нашёл бы MAXEL и MINEL в каждой из двух половин с помощью рекурсии. MAXEL и MINEL множества S можно было бы определить, произведя еще два сравнения - наибольших элементов в S1 и S2 и наименьших элементов в них.

Алгоритм 4.3. Нахождение наибольшего и наименьшего элементов множества.

ВХОД. Множество S из n элементов, где n - степень числа 2, n2.

ВЫХОД. Наибольший (MAXEL) и наименьший (MINEL) элементы множества S.

МЕТОД. К множеству S применяется рекурсивная процедура MAXMIN. Она имеет один аргумент, представляющий собой множество S, такое, что |S|=2^k при некотором k1, и вырабатывает пару (a,b), где a - MAXEL, b - MINEL.

Процедура MAXMIN приведена ниже.

procedure MAXMIN(S)

1. if |S|=2 then

begin

2. пусть s={a, b};

3. return ( MAXEL(a, b), MINEL(a, b) )

end

else

begin

4. разбить S на два равных подмножества S1 и S2

5. (max1, min1)MAXMIN(S1);

6. (max2, min2)MAXMIN(S2);

7. return (MAXEL(max1, max2), MINEL(min1, min2) )

end.

Пусть Т(n) - число сравнений элементов множества S, которые надо произвести в процедуре MAXMIN, чтобы найти наибольший и наименьший элементы n-элементного множества. Ясно, что Т(2)=1. Если n>2, то Т(n) - общее число сравнений, выполненных в двух вызовах процедуры MAXMIN (строки 5 и 6), работающей на множестве размера n/2, и еще два сравнения в строке 7. Таким образом,

Решение рекуррентных уравнений (4.35) - функция Т(n)=3n/2 - 2, что можно доказать индукцией по n.

Можно показать, что для одновременного поиска наибольшего и наименьшего элементов n-элементного множества надо выполнить не менее 3n/2 - 2 сравнений его элементов. Следовательно, алгоритм 4.3 оптимален в смысле числа сравнений между элементами из S, когда n есть степень числа 2.

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

Теорема 4.1. Пусть a, b, c - неотрицательные постоянные. Решением рекуррентных уравнений вида

где n- степень числа с, является

Из теоремы вытекает, что разбиение задачи размера n (за линейное время) на две подзадачи размера n/2 даёт алгоритм сложности О(nlog₂n). Если бы подзадач было 3, 4 или 16, то получился бы алгоритм сложности порядка n^log₂³ , n² или n⁴ соответственно. С другой стороны, разбиение задачи на 4 подзадачи размера n/4 даёт сложность порядка nlog₂n, а на 9 и 16 - порядка иn² соответственно.

Если n не является степенью числа С, то обычно можно вложить задачу размера n в задачу размера n', где n' - наименьшая степень числа С, большая n. Поэтому порядки роста, приведенные в теореме 4.1, сохраняются для любого n. На практике часто можно разработать рекурсивные алгоритмы, разбивающие задачи произвольного размера на С равных частей, где С велико, насколько возможно. Эти алгоритмы, как правило, эффективнее (на постоянный множитель) тех, которые получаются путем представления размера входа в виде ближайшей сверху степени числа С.