Г.С. Иванова
6
где
Op
j
(
G
i
) —
j
-я операция над графами
G
i
, а
J
i
— количество таких
операций.
2. Используя библиотеку описания операций над графами с
учетом выбранного способа представления, определить множество
операций
Op
t
над каждым множеством
M
i
,
, p
,
p
= 1,
P
i
, представ-
ляющим граф
G
i
:
{{{
Op
t
(
M
,
i p
)
/ t =
1
, T
,
i p
}
/ p =
1
, P
i
}
/ i =
1
, r
},
где
,
,
,
1
J i
t
i p
t j
i p
j
Op M Op M
—
совокупность
t
-х операций над
p
-м
множеством, представляющим
i
-й граф, которая выполняется при
реализации всех
J
i
операций над этим
графом.
3. Построить модели структур данных
S
i
[7], выбранных для
представления совокупности множеств
M
,
i p
каждого графа
G
i
, и
определить их емкостную сложность
L
(
S
i
):
{
L
(
S
i
)
/ i =
1
, r
}
.
4. Используя те же модели, определить функциональную вы-
числительную сложность
Q
d
(
S
i
) выполнения основных операций
Op
d
(
S
i
) над элементами структуры данных
S
i
:
{{
Q
d
(
S
i
)
/ d =
1
, D
}
/ i =
1
, r
}
,
где
D
— мощность множества основных операций.
5. Построить модель выполнения каждой операции
Op
t
(
M
,
i p
)
над множеством
M
,
i p
в основных операциях над элементами
структуры данных
Op
d
(
S
i
) и, используя полученные в п. 4
вычислительные сложности реализации основных операций над
элементами структур данных
Q
d
(
S
i
) и формулы (1)–(3), получить
функциональную вычислительную сложность ее выполнения
Q
t
(
M
i, p
),
т. е. определить
{{{
Qt
(
M
i
,
p
)
/ t =
1
, T
i
,
p
}
/ p =
1
, P
i
}
/ i =
1
, r
}
.
6. Построить модель выполнения каждой операции
Op
j
(
G
i
) над
графом
G
i
в элементарных операциях над множествами
Op
t
(
M
i, p
) и,
используя полученные в п. 5 вычислительные сложности реализации
элементарных операций над множествами и (1)–(3), получить
функциональную сложность ее выполнения
Q
j
(
G
i
), т. е. определить
{{
Q
j
(G
i
) / j =
1
, J
i
}
/ i =
1
, r
}
.
7. Построить модель алгоритма в элементарных операциях над
графами и, используя формулы (1)–(3), получить функциональную
вычислительную сложность этого алгоритма
Q
A
.
8. Рассчитать емкостную сложность алгоритма
L
A
как сумму
