Г.С. Иванова
2
время как при относительно больших размерностях входа задачи
объективную картину дает только функциональная оценка.
Предлагаемый подход лишен перечисленных недостатков.
Основные принципы и математические соотношения, поло-
женные в основу автоматизации расчета.
В основу автоматизации
расчета временной сложности алгоритма положен метод непо-
средственного расчета функции сложности выполнения программы
от размерности входа, применимый к структурным алгоритмам. Этот
метод, часто называемый методом
D
-карт [3], вручную использует
большинство авторов, занимающихся разработкой и анализом
алгоритмов.
Исходными данными для получения функций вычислительной
сложности от входа задачи являются время выполнения операторов в
условных операциях или тактах и количество повторений каждого
оператора, которое определяется размером входа задачи и струк-
турой алгоритма. Функция временной сложности отличается от
функции вычислительной сложности точностью расчета характерис-
тик времени выполнения. Если характеристика определяется с точ-
ностью до количества операторов некоторого типа, как правило
операторов сравнения, то получаем функцию вычислительной слож-
ности. Если характеристика определяется во временных единицах, то
получаем функцию временной сложности.
Для обеспечения универсальности оценки анализ характеристик
производительности алгоритма должен выполняться по его модели с
использованием характеристик области определения входных дан-
ных и области интерпретации этой модели [4]. Соответственно точ-
ность оценки зависит от степени детализации функций и предикатов
области интерпретации.
Поскольку метод непосредственного расчета применим только
для структурных алгоритмов, вычисления будем выполнять по рас-
смотренной в [5] модели структурного алгоритма, которая построена
на базе предложенной в [4] более общей модели.
Структурный алгоритм представляет собой совокупность базовых
(Следование, Ветвление, Цикл-пока) и производных конструкций, кото-
рые строятся из базовых в соответствии с принципами структурности и
являются иерархически сложными с некоторым количеством уровней
вложения [6].
Модель структурного алгоритма, предложенная в [5], базируется
на моделях базовых структурных конструкций
G
1
,
G
2
,
G
3
(рис. 1) и
модели оператора изменения данных
G
0
. При этом модели производных
структурных конструкций также строятся из базовых с использованием
правил иерархического вложения.
