Быстрый поиск

Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

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

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(N3)+O(N2)=O(N3). Такую сложность, например, будет иметь следующий фрагмент кода:

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

==============5

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

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

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

Sub CountDown(N As Integer)

If N <= 0 Then Exit Sub

CountDown N - 1

End Sub

===========6

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

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

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

Sub DoubleCountDown(N As Integer)

If N <= 0 Then Exit Sub

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(2N). Хотя процедуры CountDown и DoubleCountDown и похожи, вторая процедура требует выполнения гораздо большего числа шагов.

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

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

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

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

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

============7

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

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

Приведенная ниже подпрограмма запрашивает память при каждом вызове. После 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

В 5 главе рекурсивные алгоритмы обсуждаются более подробно.

==============8

Наихудший и усредненный случай

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

Function LocateItem(target As Integer) As Integer

For I = 1 To N

If Value(I) = target Then Exit For

Next I

LocateItem = I

End Sub

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

С другой стороны, если искомое число в начале списка, алгоритм завершит работу практически сразу, совершив всего несколько итераций. Это так называемый наилучший случай (best case) со сложностью порядка O(1). Обычно и наилучший, и наихудший случаи встречаются относительно редко, и интерес представляет оценка усредненного или ожидаемого (expected case) поведения.

Если первоначально числа в списке распределены случайно, искомый элемент может оказаться в любом месте списка. В среднем потребуется проверить N/2 элементов для того, чтобы его найти. Значит, сложность этого алгоритма в усредненном случае порядка O(N/2), или O(N), если убрать постоянный множитель.

Для некоторых алгоритмов порядок сложности для наихудшего и наилучшего вариантов различается. Например, сложность алгоритма быстрой сортировки из 9 главы в наихудшем случае порядка O(N2), но в среднем его сложность порядка O(N*log(N)), что намного быстрее. Иногда алгоритмы типа быстрой сортировки бывают очень длинными, чтобы наихудший случай достигался крайне редко.

Часто встречающиеся функции оценки порядка сложности

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

==============9

@Таблица 1.2. Часто встречающиеся функции оценки порядка сложности

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82