Эффективность алгоритма определяется мерой близости к оптимальному значению его критерия качества, под которым понимается минимум временной либо ёмкостной сложности; в сложных случаях используют составной критерий, включающий в себя оба параметра сложности с некоторыми выбранными весами. Ясно, что с увеличением размера задачи, для которой разрабатывается алгоритм, всё более важной становится проблема эффективности алгоритма. Заметим здесь же, что построение эффективного алгоритма для конкретной задачи тесно связано с выбором подходящих структур данных для этой задачи.
Существует большое число приёмов, иногда очень хитроумных, построения эффективных алгоритмов для конкретных задач. В то же время наработано небольшое число методов построения эффективных алгоритмов, которые применимы ко многим задачам и даже их классам. Ниже рассматриваются основные из этих методов.
Рекурсия
Процедуру, которая прямо или косвенно обращается к себе, называют рекурсивной. Применение рекурсии часто позволяет давать более ясные и сжатые описания алгоритмов, чем это было бы возможно без неё.
Рекурсия является особенно мощным средством в математических определениях. Рассмотрим несколько примеров таких определений.
1. Натуральные числа:
а) 1 есть натуральное число;
б) целое число, следующее за натуральным, есть натуральное число (х '= x +1 – см. c. 64).
2. Древовидные структуры:
 |
а) О - есть дерево (называемое пустым деревом);
б) если Т1 и Т2 - деревья, то
есть дерево (нарисованное сверху вниз).
3. Функция факториал n! для неотрицательных целых чисел:
а) 0!=1;
б) если n >0, то n! = n(n-1)!
Мощность рекурсии связана с тем, что она позволяет определять бесконечное множество объектов с помощью конечного высказывания. Точно так же бесконечные вычисления можно описать с помощью конечной рекурсивной программы, даже если эта программа не содержит явных циклов. Однако лучше всего использовать рекурсивные алгоритмы в тех случаях, когда решаемая задача, или вычисляемая функция, или обрабатываемая структура данных определена с помощью рекурсии. В общем виде рекурсивную программу P можно изобразить как композицию R базовых операторов Si (не содержащихP) и самой P:
PºR[Si, P]. (4.18)
С процедурой принято связывать некоторое множество локальных объектов, т.е. переменных, констант, типов и процедур, которые определе-ны только в этой процедуре, а вне её не существуют или не имеют смысла. Каждый раз, когда такая процедура рекурсивно вызывается, для неё создаётся новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы множества локальных переменных, созданного при предыдущем обращении к этой процедуре, значения переменных различны. Следующие правила области действия идентификаторов позволяют исключить какой-либо конфликт при использовании имён: идентификаторы всегда ссылаются на множество переменных, созданное последним; то же правило относится и к параметрам процедуры.
В качестве примера рекурсивного алгоритма рассмотрим процедуру прохождения двоичного дерева во внутреннем порядке с присвоением узлам соответствующего номера.
Алгоритм 4.1. Нумерация узлов двоичного дерева в соответствии с внутренним порядком (INOR - INternal ORder).
ВХОД. Двоичное дерево, представленное массивами LES (Left Son-левый сын) и RIS (RIght Son - правый сын).
ВЫХОД. Массив, называемый NUM (NUMber - номер), такой, что NUM[i] - номер узла i во внутреннем порядке.
МЕТОД. Кроме массивов LES, RIS и NUM, алгоритм использует глобальную переменную COT (COunT - счёт), значение которой - номер очередного узла в соответствии с внутренним порядком. Начальное значение переменной СОТ является 1. Параметр ND (NoDe - узел) вначале равен RT (RooT - корень). На рис. 4.1а изображена СА основного алгоритма, а на рис. 4.1б - процедура INOR(ND), которая применяется рекурсивно.
Основной алгоритм таков:
Begin
COT:= 1;
ND:= RT;
INOR (ND)
Еnd.
Процедура INOR (ND) записывается следующим образом:
procedure INOR (ND)
Begin
if LES[ND] ¹ 0 then INOR (LES[ND]);
NUM[ND]:= COT;
COT:= COT + 1;
if RIS[ND] ¹ 0 then INOR (RIS[ND])
End.
 |
Рекурсия даёт несколько преимуществ и, прежде всего, простоту программ. Если бы приведенный выше алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм.
Рассмотрим возможный вариант того же алгоритма, но без использования рекурсии.
Алгоритм 4.2. Вариант алгоритма 4.1 без рекурсии.
ВХОД. Тот же, что и у алгоритма 4.1.
ВЫХОД. Тот же, что и у алгоритма 4.1.
МЕТОД. При прохождении дерева в стеке запоминаются все узлы, которые ещё не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла v к его левому сыну узел v запоминается в стеке. После нахождения левого поддерева для v узел v нумеруется и выталкивается из стека. Затем нумеруется правое поддерево для v.
При переходе из v к его правому сыну узел v не помещается в стек, поскольку после нумерации правого поддерева не нужно возвращаться в v, а следует вернуться к тому предку узла v, который еще не занумерован (т.е. к ближайшему предку w узла v такому, что v лежит в левом поддереве для w). Схема этого алгоритма приведена на рис. 4.2.
Запишем нерекурсивный вариант процедуры обхода дерева.
Begin
COT:= 1;
ND:= RT;
STK:= 0;
L: while LES[ND] ¹ 0 do
Begin
PUSH; (* затолкнуть узел в стек *)
ND:= LES[ND]
end;
C: NUM[ND]:= COT;
COT:= COT +1;
if RIS[ND] ¹0 then
Begin
ND:= RIS[ND];
goto L;
end;
if STK ¹0 then
Begin
ND:= ETS; (*ETS - номер элемента в вершине стека*)
POP; (* вытолкнуть узел из стека *)
goto C;
End
End.
 |
Рассмотрим процедуру INOR из алгоритма 4.1. Когда, например, она вызывает себя с фактическим параметром LES[ND], она запоминает в стеке адрес нового значения параметра ND вместе с адресом возврата, который указывает, что по окончании работы этого вызова выполнение программы продолжается со второй строки 2. Таким образом, переменная ND эффективно заменяется на LES[ND], где бы ни входила ND в это определение процедуры.
В алгоритме 4.2 сделано так, что окончание выполнения вызова INOR с фактическим параметром RIS[ND] завершает выполнение и самой вызывающей процедуры. Поэтому не обязательно теперь хранить адрес возврата или узел (ND) в стеке, если фактическим параметром является RIS[ND].
Подобно операторам цикла, рекурсивные процедуры могут привести к бесконечным вычислениям. Поэтому необходимо рассмотреть проблему окончания работы процедур. Очевидно, что для того чтобы работа когда-либо завершилась, необходимо, чтобы рекурсивное обращение к процедуре Р подчинялось условию В, которое в какой-то момент перестаёт выполняться. Поэтому более точно схему рекурсивных алгоритмов можно представить в виде
P º if B then R[Si, P], (4.19)
или
P º R [Si, if B then P]. (4.20)
Наиболее надежный способ обеспечить окончание процедуры - связать с Р параметр (значение) n и рекурсивно вызвать Р со значением этого параметра n -1. Тогда замена условия В на n >0 гарантирует окончание работы. Это можно изобразить следующими схемами программ:
P(n) º if n >0 then R [Si, P(n -1)], (4.21)
P(n) º R [Si, if n >0 then P(n -1)]. (4.22)
На практике нужно обязательно убедиться, что наибольшая глубина рекурсии не только конечна, но и не слишком велика. Дело в том, что при каждом рекурсивном вызове процедуры Р для размещения её переменных выделяется некоторая память. Кроме этих локальных переменных, нужно ещё сохранять текущее состояние вычислений, чтобы вернуться к нему, когда закончится выполнение новой активации Р и нужно будет вернуться к старой. Другими словами, рекурсивный алгоритм работает в два прохода: сначала алгоритм "уходит" на всю глубину, резервируя память для переменных процедуры, а затем возвращается, вычисляя их значения.
Рекурсивные алгоритмы наиболее пригодны в случаях, когда поставленная задача или используемые данные определены рекурсивно. Но это не значит, что при наличии таких рекурсивных определений лучшим способом решения задачи непременно является рекурсивный алгоритм.
Программы, в которых следует избегать использования рекурсии, можно охарактеризовать схемой, изображающей их строение:
P º if B then (S; P), (4.23)
или эквивалентной ей
P º (S; if B then P). (4.24)
Эти схемы естественно применять в тех случаях, когда вычисляемые значения определяются с помощью простых рекуррентных соотношений.
Рассмотрим известный пример вычисления факториалов fi = i!:
i = 0, 1, 2, 3, 4, 5,...,
f = 1, 1, 2, 6, 24, 120,... (4.25)
"Нулевое" число определяется явным образом как f0 =1, а последующие числа обычно определяются рекурсивно - с помощью предшествующего значения:
fi+ 1 = (i+ 1) ·fi. (4.26)
Эта формула предполагает использование рекурсивного алгоритма для вычисления n -го факториального числа. Если ввести две переменные I и F для значений i и fi на i -м уровне рекурсии, то для перехода к следующему числу в последовательности (4.25) понадобятся такие вычисления:
I:= I+1; F:= F * I;(4.27)
подставив (4.27) вместо S в (4.23), получим рекурсивную программу
P º if I <n then (I:= I+1; F:= F*I; P);
I:= 0; F:= 1; (4.28)
Первую строку в (4.28) можно записать следующим образом:
procedure P;
Begin
if I <n then
Begin
I:= I+1; F:= F*I; P
End
end. (4.29)
Вместо процедуры можно ввести чаще используемую процедуру-функцию, т.е. некоторую процедуру, с которой явно связывается вычисляемое значение. Поэтому функцию можно использовать непосредственно как элемент выражения. Тем самым переменная F становится излишней, а роль I выполняет явный параметр процедуры.
function F(I);
Begin
if I>0 then F(I):= F(I-1)*I
else F(I):= 1
end. (4.30)
Совершенно ясно, что здесь рекурсию можно заменить обычной итерацией, а именно программой
I:= 0; F:= 1;
while I <n do
Begin
I:= I+1; F:= F*I
end. (4.31)
В общем виде программу, соответствующую схеме (4.23) или (4.24), нужно преобразовать так, чтобы она соответствовала схеме
P º (x:= xo; while B do S). (4.32)
Есть и другие, более сложные рекурсивные схемы, которые можно и должно переводить в итеративную форму. Примером служит вычисление чисел Фибоначчи, определяемых с помощью рекуррентного соотношения
fibn+1 = fibn + fibn-1 (4.33)
для n >0 и fib1=1, fib0=0.
При непосредственном подходе получим программу
function Fib(n);
Begin
if n=0 then Fib(n):= 0 else
if n=1 then Fib(n):= 1 else
Fib(n):= Fib(n-1) + Fib(n-2)
еnd. (4.34)
При вычислении fibn обращение к функции Fib(n) приводит к рекурсивным активациям этой процедуры. Сколько раз? Можно заметить, что каждое обращение при n >1 приводит к двум дальнейшим обращениям, т.е. общее число обращений растёт экспоненциально. Ясно, что такая программа непригодна для практического использования.
Однако очевидно, что числа Фибоначчи можно вычислить по итеративной схеме, при которой использование вспомогательных переменных x=fibi и y=fibi-1 позволяет избежать повторного вычисления одних и тех же значений. Тогда программа принимает вид
/* вычисляем x =fibn для n >0 */
i:= 0; x:= 1; y:= 0;
while i<n do
Begin
z:= x; i:= i+1;
x:= x+y; y:= z
End.
Отметим, что три присваивания x, y и z можно выразить всего лишь двумя присваиваниями без использования вспомогательной переменной z: x:= x+y; y:= x-y.
Итак, следует избегать рекурсии, когда имеется очевидное итеративное решение поставленной задачи. Но это не означает, что всегда нужно избавляться от рекурсии любой ценой; во многих случаях она вполне применима. Тот факт, что рекурсивные процедуры можно реализовать на нерекурсивных по сути машинах, говорит о том, что для практических целей любую рекурсивную программу можно преобразовать в чисто итеративную. Но это требует явного манипулирования со стеком рекурсий, и эти операции до такой степени заслоняют суть программы, что понять её становится очень трудно. Следовательно, алгоритмы, которые по своей сути скорее рекурсивны, чем итеративны, нужно представлять в виде рекурсивных процедур.
Примеры рекурсивных процедур (построение кривых Гильберта, Серпинского, алгоритмы с возвратом и др.) – см. в [9].
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) =3 n /2 - 2, что можно доказать индукцией по n.
Можно показать, что для одновременного поиска наибольшего и наименьшего элементов n -элементного множества надо выполнить не менее 3 n /2 - 2 сравнений его элементов. Следовательно, алгоритм 4.3 оптимален в смысле числа сравнений между элементами из S, когда n есть степень числа 2.
Временная сложность процедуры определяется числом и размером подзадач и в меньшей степени работой, необходимой для разбиения данной задачи на подзадачи. Так как рекуррентные уравнения вида (4.35) часто возникают при анализе рекурсивных алгоритмов типа “разделяй и властвуй”, рассмотрим решение таких уравнений в общем виде.
Теорема 4.1. Пусть a, b, c - неотрицательные постоянные. Решением рекуррентных уравнений вида
где n - степень числа с, является
Из теоремы вытекает, что разбиение задачи размера n (за линейное время) на две подзадачи размера n /2 даёт алгоритм сложности О(nlog2n). Если бы подзадач было 3, 4 или 16, то получился бы алгоритм сложности порядка n log23 , n 2 или n 4 соответственно. С другой стороны, разбиение задачи на 4 подзадачи размера n/4 даёт сложность порядка n log 2n, а на 9 и 16 - порядка 
и n2 соответственно.
Если n не является степенью числа С, то обычно можно вложить задачу размера n в задачу размера n', где n' - наименьшая степень числа С, большая n. Поэтому порядки роста, приведенные в теореме 4.1, сохраняются для любого n. На практике часто можно разработать рекурсивные алгоритмы, разбивающие задачи произвольного размера на С равных частей, где С велико, насколько возможно. Эти алгоритмы, как правило, эффективнее (на постоянный множитель) тех, которые получаются путем представления размера входа в виде ближайшей сверху степени числа С.
4.3.3 Принцип балансировки
Разбиение задачи на подзадачи равных размеров с целью поддержания равновесия - основной руководящий принцип при разработке эффективного алгоритма. Балансировка полезна не только при использовании приема “разделяй и властвуй”; например, эффективные алгоритмы получаются в результате балансировки размеров поддеревьев, а также весов двух операций.
Рассмотрим задачу расположения целых чисел в порядке неубывания. Простейший способ сделать это - найти наименьший элемент, исследуя всю последовательность и затем меняя местами наименьший элемент с первым. Процесс повторяется на остальных n -1 элементах, и это повторение приводит к тому, что второй наименьший элемент оказывается на втором месте. Повторение процесса на остальных n -2, n -3,..., 2 элементах сортирует всю последовательность (этот процесс известен под названием “сортировка простым выбором“). Этот алгоритм приводит к рекуррентным уравнениям
для числа сравнений, произведенных между сортируемыми элементами. Решением этих уравнений служит Т(n)=n(n-1)/2, что составляет О(n2).
Хотя этот алгоритм можно считать рекурсивным применением приема “разделяй и властвуй”, он не эффективен для больших n, поскольку задача разбивается на неравные части (одна подзадача имеет размер i, а другая - n-i, где i - номер шага процесса решения задачи). Эффективнее будет решение, если разбить задачу на две подзадачи c размерами примерно n /2. Это выполняется методом, известным как сортировка слиянием.
Рассмотрим последовательность целых чисел х1, х2,..., хn. Снова предположим для простоты, что n - степень числа 2. Один из способов упорядочить эту последовательность - разбить ее на две подпоследовательности х1, х2,..., хn/2 и xn/2+1,..., хn, упорядочить каждую из них и затем слить их. Под “слиянием” понимают объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.