8 / 14
В.П. Корвяков
40
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
Алгоритм функции
encode
описан следующим псевдокодом:
INTEGER encode(ROOT)
{
if (ROOT == EMPTY) return 0 // Пустое дерево кодируется нулём
N = size(ROOT) // Число узлов дерева ROOT
NL = size(ROOT.LLINK) // Число узлов левого поддерева
NR = N – NL – 1 // Число узлов правого поддерева
I = 0
for (k = 0; k < NR; k++)
{
I = I + catalan(N – k – 1)*catalan(k)
}
IL = encode(ROOT.LLINK) // Код левого поддерева
IR = encode(ROOT.LLINK) // Код правого поддерева
I = I + catalan(NL)*IR + IL
return I
}
Вычислительная сложность алгоритма.
Для анализа вычислительной
сложности разработанных алгоритмов сделаем допущение о том, что вычисле-
ние факториалов и чисел Каталана выполняется «наивным» способом, приве-
денным ниже.
1. Функция факториала требует
N
–1 операций умножения, т.
е. имеет
линейную сложность
( )
.
O N
2.
В соответствии с формулой (1) вычисление числа Каталана требует
2 1
1 2 4
N N N
N
− + + − + =
операций умножения и деления, т. е. также имеет
линейную сложность
( )
O N
.
Кроме того, значения чисел Каталана рассчитываются каждый раз и не кэ-
шируются. Поскольку индекс дерева может принимать любое значение от 0 до
1,
N
C
−
на каждом этапе рекурсивного вызова функции
decode
заранее неизвест-
но, какие индексы будут переданы функциям, вызываемым для правого и лево-
го поддеревьев. Также неизвестно, на какой итерации (от 0 до
N
–1) остановится
цикл поиска суммы, вычисляемой по формуле (2). Для упрощения будем пола-
гать, что на каждом этапе дерево разбивается на две равные части, а вычисление
формулы (2) в худшем случае проходит все
N
итераций. В соответствии с основ-
ной теоремой о рекуррентных соотношениях (
Master theorem
) [9], время работы
рекуррентного алгоритма может быть оценено по формуле
( )
( )
,
n
T n aT f n
b
=
+
где
n
— размер задачи;
a
— число подзадач в рекурсии (в рассматриваемом случае
a
= 2);
n/b
— размер каждой подзадачи (с учетом принятых допущений
b
= 2);
f
(
n
) — сложность алгоритма, выполняемого вне рекурсивных вызовов.