4. способы повышения эффективности алгоритмов

4.2.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