Черников / Домашние задания / ДЗ-2 / 05_Username_Сложность-1
.docx
Упростим граф
Первый критерий.
m1: 1-2-3-2-3-4-3-4-8-10-6-7-6-7-8-10-11-12-13-12-13-8-10-11-14
S1=p1=14
Второй критерий.
Число вершин ветвления в составленном графе составляет 6, отсюда:
Z = nв + 1 = 6 + 1 = 7
Таким образом, общее число циклических и ациклических участков равно 7. Выделим маршруты на заданном графе:
• ациклические маршруты:
m1: 1-2-3-4-8-10-11-14; p1 = 4;
• циклические маршруты:
m2: 2-3; p2 = 1;
m3: 3-4; p3 = 2;
m4: 6-7; p4 = 1;
m5: 6-7-8-10; p5 = 2;
m6: 12-13; p6= 1;
m7: 8-10-11-12-13; p7= 3;
S2 = p1+p2+ p3+p4+ p5+ p6+p7+ p8= 14;
Третий критерий
m1: 1-2-3-4-8-10-11-14
m2: 1-2-3-2-3-4-8-10-11-14
m3: 1-2-3-2-3-4-3-4-8-10-11-14
m4: 1-2-3-4-3-4-8-10-11-14
m5: 1-2-3-4-8-10-6-7-6-7-8-10-11-14
m6: 1-2-3-4-8-10-6-7-8-10-11-12-13-8-10-11-14
m7: 1-2-3-4-8-10-6-7-6-7-8-10-11-12-13-8-10-11-14
m8: 1-2-3-4-8-10-6-7-6-7-8-10-11-12-13-12-13-8-10-11-14
m9: 1-2-3-2-3-4-8-10-6-7-6-7-10-11-14
m10: 1-2-3-2-3-4-3-4-8-20-6-7-6-8-10-11-14
m11: 1-2-3-2-3-4-8-10-6-7-8-10-11-12-13-8-10-11-14
m12: 1-2-3-2-3-2-4-8-10-6-7-8-10-11-12-13-12-13-8-10-11-14
m13: 1-2-3-2-3-2-4-8-10-6-7-6-7-8-10-11-12-13-8-10-11-14
m14: 1-2-3-2-3-2-4-8-10-6-7-6-7-8-10-11-12-13-12-13-8-10-11-14
m15: 1-2-3-4-3-4-8-10-6-7-8-10-11-12-13-8-10-11-14
m16: 1-2-3-4-3-4-8-10-6-7-8-10-11-12-13-12-13-8-10-11-14
m17: 1-2-3-4-3-4-8-10-6-7-6-7-8-10-11-12-13-8-10-11-14
m18: 1-2-3-4-3-4-8-10-6-7-6-7-8-10-11-12-13-8-10-11-14
m19: 1-2-3-2-3-4-3-4-8-10-6-7-8-10-11-12-13-8-10-11-14
m20: 1-2-3-2-3-4-3-4-8-10-6-7-6-7-8-10-11-12-13-8-10-11-14
m21: 1-2-3-2-3-4-3-4-8-10-6-7-8-10-11-12-13-12-13-8-10-11-14
m22: 1-2-3-2-3-4-8-10-6-7-6-7-8-10-11-12-13-12-13-8-10-11-14
S3=216
Матрица смежности
|
|
1 |
2 |
3 |
4 |
6 |
7 |
8 |
10 |
11 |
12 |
13 |
14 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
3 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
4 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
7 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
8 |
|
|
|
1 |
|
1 |
|
|
|
|
1 |
|
|
10 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
13 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
14 |
|
|
|
|
|
|
|
|
1 |
|
|
|
Матрица достижимости
|
|
1 |
2 |
3 |
4 |
6 |
7 |
8 |
10 |
11 |
12 |
13 |
14 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
3 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
4 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
10 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
11 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
12 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
13 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
14 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
В соответствии с теорией Маккейба сложность алгоритма оценивается величиной цикломатического числа, которая определяется по следующему соотношению:
Z = m – n + 2, где m – количество дуг управляющего графа, построенного на основе алгоритма программы, n – количество вершин графа. В соответствии с полученным управляющим графом m = 17, n = 12, тогда цикломатическое число равно:
Z = m – n + 2 = 17 – 12 + 1 = 7
По Маккейбу: в соответствии со значением цикломатического числа (Z = 7) в полученном графе управления программой можно выделить 7 независимых контуров, которые определяют 7 управляющих маршрутов, ведущих из начальной вершины в конечную. Значение цикломатического числа для полученного графа (Z = 7) не превышает значения 10, что говорит о незначительной сложности алгоритма решения задачи расчета значений функции.
Вывод
Исходя из полученных результатов расчета метрик структурной сложности критериям выделения маршрутов можно сделать вывод, что программа имеет невысокую алгоритмическую сложность, так как количество используемых в тексте операторов условий 7.