Г.С. Иванова
4
тело которого
G
0
G
3
C
может содержать вложенные структурные
конструкции, т. е.
G
0
{
G
1
,
G
1
F
,
G
2
F
,
G
3
,
G
3
F
}.
В итоге получаем множество моделей конструкций, изоморфных
базовым
G
B
и формируемых из сложных посредством свертки:
G
BF
= {
G
0
F
,
G
1
F
,
G
2
F
,
G
3
F
}.
Таким образом, процесс анализа модели исследуемого алгорит-ма
заключается в ее декомпозиции на фрагменты,
гомеоморфные
или,
после факторизации вложенных конструкций, изоморфные моделям
базовых конструкций. Распознавание вида конструкций перед их
сверткой осуществляется на основе выявленных в [5] инвариантов вида
куска.
Модель каждой структурной конструкции, а также модель
оператора изменения данных сопоставим с оценкой вычислительной
или, соответственно, временной сложности ее выполнения. Вычис-
ление интегральной оценки будем осуществлять в процессе фак-
торизации структурных конструкций при их распознавании.
Модели
G
0
оператора изменения данных поставим в соответ-
ствие его вычислительную
Q
0
или временную сложность
T
0
, которые
определяются количеством операций сравнения элементов структур
данных или временем выполнения этих операций.
При свертке конструкции
G
1
(Следование) функции временной
и вычислительной сложности входящих в нее операторов
G
01
и
G
02
складываются
Q
1
= Q
01
+ Q
02
,
T
1
= T
01
+ T
02
.
(1)
Функции вычислительной и временной сложности Ветвления
зависят от количества проходов по каждой ветви. Обычно это учи-
тывают, вводя вероятности выбора ветвей. Однако расчет этих ве-
роятностей, как правило, задача не тривиальная, поскольку они зависят
от значений исходных данных. Поэтому при свертке конструкции
G
2
будем считать вычислительную и временную сложность как полусумму
сложностей ветвей
G
01
и
G
02
:
Q
2
=
(
Q
01
+ Q
02
)
/ 2,
T
2
=
(
T
01
+ T
02
)
/2
.
(2)
В алгоритмах решения задач структурного анализа и синтеза в
основном встречаются счетные циклы, количество повторений ко-
торых известно либо, если анализируется подмножество универсума,
сравнительно просто можно оценить «сверху». Так, если в цикле
перебираются значения некоторой целочисленной переменной —
i
= 1,
k
, то количество его повторений, очевидно, равно
k
. Если в
цикле операции выполняются для всех элементов некоторого под-
множества —
x
X
1, то количество его повторений при условии, что
