Оценка структурной сложности трех критериев и метрики Маккейба

Исходный граф

Исходный управляющий граф, построенный по алгоритму программы:

Рис. 2 Управляющий граф разработанной программы

 

Найдем цикломатическое число:

Z = m – n +2 = 28 – 22 + 2 = 8,

Где m – количество дуг, а n – количество вершин.

Модифицированный граф

Как видно, некоторые из вершин можно убрать, так как они образуют линейную последовательность операторов:

Рис. 3 Модифицированный управляющий граф разработанной программы

 

Цикломатическое число осталось таким же:

Z = m – n +2 = 22 – 16 + 2 = 8,

Первый критерий

Определяем минимальный набор маршрутов, проходящих через каждый оператор ветвления и по каждой дуге:

M₁: 1- 2 - 3 - 4 - 6 -7- 4 - 6 -9- 10 -13- 4 - 6 -9- 10 - 11 -12-9- 10 - 11 -13- 4 - 2 - 3 - 14 - 16 -20- 14 - 16 -19- 14 - 2 -22; p₁=22

Вычислим уровень сложности:

S₁= p ₁ = 22

Второй критерий

Определяем число проверок каждого линейно независимого цикла и линейно независимого циклического участка программы:

Общее число проверок = Z = 8 Таким образом, общее число циклических и ациклических участков в графе равно 8.

 

Циклические участки:

M₁: 2 - 3 - 4; p₁=3

M₂: 2 - 3 - 14; p₂=3

M₃: 4 - 6 -7; p₃=2

M₄: 4 - 6 -9- 10 - 11 -13; p₄ =4

M₅: 9- 10 - 11 -13; p₅ =2

M₆: 14 - 16 -20; p₆=2

M₇: 14 - 16 -19; p₇=2

Ациклические маршруты:

M₈: 1- 2 -22; p₈=1

Метрика структурной сложности:

S₂ = p₁+p₂+p₃+p₄+p₅+p₆+p₇+p₈ = 3+3+2+4+2+2+2+1 = 19

Третий критерий

Так как циклы, идущие от вершин 4 и 14 независимы друг от друга (2 подзадачи в программе), то в третьем критерии можно рассматривать комбинации всех маршрутов внутри этих независимых циклов:

M₁: 1- 2 -22; p₁=2

M₂: 1- 2 - 3 - 4 - 6 -9- 10 - 11 -13- 4 - 2 -22; p₂=8

M₃: 1- 2 - 3 - 4 - 6 -7- 2 -22; p₃=5

M₄: 1- 2 - 3 - 4 - 6 -9- 10 -13- 4 - 2 -22; p₄=7

M₅: 1- 2 - 3 - 4 - 6 -9- 10 - 11 -12-9- 10 - 11 -13- 4 - 2 -22; p₅=10

M₆: 1- 2 - 3 - 4 - 6 -9- 10 - 11 -12-9- 10 -13- 4 - 2 -22; p₆=9

M₇: 1- 2 - 3 - 14 - 16 -20- 14 - 2 -22; p₇=6

M₈: 1- 2 - 3 - 14 - 16 -19- 14 - 2 -22; p₈=6

M₉: 1- 2 - 3 - 14 - 16 -20- 14 - 16 -19- 14 - 2 -22; p₉=8

M₁₀: 1- 2 - 3 - 4 - 6 -7-9- 10 - 11 -13- 4 - 2 -22; p₁₀=8

M₁₁: 1- 2 - 3 - 4 - 6 -7- 4 - 6 -9- 10 -13- 4 - 2 -22; p₁₁=9

M₁₂: 1- 2 - 3 - 4 - 6 -7- 4 - 6 -9- 10 - 11 -12-9- 10 - 11 -13- 2 -22; p₁₂=11

M₁₃: 1- 2 - 3 - 4 - 6 -7- 4 - 6 -9- 10 - 11 -12-9- 10 -13- 2 -22; p₁₃=10

M₁₄: 1- 2 - 3 - 4 - 2 -22; p₁₄=4

M₁₅: 1- 2 - 3 - 14 - 2 -22-9-5-9- 11 - 2 - 14; p₁₅=7

M₁₆: 1- 2 - 3 - 4 - 2 - 3 - 14 - 2 -22; p₁₆=7

Посчитаем третий критерий:

S₃= 2+2+5+7+10+9+6+6+8+8+9+11+10+4+7+7 = 111

Таблица 16 Матрица смежности управляющего графа

Таблица 17 Матрица достижимости управляющего графа

Алгоритмическая сложность на основе метрики Маккейба

На основе цикломатического числа полученного графа (Z = m –n + 2 =8) можно утверждать, что в данном графе управления можно выделить 8 независимых контуров, ведущих из начальной вершины в конечную.

Z < 10, следовательно, можно говорить о незначительной сложности алгоритма. А это значит, что исходная программа не обладает излишней сложностью, и нет необходимости разбивать ее более сложные составные части.

Вывод

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

 

Оценка характеристик программы на основе модели функциональных указателей