Автоматизация анализа вычислительной и емкостной сложности алгоритмов…
5
X
1
X
, |
X
| =
n
, можно оценить «сверху», как |
X
1|
n
. И, наконец, для
варианта с дополнительным условием —
x
X
1 & <Условие> в
качестве оценки «сверху» также применимо значение |
X
1|
n
.
В некоторых случаях мощность подмножества универсума
может быть ограничена физическим смыслом моделируемой сис-
темы, например заданным количеством выводов элементов
ρ
или
нагрузочной способностью элемента
A
. Использование этих величин
при оценке количества повторений цикла позволяет существенно
уточнить оценки вычислительной и временной сложности. Инфор-
мацию о подобных ограничениях количества повторений цикла
целесообразно получать от разработчика алгоритма через специаль-
ный формат описания алгоритма или в виде ответов пользователю на
соответствующие запросы.
Функции вычислительной и временной сложности счетного
цикла определяются умножением функций сложности тела цикла на
количество его повторений
k
:
Q
3
= kQ
01
,
T
3
= kT
01
.
(3)
Однако кроме счетных циклов в алгоритмах задач структурного
анализа и синтеза встречаются и итерационные циклы, количество
повторений которых неизвестно, так как зависит от конкретных
данных. Например, рассмотрим алгоритм решения задачи дихотоми-
ческого разрезания по методу ветвей и границ. В пределе при
выполнении этого алгоритма может осуществляться полный перебор.
Более точно вычислительную сложность подобных алгоритмов на
этапе компиляции без информации о конкретных наборах данных
оценить невозможно. В этом случае также целесообразно запросить
оценку количества повторений итерационного цикла у пользователя,
поскольку оно может ограничиваться конструктивными особеннос-
тями рассматриваемых объектов.
При свертке конструкций, состоящих из факторизованных
элементов, вычислительная и временная сложности также должны
рассчитываться по формулам (1)–(3).
Методика расчета вычислительной, временной и емкостной
сложности алгоритма.
Определение вычислительной, временной и
емкостной сложности структурного алгоритма по описанию в
операциях над графами состоит из следующих действий [8
–
10].
1. По описанию алгоритма в операциях над графами
A = A
(
OP
(
G
1
),
OP
(
G
2
),
…
,
OP
(
G
r
)),
определить множество операций
OP
(
G
i
) над каждым графом
G
i
:
{{
Op
j
(
G
i
)
/ j =
1
, J
i
}
/ i =
1
, r
},
