Рис. 1. Модель вектора:
— вершина данных;
— вершина адреса;
— дуга, связывающая вершины
адреса; —— — ребро, связывающее вершину адреса и вершину данных
u
AD
∈
U
AD
. Таким образом, каждому компоненту
c
∈
C
вектора бу-
дет взаимно-однозначно соответствоватьдвухвершинный подграф с
одним ребром
g
(
< x
A
, x
D
>, u
AD
)
∈
G
, где
G
— граф, описывающий
организацию элементов структуры данных. Каждой связи компонен-
тов из множества
F
сопоставим дугу из множества
U
F
(рис. 1).
Рассмотрим способ определения емкостной сложности вектора по
модели. Поскольку вектор предназначен для хранения данных фик-
сированной длины, обозначим размер одного элемента через
l
V
. Ко-
личество данных, хранимых вектором, определяется мощностью мно-
жества
|
X
А
|
=
n
. Сопоставим каждому элементу из этого множества
значение веса, равное
l
V
, т.е. (
∀
x
∈
X
A
)
l
V
(
x
) =
l
V
. Каждому эле-
менту множества
X
D
сопоставим значение веса, равное нулю, т.е.
(
∀
x
∈
X
D
)
l
V
(
x
) = 0
. В результате объем памяти (в байтах), требуе-
мый для хранения вектора, составит
E
(
n
) =
∀
x
∈
X
l
V
(
x
) =
l
V
|
X
A
|
=
l
V
n.
При сравнении нескольких структур данных между собой необхо-
димо знатьобъем памяти
L
(
n
)
, занимаемый вспомогательными эле-
ментами каждой структуры данных в зависимости от числа хранимых
элементов данных. Далее функцию
L
(
n
)
будем называть
дополнитель-
ной
емкостной сложностью. Очевидно, что функция
L
(
n
)
будет связа-
на с емкостной сложностью
E
(
n
)
следующим соотношением:
E
(
n
) =
L
(
n
) +
l
V
n,
соответственно для вектора
L
(
n
) = 0
.
Можно показать, что вычислительная сложность операций, посчи-
танная по модели, совпадает с вычислительной сложностью операций
над вектором, приведенной в работах [1, 4], что обусловлено адекват-
ностью полученной модели. Для дополнения модели информацией
о вычислительной сложности операций определим также множество
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 31
