Если N > 1, то функция рекурсивно вычисляет Fib(N-1) и Fib(N-2), и завершает работу. При первом вызове функции, условие остановки не выполняется — оно достигается только в следующих, рекурсивных вызовах. Полное число выполнения условия остановки для входного значения N, складывается из числа раз, которое оно выполняется для значения N-1 и числа раз, которое оно выполнялось для значения N-2. Все это можно записать так:
G(0) = 1
G(1) = 1
G(N) = G(N - 1) + G(N - 2) для N > 1.
Это рекурсивное определение очень похоже на определение чисел Фибоначчи. В табл. 5.2 приведены некоторые значения функций G(N) и Fib(N). Легко увидеть, что G(N) = Fib(N+1).
Теперь рассмотрим, сколько раз алгоритм достигает рекурсивного шага. Если N<=1, функция не достигает этого шага. При N>1, функция достигает этого шага 1 раз и затем рекурсивно вычисляет Fib(n-1) и Fib(N-2). Пусть H(N) — число раз, которое алгоритм достигает рекурсивного шага для входа N. Тогда H(N)=1+H(N-1)+H(N-2). Уравнения, определяющие H(N):
H(0) = 0
H(1) = 0
H(N) = 1 + H(N - 1) + H(N - 2) для N > 1.
В табл. 5.3 показаны некоторые значения для функций Fib(N) и H(N). Можно увидеть, что H(N)=Fib(N+1)-1.
@Таблица 5.2. Значения чисел Фибоначчи и функции G(N)
======87
@Таблица 5.3. Значения чисел Фибоначчи и функции H(N)
Объединяя результаты для G(N) и H(N), получаем полное время выполнения для алгоритма:
Время выполнения = G(N) + H(N)
= Fib(N + 1) + Fib(N + 1) - 1
= 2 * Fib(N + 1) - 1
Поскольку Fib(N + 1) >= Fib(N) для всех значений N, то:
Время выполнения >= 2 * Fib(N) - 1
С точностью до порядка это составит O(Fib(N)). Интересно, что эта функция не только рекурсивная, но она также используется для оценки времени ее выполнения.
Чтобы помочь вам представить скорость роста функции Фибоначчи, можно показать, что Fib(M)>ÆM-2 где Æ — константа, примерно равная 1,6. Это означает, что время выполнения не меньше, чем значение экспоненциальной функции O(ÆM). Как и другие экспоненциальные функции, эта функция растет быстрее, чем полиномиальные функции, но медленнее, чем функция факториала.
Поскольку время выполнения растет очень быстро, этот алгоритм довольно медленно выполняется для больших входных значений. Фактически, настолько медленно, что на практике почти невозможно вычислить значения функции Fib(N) для N, которые намного больше 30. В табл. 5.4 показано время выполнения для этого алгоритма на компьютере с процессором Pentium с тактовой частотой 90 МГц при разных входных значениях.
Программа Fibo использует этот рекурсивный алгоритм для вычисления чисел Фибоначчи. Введите целое число и нажмите на кнопку Go для вычисления чисел Фибоначчи. Начните с небольших чисел, пока не оцените, насколько быстро ваш компьютер может выполнять эти вычисления.
Рекурсивное построение кривых Гильберта
Кривые Гильберта (Hilbert curves) — это самоподобные (self‑similar) кривые, которые обычно определяются при помощи рекурсии. На рис. 5.2. показаны кривые Гильберта с 1, 2 или 3 порядка.
@Таблица 5.4. Время выполнения программы Fibonacci
=====88
@Рис. 5.2. Кривые Гильберта
Кривая Гильберта, как и любая другая самоподобная кривая, создается разбиением большой кривой на меньшие части. Затем вы можете использовать эту же кривую, после изменения размера и поворота, для построения этих частей. Эти части можно разбить на более мелкие части, и так далее, пока процесс не достигнет нужной глубины рекурсии. Порядок кривой определяется как максимальная глубина рекурсии, которой достигает процедура.
Процедура Hilbert управляет глубиной рекурсии, используя соответствующий параметр. При каждом рекурсивном вызове, процедура уменьшает параметр глубины рекурсии на единицу. Если процедура вызывается с глубиной рекурсии, равной 1, она рисует простую кривую 1 порядка, показанную на рис. 5.2 слева и завершает работу. Это условие остановки рекурсии.
Например, кривая Гильберта 2 порядка состоит из четырех кривых Гильберта 1 порядка. Аналогично, кривая Гильберта 3 порядка состоит из четырех кривых 2 порядка, каждая из которых состоит из четырех кривых 1 порядка. На рис. 5.3 показаны кривые Гильберта 2 и 3 порядка. Меньшие кривые, из которых построены кривые большего размера, выделены полужирными линиями.
Следующий код строит кривую Гильберта 1 порядка:
Line -Step (Length, 0)
Line -Step (0, Length)
Line -Step (-Length, 0)
Предполагается, что рисование начинается с верхнего левого угла области и что Length — это заданная длина каждого отрезка линий.
Можно набросать черновик метода, рисующего кривые Гильберта более высоких порядков:
Private Sub Hilbert(Depth As Integer)
If Depth = 1 Then
Нарисовать кривую Гильберта 1 порядка
Else
Нарисовать и соединить 4 кривые порядка (Depth - 1)
End If
End Sub
====89
@Рис. 5.3. Кривые Гильберта, образованные меньшими кривыми
Этот метод требует небольшого усложнения для определения направления рисования кривых. Это требуется для того, чтобы выбрать тип используемых кривых Гильберта.
Эту информацию можно передать процедуре при помощи параметров Dx и Dy для определения направления вывода первой линии в кривой. Для кривой 1 порядка, процедура рисует первую линию при помощи функции Line-Step(Dx, Dy). Если кривая имеет более высокий порядок, процедура соединяет первые две подкривых, используя функцию Line-Step(Dx, Dy). В любом случае, процедура может использовать параметры Dx и Dy для выбора направления, в котором она должна рисовать линии, образующие кривую.
Код на языке Visual Basic для рисования кривых Гильберта короткий, но сложный. Вам может потребоваться несколько раз пройти его в отладчике для кривых 1 и 2 порядка, чтобы увидеть, как изменяются параметры Dx и Dy, при построении различных частей кривой.
Private Sub Hilbert(depth As Integer, Dx As Single, Dy As Single)
If depth > 1 Then Hilbert depth - 1, Dy, Dx
HilbertPicture.Line -Step(Dx, Dy)
If depth > 1 Then Hilbert depth - 1, Dx, Dy
HilbertPicture.Line -Step(Dy, Dx)
If depth > 1 Then Hilbert depth - 1, Dx, Dy
HilbertPicture.Line -Step(-Dx, -Dy)
If depth > 1 Then Hilbert depth - 1, -Dy, -Dx
End Sub
Чтобы проанализировать время выполнения этой процедуры, вы можете определить число вызовов процедуры Hilbert. При каждой рекурсии она вызывает себя четыре раза. Если T(N) — это число вызовов процедуры, когда она вызывается с глубиной рекурсии N, то:
T(1) = 1
T(N) = 1 + 4 * T(N - 1) для N > 1.
Если раскрыть определение T(N), получим:
T(N) = 1 + 4 * T(N - 1)
= 1 + 4 *(1 + 4 * T(N - 2))
= 1 + 4 + 16 * T(N - 2)
= 1 + 4 + 16 * (1 + 4 * T(N - 3))
= 1 + 4 + 16 + 64 * T(N - 3)
= ...
= 40 + 41 + 42 + 43 + ... + 4K * T(N - K)
Раскрыв это уравнение до тех пор, пока не будет выполнено условие остановки рекурсии T(1)=1, получим:
T(N) = 40 + 41 + 42 + 43 + ... + 4N-1
Это уравнение можно упростить, воспользовавшись соотношением:
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) до тех пор, пока вы не определите, насколько быстро выполняется эта программа на вашем компьютере.