Поиск сложных частей алгоритма

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

 

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

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

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

 

Sub Slow()

Dim I As Integer

Dim J As Integer

Dim K As Integer

For I = 1 To N

   For J = 1 To N

      For K = 1 To N

          ' Выполнить какие‑либо действия.

      Next K

   Next J

Next I

End Sub

 

Sub Fast()

Dim I As Integer

Dim J As Integer

Dim K As Integer

For I = 1 To N

   For J = 1 To N

      Slow  ' Вызов процедуры Slow.

   Next J

Next I

End Sub

 

Sub MainProgram()

Fast

End Sub

 

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

 

Sub Slow()

Dim I As Integer

Dim J As Integer

Dim K As Integer

 

For I = 1 To N

   For J = 1 To N

      For K = 1 To N

          ' Выполнить какие‑либо действия.

      Next K

   Next J

Next I

End Sub

 

Sub Fast()

Dim I As Integer

Dim J As Integer

For I = 1 To N

   For J = 1 To N

      ' Выполнить какие‑либо действия.

   Next J

Next I

End Sub

 

Sub MainProgram()

Slow

Fast

End Sub

 

 

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

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

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

 

Sub CountDown(N As Integer)

If N <= 0 Then Exit Sub

CountDown N - 1

End Sub

 

 

Многократная рекурсия

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

Нижеприведенная подпрограмма похожа на предыдущую подпрограмму CountDown, только она вызывает саму себя дважды:

 

Sub DoubleCountDown(N As Integer)

If N <= 0 Then Exit Sub

DoubleCountDown N - 1

DoubleCountDown N - 1

End Sub

 

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

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

Для больших значений N процедура вызывает себя дважды с параметром, равным N-1, выполняясь 1+2*T(N-1) раз. В табл. 1.1 приведены некоторые значения функции T(0)=1 и T(N)=1+2*T(N-1). Если обратить внимание на эти значения, можно увидеть, что T(N)=2^(N+1)-1, что дает оценку сложности процедуры порядка O(2^N). Хотя процедуры CountDown и DoubleCountDown и похожи, вторая процедура требует выполнения гораздо большего числа шагов.

 

@Таблица 1.1. Значения функции времени выполнения для подпрограммы DoubleCountDown

 

Косвенная рекурсия

Процедура также может вызывать другую процедуру, которая в свою очередь вызывает первую. Такие процедуры иногда даже сложнее анализировать, чем процедуры с множественной рекурсией. Алгоритм вычисления кривой Серпинского, который обсуждается в 5 главе, включает в себя четыре процедуры, которые используют как множественную, так и непрямую рекурсию. Каждая из этих процедур вызывает себя и другие три процедуры до четырех раз. После довольно сложных подсчетов можно показать, что этот алгоритм имеет сложность порядка O(4^N).

Требования рекурсивных алгоритмов к объему памяти

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

 

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

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

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

 

Sub GobbleMemory(N As Integer)

Dim Array() As Integer

 

ReDim Array (1 To 32000)

GobbleMemory N + 1

End Sub

 

Даже если внутри процедуры память не запрашивается, система выделяет память из системного стека (system stack) для сохранения параметров при каждом вызове процедуры. После возврата из процедуры память из стека освобождается для дальнейшего использования.

Если в подпрограмме встречается длинная последовательность рекурсивных вызовов, программа может исчерпать стек, даже если выделенная программе память еще не вся использована. Если запустить на исполнение следующую подпрограмму, она быстро исчерпает всю свободную стековую память и программа аварийно прекратит работу с сообщением об ошибке «Out of stack Space». После этого вы сможете узнать значение переменной Count, чтобы узнать, сколько раз подпрограмма вызывала себя перед тем, как исчерпать стек.

 

Sub UseStack()

Static Count As Integer

 

Count = Count + 1

UseStack

End Sub

 

Определение локальных переменных внутри подпрограммы также может занимать память из стека. Если изменить подпрограмму UseStack из предыдущего примера так, чтобы она определяла три переменных при каждом вызове, программа исчерпает стековое пространство еще быстрее:

 

Sub UseStack()

Static Count As Integer

Dim I As Variant

Dim J As Variant

Dim K As Variant

 

Count = Count + 1

UseStack

End Sub