4. Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызовов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.

Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определенное число инструкций, например, вывод на печать, то на оценку порядка сложности она практически не влияет. С другой стороны, если в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнять алгоритм. Если процедура вызывается внутри цикла, то влияние может быть намного больше.

В качестве примера возьмем программу, содержащую медленную процедуру Slow со сложностью порядка О(N³) и быструю процедуру Fast со сложностью порядка О(N²). Сложность всей программы зависит от соотношения между этими двумя процедурами.

Если при выполнении циклов процедуры Fast всякий раз вызывается процедура Slow, то сложности процедур перемножаются. Общая сложность равна произведению обеих сложностей. В данном случае сложность алгоритма составляет O(N²) * O(N³) или О(N³* N²) = О(N⁵).

С другой стороны, если основная программа вызывает процедуры отдельно, их вычислительная сложность складывается. В этом случае итоговая сложность по порядку величины равна O(N³) + O(N²) = O(N³).

5. Сложность рекурсивных алгоритмов

Рекурсивные процедуры (recursive procedure) - это процедуры, которые вызывают сами себя. Их сложность определяется очень тонким способом. Сложность многих рекурсивных алгоритмов зависит именно от количества итераций рекурсии. Рекурсивная процедура может казаться достаточно простой, но она может очень серьезно усложнять программу, многократно вызывая саму себя.

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

procedure CountDown(N : Integer);

begin

if (N<=0) then exit;

CountDown(N-l) ;

end;

Многократная рекурсия. Рекурсивный алгоритм, вызывающий себя несколько раз, называется многократной рекурсией (multiple recursion). Процедуры множественной рекурсии сложнее анализировать, чем однократные алгоритмы, кроме того, они могут сделать алгоритм гораздо сложнее.

Следующая процедура аналогична процедуре CountDown, только она вызывает саму себя дважды.

procedure DoubleCountDown(N : Integer) ;

begin

if (N<=0) then exit;

DoubleCountDown(N-l) ;

DoubleCountDown(N-l) ;

end;

Поскольку процедура вызывается дважды, можно было бы предположить, что ее рабочий цикл будет вдвое больше, чем цикл процедуры CountDown. При этом сложность была бы равна 2 * O(N) = O(N). В действительности ситуация гораздо сложнее.

Если количество итераций процедуры при входном значении N равно T(N), то легко заметить, что Т(0) равно 1. Если процедура вызывается с параметром 0, то программа просто закончит свою работу с первого шага.

Для больших значений N процедура запускается дважды с параметром N - 1. Количество ее итераций при этом равно 1 + 2 * T(N - 1). При внимательном рассмотрении этих значений можно заметить, что если T(N) = 2^(N+1) - 1, то рабочий цикл процедуры будет равен O(2^N).

Несмотря на то, что процедуры CountDown и DoubleCountDown выглядят почти одинаково, DoubleCountDown выполняется гораздо дольше.

Косвенная рекурсия. Рекурсивная процедура может выполняться косвенно, вызывая вторую процедуру, которая, в свою очередь, вызывает первую. Косвенную рекурсию даже сложнее анализировать, чем многократную.

Объемная сложность рекурсивных алгоритмов. Для некоторых рекурсивных алгоритмов особенно важна объемная сложность. Очень просто написать рекурсивный алгоритм, который запрашивает небольшой объем памяти при каждом вызове. Объем занятой памяти может увеличиваться в процессе последовательных рекурсивных вызовов. По этой причине необходимо провести хотя бы поверхностный анализ объемной сложности рекурсивных процедур, чтобы убедиться, что программа не исчерпает при выполнении все доступные ресурсы.

Следующая процедура выделяет больше памяти при каждом вызове. После 100 или 200 рекурсивных обращений процедура займет всю свободную память компьютера, и программа аварийно остановится, выдав сообщение об ошибке Out of Memory (Недостаточно памяти).

procedure Memory;

var

x : Pointer;

begin

GetMem(х,100000); { Выделяет 100000 байт}

Memory;

end;