МЕТРИКА МАККЕЙБА.

Для оценивания сложности потока управления программ Маккейбом была предложена метрика, базирующаяся на графическом представлении программ. Маккейб предложил представить программу в виде управляющего ориентированного графа G=(V,E), где V - вершины, соответствующие операторам, а E - дуги, соответствующие переходам. Основной метрикой сложности он предлагает считать цикломатическую сложность графа программы, или, как ее еще называют, цикломатическое число Маккейба, характеризующее трудоемкость тестирования программы.

Для вычисления цикломатического числа Маккейба Z(G) применяется формула

Z(G)=e-v+2p, (3)

где e - число дуг ориентированного графа G;

v - число вершин;

p - число компонентов связности графа.

Число компонентов связности графа можно рассматривать как количество дуг, которые необходимо добавить для преобразования графа в сильно связный. Cильно связным называется граф, любые две вершины которого взаимно достижимы. Для графов корректных программ, т. е. графов, не имеющих недостижимых от точки входа участков и "висячих" точек входа и выхода, сильно связный граф, как правило, получается путем замыкания дугой вершины, обозначающей конец программы, на вершину, обозначающую точку входа в эту программу.

По сути Z(G) определяет число линейно независимых контуров в сильно связном графе. Иначе говоря, цикломатическое число Маккейба показывает требуемое количество проходов для покрытия всех контуров сильно связного графа или количество тестовых прогонов программы, необходимых для исчерпывающего тестирования по критерию "работает каждая ветвь".

Имеет место теорема о том, что число базисных путей в орграфе равно его цикломатическому числу, увеличенному на единицу. При этом, цикломатической сложностью программы с управляющим графом G называется величина

n (G) = l (G) +1 = m - n + 2 (4)

Практически цикломатическая сложность программы равна числу предикатов плюс единица, что позволяет вычислять ее без построения управляющего графа простым подсчетом предикатов. Данная метрика отражает психологическую сложность программы.
К достоинствам метрики относят простоту ее вычисления и повторяемость результата, а также наглядность и содержательность интерпретации. В качестве недостатков можно отметить: нечувствительность к размеру программы, нечувствительность к изменению структуры программы, отсутствие корреляции со структурированностью программы, отсутствие различия между конструкциями Развилка и Цикл, отсутствие чувствительности к вложенности циклов. Указанные недостатки метрики привели к появлению ее модификаций, а также принципиально иных метрик сложности.

Метрика Майерса

Дж. Майерс предложил в качестве метрики сложности интервал [n 1¸ n 2], где n 1- цикломатическая мера, а n 2 - число отдельных условий плюс единица. При этом, оператор DO считается за одно условие, а CASE c n - исходами за n - 1- условий. Введенная мера получила название интервальной мерой.

К метрикам сложности, учитывающим вложенность управляющих конструкций, относят метрику Харрисона-Мейджела, учитывающую уровень вложенности и протяженности программного обеспечения, метрику Пивоварского , учитывающую цикломатическую сложность и глубину вложенности, и метрику Мак-Клура , учитывающую сложность схемы разбиения программы на модули с учетом вложенности модулей и их внутренней сложности.

Метрика Харрисона-Мейджела


Функциональная мера сложности Харрисона-Мейджела предусматривает приписывание каждой вершине графа своей собственной сложности (первичной) и разбиение графа на сферы влияния предикатных вершин. Сложность сферы называют приведенной и слагают ее из первичных сложностей вершин, входящих в сферу ее влияния, плюс первичную сложность самой предикатной вершины. Первичные сложности вычисляются всеми возможными способами. Отсюда функциональная мера сложности программы есть сумма приведенных сложностей всех вершин управляющего графа.

Метрика Пивоварского

Мера Пивоварского ставит целью учесть в оценке сложности программы различия не только между последовательными и вложенными управляющими конструкциями, но и между структурированными и неструктурированными программами. Она выражается отношением

N(G) = n *(G) + S Pi , (5)

где n *(G) - модифицированная цикломатическая сложность, вычисленная так же, как и V(G), но с одним отличием: оператор CASE с n- выходами рассматривается как один логический оператор, а не как n - 1 операторов.

Рi - глубина вложенности i - той предикатной вершины.


Для подсчета глубины вложенности предикатных вершин используется число сфер влияния. Под глубиной вложенности понимается число всех сфер влияния предикатов, которые либо полностью содержаться в сфере рассматриваемой вершины, либо пересекаются с ней. Глубина вложенности увеличивается за счет вложенности не самих предикатов, а сфер влияния. Сравнительный анализ цикломатических и функциональных мер с обсуждаемой для десятка различных управляющих графов программы показывает, что при нечувствительности прочих мер этого класса, мера Пивоварского возрастает при переходе от последовательных программ к вложенным и далее к неструктурированным.

Метрика Мак-Клура


Мера Мак-Клура предназначена для управления сложностью структурированных программ в процессе проектирования. Она применяется к иерархическим схемам разбиения программ на модули, что позволяет выбрать схему разбиения с меньшей сложностью задолго до написания программы. Метрикой выступает зависимость сложности программы от числа возможных путей исполнения, числа управляющих конструкций и числа переменных (от которых зависит выбор пути). Методика расчета сложности по Мак-Клуру четко ориентирована на хорошо структурированные программы.

 


МЕТРИКА ДЖИЛБА.

Одной из наиболее простых, но, как показывает практика, достаточно эффективных оценок сложности программ является метрика Т. Джилба, в которой логическая сложность программы определяется как насыщенность программы выражениями типа IF-THEN-ELSE. При этом вводятся две характеристики:

CL - абсолютная сложность программы, характеризующаяся количеством операторов условия;

cl - относительная сложность программы, характеризующаяся насыщенностью программы операторами условия, т. е. cl определяется как отношение CL к общему числу операторов.