Предыдущая страница реферата | 27  28  29  30  31  32  33  34  35  36  37 | Следующая страница реферата

Это уравнение можно упростить, воспользовавшись соотношением:

X0 + X1 + X2 + X3 + ... + XM = (XM+1 - 1) / (X - 1)

После преобразования, уравнение приводится к виду:

T(N) = (4(N-1)+1 - 1) / (4 - 1)

= (4N - 1) / 3

=====90

С точностью до постоянных, эта процедура выполняется за время порядка
O(4N). В табл. 5.5 приведены несколько первых значений функции времени выполнения. Если вы внимательно посмотрите на эти числа, то увидите, что они соответствуют рекурсивному определению.
Этот алгоритм является типичным примером рекурсивного алгоритма, который выполняется за время порядка O(CN), где C — некоторая постоянная. При каждом вызове подпрограммы Hilbert, она увеличивает размерность задачи в 4 раза. В общем случае, если при каждом выполнении некоторого числа шагов алгоритма размер задачи увеличивается не менее, чем в C раз, то время выполнения алгоритма будет порядка O(CN).
Это поведение противоположно поведению алгоритма поиска наибольшего общего делителя. Процедура GCD уменьшает размерность задачи в 2 раза при каждом втором своем вызове, и поэтому время ее выполнения порядка O(log(N)).
Процедура построения кривых Гильберта увеличивает размер задачи в 4 раза при каждом своем вызове, поэтому время ее выполнения порядка O(4N).
Функция (4N-1)/3 — это экспоненциальная функция, которая растет очень быстро. Фактически, она растет настолько быстро, что вы можете предположить, что это не слишком эффективный алгоритм. В действительности работа этого алгоритма занимает много времени, но есть две причины, по которым это не так уж и плохо.
Во-первых, ни один алгоритм для построения кривых Гильберта не может быть намного быстрее. Кривые Гильберта содержат множество отрезков линий, и любой рисующий их алгоритм будет требовать достаточно много времени. При каждом вызове процедуры Hilbert, она рисует три линии. Пусть L(N) — суммарное число линий, из которых состоит кривая Гильберта порядка N. Тогда
L(N) = 3 * T(N) = 4N - 1, поэтому L(N) также порядка O(4N). Любой алгоритм, рисующий кривые Гильберта, должен вывести O(4N) линий, выполнив при этом
O(4N) шагов. Существуют другие алгоритмы построения кривых Гильберта, но они занимают почти столько же времени, сколько и этот алгоритм.

@Таблица 5.5. Число рекурсивных вызовов подпрограммы Hilbert

=====91

Второй факт, который показывает, что этот алгоритм не так уж плох, заключается в том, что кривые Гильберта 9 порядка содержат так много линий, что экран большинства компьютерных мониторов при этом оказывается полностью закрашенным. Это неудивительно, так как эта кривая содержит 262.143 отрезков линий. Это означает, что вам вероятно никогда не понадобится выводить на экран кривые Гильберта 9 или более высоких порядков. На каком- то порядке вы столкнетесь с ограничениями языка Visual Basic и вашего компьютера, но, скорее всего, вы еще раньше будете ограничены максимальным разрешением экрана.
Программа Hilbert, показанная на рис. 5.4, использует этот рекурсивный алгоритм для рисования кривых Гильберта. При выполнении программы не задавайте слишком большую глубину рекурсии (больше 6) до тех пор, пока вы не определите, насколько быстро выполняется эта программа на вашем компьютере.

Рекурсивное построение кривых Серпинского

Как и кривые Гильберта, кривые Серпинского (Sierpinski curves) — это самоподобные кривые, которые обычно определяются рекурсивно. На рис. 5.5 показаны кривые Серпинского 1, 2 и 3 порядка.
Алгоритм построения кривых Гильберта использует всего одну подпрограмму для рисования кривых. Кривые Серпинского проще рисовать, используя четыре отдельных процедуры, которые работают совместно. Эти процедуры называются
SierpA, SierpB, SierpC и SierpD. Это процедуры с косвенной рекурсией — каждая процедура вызывает другие, которые затем вызывают первоначальную процедуру. Они рисуют верхнюю, левую, нижнюю и правую части кривой
Серпинского, соответственно.
На рис. 5.6 показано, как эти процедуры работают совместно, образуя кривую
Серпинского 1 порядка. Подкривые изображены стрелками, чтобы показать направление, в котором они рисуются. Отрезки, соединяющие четыре подкривые, нарисованы пунктирными линиями.

@Рис. 5.4. Программа Hilbert

=====92

@Рис. 5.5. Кривые Серпинского

Каждая из четырех основных кривых состоит из диагонального отрезка, затем вертикального или горизонтального отрезка, и еще одного диагонального отрезка. Если глубина рекурсии больше единицы, каждая из этих кривых разбивается на меньшие части. Это осуществляется разбиением каждого из двух диагональных отрезков на две подкривые.
Например, для разбиения кривой типа A, первый диагональный отрезок разбивается на кривую типа A, за которой следует кривая типа B. Затем рисуется без изменений горизонтальный отрезок из исходной кривой типа A.
Наконец, второй диагональный отрезок разбивается на кривую типа D, за которой следует кривая типа A. На рис. 5.7 показано, как кривая типа A второго порядка образуется из нескольких кривых 1 порядка. Подкривые изображены жирными линиями.
На рис. 5.8 показано, как полная кривая Серпинского 2 порядка образуется из
4 подкривых 1 порядка. Каждая из подкривых обведена контурной линией.
Можно использовать стрелки ( и ( для обозначения типа линий, соединяющих подкривые (тонкие линии на рис. 5.8), тогда можно будет изобразить рекурсивные отношения между четырьмя типами кривых так, как это показано на рис. 5.9.

@Рис. 5.6. Части кривой Серпинского

=====93

@Рис. 5.7. Разбиение кривой типа A

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

Private Sub SierpA(Depth As Integer, Dist As Single)

If Depth = 1 Then

Line -Step(-Dist, Dist)

Line -Step(-Dist, 0)

Line -Step(-Dist, -Dist)

Else

SierpA Depth - 1, Dist

Line -Step(-Dist, Dist)

SierpB Depth - 1, Dist

Line -Step(-Dist, 0)

SierpD Depth - 1, Dist

Line -Step(-Dist, -Dist)

SierpA Depth - 1, Dist

End If
End Sub

@Рис. 5.8. Кривые Серпинского, образованные из меньших кривых Серпинского

=====94

@Рис. 5.9. Рекурсивные соотношения между кривыми Серпинского

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

Sub Sierpinski (Depth As Integer, Dist As Single)

SierpB Depth, Dist

Line -Step(Dist, Dist)

SierpC Depth, Dist

Line -Step(Dist, -Dist)

SierpD Depth, Dist

Line -Step(-Dist, -Dist)

SierpA Depth, Dist

Line -Step(-Dist, Dist)
End Sub

Анализ времени выполнения программы

Чтобы проанализировать время выполнения этого алгоритма, необходимо определить число вызовов для каждой из четырех процедур рисования кривых.
Пусть T(N) — число вызовов любой из четырех основных подпрограмм основной процедуры Sierpinski при построении кривой порядка N.
Если порядок кривой равен 1, кривая каждого типа рисуется только один раз.
Прибавив сюда основную процедуру, получим T(1) = 5.
При каждом рекурсивном вызове, процедура вызывает саму себя или другие процедуры четыре раза. Так как эти процедуры практически одинаковые, то
T(N) будет одинаковым, независимо от того, какая процедура вызывается первой. Это обусловлено тем, что кривые Серпинского симметричны и содержат одно и то же число кривых разных типов. Рекурсивные уравнения для T(N) выглядят так:

T(1) = 5
T(N) = 1 + 4 * T(N-1) для N > 1.

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.



Предыдущая страница реферата | 27  28  29  30  31  32  33  34  35  36  37 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки