Цикломатическая сложность: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Функция «Добавить ссылку»: добавлено 2 ссылки.
 
(не показаны 42 промежуточные версии 20 участников)
Строка 1: Строка 1:
'''Цикломати́ческая сло́жность програ́ммы''' ({{lang-en|Cyclomatic complexity of a program}}) — структурная (или топологическая) [[Качество программного обеспечения|мера сложности программ]], используемая для измерения качества [[программное обеспечение|программного обеспечения]], основанная на методах статического анализа кода. ЦСП равна увеличенному на единицу [[Цикломатическое число|цикломатическому числу]] графа программы.
'''Цикломати́ческая сло́жность програ́ммы''' ({{lang-en|cyclomatic complexity of a program}}) — структурная (или топологическая) мера сложности [[Компьютерная программа|компьютерной программы]]. Мера была разработана Томасом Дж. Маккейбом в [[1976 год|1976 году.]]


При вычислении цикломатической сложности используется [[граф потока управления]] программы. [[Узел (граф)|Узлы]] [[Граф (математика)|графа]] соответствуют неделимым группам команд программы, они соединены [[Ориентированный граф|ориентированными]] [[Ребро (теория графов)|рёбрами]], если группа команд, соответствующая второму узлу, может быть выполнена непосредственно после группы команд первого узла. Цикломатическая сложность может быть также вычислена для отдельных [[Функция (программирование)|функций]], [[Модульность (программирование)|модулей]], [[Метод (языки программирования)|методов]] или [[Класс (программирование)|классов]] в пределах программы.
Она была разработана Томасом Дж. Мак-Кейбом в [[1976 год]]у; он использовал эти показатели сложности для программ. Он производил непосредственные численные измерения для линейно независимых путей в [[Исходный код|исходных кодах]] программ. Концепция, но не метод, отчасти похож на измерение сложности с помощью [[:en:Flesch–Kincaid readability test|теста удобочитаемости Флеша-Кинкейда]]{{ref-en}} для общего текста.


Маккейб применял вычисление цикломатической сложности при [[Тестирование программного обеспечения|тестировании]]. Предложенный им метод заключался в тестировании каждого линейно независимого маршрута через программу, в этом случае число необходимых тестов равно цикломатической сложности программы.<ref>{{cite web
При вычислении цикломатической сложности используется [[control flow graph|граф потока управления]] программы: [[Узел (граф)|узлы]] [[Граф (математика)|графа]] соответствуют неделимым группам команд программы и [[Ориентированный граф|ориентированным]] [[Ребро (теория графов)|рёбрам]], каждый из которых соединяет два узла и соответствует двум командам, вторая из которых может быть выполнена сразу после первой. Цикломатическая сложность может также быть применена для отдельных [[Функция (программирование)|функций]], [[Модульность (программирование)|модулей]], [[Метод (языки программирования)|методов]] или [[Класс (программирование)|классов]] в пределах программы.
|url = http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html

|title = Основной маршрут тестирования
Эта стратегия [[Тестирование программного обеспечения|тестирования]] называется ''основным [[:Категория:Управление потоком|маршрутом]] тестирования'' Мак-Кейба, который первым предложил его. Это тестирование каждого линейного независимого маршрута через программу; в этом случае, число тестов должно быть равно цикломатической сложности программы.<ref>{{cite web
|author = A. J. Sobey
| url = http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html
|archiveurl = https://www.webcitation.org/67CusdjXN?url=http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html
| title = Основной маршрут тестирования
|archivedate = 2012-04-26
| author = A J Sobey
|accessdate = 2009-05-02
| archiveurl = http://www.webcitation.org/67CusdjXN
|deadlink = no
| archivedate = 2012-04-26
}}</ref>
}}</ref>


== Описание ==
== Описание ==
[[Файл:Control flow graph of function with loop and an if statement without loop back.svg|thumb|250px|right|Граф управления потоком простой программы. Программа начинает выполняться с красного узла, затем идут циклы (после красного узла идут две группы по три узла). Выход из цикла осуществляется через условный оператор (нижняя группа узлов) и конечный выход из программы в синем узле. Для этого графа E = 9, N = 8 и P = 1, цикломатическая сложность программы равна 3.]]
[[Файл:Control flow graph of function with loop and an if statement without loop back.svg|thumb|250px|right|Граф управления потоком простой программы. Программа начинает выполняться с красного узла, затем идут циклы (после красного узла идут две группы по три узла). Выход из цикла осуществляется через условный оператор (нижняя группа узлов) и конечный выход из программы в синем узле. Для этого графа ''E'' = 9, ''N'' = 8 и ''P'' = 1, цикломатическая сложность программы равна {{s|9 − 8 + 2 × 1 {{=}} 3}} (рассчитано по первому варианту)]]


Цикломатическая сложность части программного кода — счётное число линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек решений, таких, как указания <code>IF</code> или циклы <code>FOR</code>, то сложность равна единице, поскольку, есть только единственный маршрут через код. Если код имеет единственный оператор <code>IF</code>, содержащий простое условие, то должно быть два пути через код: один путь через оператор <code>IF</code> с оценкой как <code>TRUE</code> и один — как <code>FALSE</code>.
Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через [[Исходный код|программный код]]. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку есть только единственный маршрут через код. Если код имеет единственный оператор <code>IF</code>, содержащий простое условие, то существует два пути через код: один если условие оператора <code>IF</code> имеет значение <code>TRUE</code> и один — если <code>FALSE</code>.


Математически, цикломатическая сложность [[Структурное программирование|структурного программирования]]<ref>Here «structured» means in particular «with a single exit ([[return statement]]) per function».</ref> — определение с помощью ссылок от [[Базовый блок|базового блока]]{{ref-en}} программы на [[Ориентированный граф|ориентированный граф]] и с помощью рёбер между двумя основными блоками, если управление может переходить с первого на второй граф управления потоком программы. Тогда сложность определяется как:<ref name="mccabe76">{{cite journal|
Математически цикломатическая сложность [[Структурное программирование|структурированной программы]]<ref>Здесь термин «структурированная» означает, что программа имеет только одну точку выхода.</ref> определяется с помощью [[Ориентированный граф|ориентированного графа]], узлами которого являются блоки программы, соединенные рёбрами, если управление может переходить с одного блока на другой. Тогда сложность определяется как:<ref name="mccabe76">{{статья
|издание={{Нп3|IEEE Transactions on Software Engineering}}
last=McCabe|
|страницы=308—320
year=1976|month=December|
|заглавие=A Complexity Measure
journal=IEEE Transactions on Software Engineering|
|ссылка=http://classes.cecs.ucf.edu/eel6883/berrios/notes/Paper%204%20(Complexity%20Measure).pdf
pages=308–320|
|accessdate=2010-01-09
title=A Complexity Measure|
url=http://classes.cecs.ucf.edu/eel6883/berrios/notes/Paper%204%20(Complexity%20Measure).pdf|
|archiveurl=https://web.archive.org/web/20091229035408/http://classes.cecs.ucf.edu/eel6883/berrios/notes/Paper%204%20(Complexity%20Measure).pdf
|archivedate=2009-12-29
format={{dead link|date=May 2010}}}}</ref>:
|deadlink=yes
|язык=en
|автор=McCabe
|месяц=12
|год=1976
|тип=journal}}</ref>:


: ''M'' = ''E'' &minus; ''N'' + 2''P'',
: ''M'' = ''E'' &minus; ''N'' + 2''P'',
Строка 34: Строка 40:
: ''P'' = количество [[Компонента связности графа|компонент связности]].
: ''P'' = количество [[Компонента связности графа|компонент связности]].


[[Файл:Control flow graph of function with loop and an if statement.svg|thumb|250px|right|''Сильносвязанный'' граф управления потоком той же функции, использующийся для вычисления альтернативным путём. Для этого графа E = 10, N = 8 и P = 1, следовательно, цикломатическая сложность программы всё ещё равна 3.]]
[[Файл:Control flow graph of function with loop and an if statement.svg|thumb|250px|''Сильносвязный'' граф управления потоком той же функции. Для этого графа ''E'' = 10, ''N'' = 8 и ''P'' = 1, следовательно, цикломатическая сложность программы, рассчитанная по второму варианту, также равна {{s|10 − 8 + 1 {{=}}3}}]]
В другой формулировке используется граф, в котором каждая точка выхода соединена с обратной — точкой входа. В этом случае говорят, что граф будет сильносвязанным и цикломатическая сложность программы будет равняться [[цикломатическое число|цикломатическому числу]] этого графа (также известному как [[:en:Betti_number#Example:_the_first_Betti_number_in_graph_theory|first Betti number]]{{ref-en}}), которое определяется как:<ref name="mccabe76" />
В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. В этом случае граф является [[Связный граф|сильносвязным]], и цикломатическая сложность программы равна [[цикломатическое число|цикломатическому числу]] этого графа (также известному как [[Число Бетти|первое число Бетти]]), которое определяется как<ref name="mccabe76" />
: ''M'' = ''E'' &minus; ''N'' + ''P''
: ''M'' = ''E'' &minus; ''N'' + ''P''.


Это может рассматриваться как вычисление числа [[Линейная независимость|линейно независимых]] циклов, которые существуют в графе, то есть тех циклов, которые не содержат в себе других циклов. Надо учитывать, что каждая точка выхода из цикла становится точкой входа в него, то есть по крайней мере одна [[итерация]] его для каждой точки выхода.
Это определение может рассматриваться как вычисление числа [[Линейная независимость|линейно независимых]] циклов, которые существуют в графе, то есть тех циклов, которые не содержат в себе других циклов. Так как каждая точка выхода соединена с точкой входа, то существует по крайней мере один цикл для каждой точки выхода.


Для простой программы, или подпрограммы, или метода <code>P</code> всегда эквивалентно <code>1</code>. Цикломатическая сложность может, тем не менее, применяться к некоторым таким программам или подпрограммам (например, ко всем методам в [[Класс (программирование)|классе]]), в таком случае <code>P</code> эквивалентен числу программ, о которых идёт речь, как о каждой подпрограмме, проявляющейся как разрозненное подмножество графа.
Для простой программы, или подпрограммы, или метода ''P'' всегда равно 1. Однако цикломатическая сложность может применяться к нескольким таким программам или подпрограммам (например, ко всем методам в [[Класс (программирование)|классе]]), в таком случае ''P'' равно числу [[Подпрограмма|подпрограмм]], о которых идёт речь, так как каждая подпрограмма может быть представлена как независимая часть графа.


Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек решения (то есть, <code>if</code> операторных или условного циклов), содержащихся в этой программе, плюс один.<ref name="mccabe76"/><ref name="ecst">{{cite book|
Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек ветвления (то есть, операторов <code>if</code> или условных циклов), содержащихся в этой программе, плюс один.<ref name="mccabe76"/><ref name="ecst">{{книга |заглавие=Encyclopedia of Computer Science and Technology |издательство=[[CRC Press]] |год=1992 |страницы=367—368 |язык=en |автор=Belzer, Kent, Holzman and Williams}}</ref>
title=Encyclopedia of Computer Science and Technology|
author=Belzer, Kent, Holzman and Williams|
publisher=CRC Press|year=1992|
pages=367–368}}</ref>


Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна:<ref name="ecst" /><ref name="harrison">{{cite journal|
Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна<ref name="ecst" /><ref name="harrison">{{статья |издание=Software: Practice and Experience |заглавие=Applying Mccabe's complexity measure to multiple-exit programs |издательство=J Wiley & Sons |язык=en |тип=journal |автор=Harrison |месяц=10 |год=1984}}</ref>
: &pi; &minus; ''s'' + 2,
journal=Software: Practice and Experience|
title=Applying Mccabe's complexity measure to multiple-exit programs|
author=Harrison|
date=October 1984|
publisher=J Wiley & Sons}}</ref>
: &pi; &minus; s + 2
где:
где:
: &pi; — число точек решения в программе,
: &pi; — число точек ветвления в программе,
: s — число точек выхода.
: ''s'' — число точек выхода.


=== Формальное определение ===
=== Формальное определение ===


Формально, цикломатическая сложность может быть определена, как относительное [[число Бетти]], как размер [[:en:relative homology|относительнооднородной]] группы:
Формально, цикломатическая сложность может быть определена как относительное [[число Бетти]]:
: <math>M := b_1(G,t) := \operatorname{rank}\,H_1(G,t) </math>
: <math>M := b_1(G, t) := \operatorname{rank} H_1(G, t), </math>
Это читается, как «первый однородный граф ''G'', относительно терминального узла ''t''». Этот технический путь произносится, как «число линейно независимых маршрутов через граф от входа к выходу», где:
то есть «первая [[Гомология (математика)|гомология]] графа ''G'' относительно терминальных узлов ''t''. Это другой способ сказать «число линейно независимых маршрутов через граф от входа к выходу».
* «линейно независимый» соответствует однородности и означает, что один не возвращается в исходное состояние двойного счета;
* «маршрут» соответствует ''нальной'' однородности: маршруту соответствует одномерный объект;
* «относительно» означает, что путь должен начаться и закончится в точке входа или выхода, соответственно.


Кроме того, цикломатическую сложность можно вычислить через абсолютное [[число Бетти]] (с помощью абсолютной гомологии, а не относительной), объединив все терминальные узлы данного компонента (что эквивалентно соединению точек выхода с точкой входа), в этом случае для нового, расширенного, графа <math>\tilde G</math>
Это соответствие интуитивно понятно как цикломатическая вложенность, и может быть вычислено как указанно выше.
: <math>M = b_1(\tilde G) = \operatorname{rank} H_1(\tilde G).</math>

Кроме того, его можно вычислить через абсолютное [[число Бетти]] (абсолютно однородное — не относительное) определяющее
все терминальные узлы данного компонента (или равно, получение маршрутов соединяющих входы с выходами), в этом случае (вызов нового, расширенного графа <math>\tilde G</math>, которым он является) получаем:
: <math>M = b_1(\tilde G) = \operatorname{rank}\,H_1(\tilde G)</math>
Это соответствие характеризуется цикломатической сложностью как «количество циклов плюс количество компонентов».

=== Этимология (происхождение названия) ===
Название ''цикломатическая сложность'' может попервоначалу показаться не являющимся целостным, но это не так, так как эта метрика не только считает циклы в программе. Она должна быть первостепенно заинтересована в подсчёте количества других циклов, тех, которые контролируются по построенному по программе графу, которые заключаются в присутствии веток возврата (ветки от выходного узла к входному), которые выявляются при построении графа.<ref name="mccabe76" />


== Применение ==
== Применение ==


=== Ограничение сложности при разработке ===
=== Ограничение сложности при разработке ===
Одно из оригинальных предложений Мак-Кейба в том, что необходимо ограничивать сложность программ в течение их разработки; он рекомендует, чтобы программистов обязывали считать сложность разрабатываемых ими модулей, и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десяти.<ref name="mccabe76" /> Эта практика была адаптирована [[Национальный институт стандартов и технологий (США)|НИСТ]]-ом для методологии [[Структурное тестирование|структурного тестирования]]. С помощью этих наблюдений, со времени исходной публикации Мак-Кейба, счёт от десяти считается, что преемственная надёжность подтверждена. В некоторых случаях может быть более целесообразны ослабленные ограничения и разрешить модули со сложностью выше, чем 15. Методологически признано, что существуют случайные причины, выводящие за рамки согласованного лимита, и это сформулировано как рекомендация: "Для каждого модуля, либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен".
Одно из первоначально предложенных Маккейбом применений состоит в том, что необходимо ограничивать сложность программ во время их разработки. Он рекомендует, чтобы программистов обязывали вычислять сложность разрабатываемых ими модулей и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десять.<ref name="mccabe76" /> Эта практика была включена [[Национальный институт стандартов и технологий (США)|НИСТ]]-ом в методику [[Структурное тестирование|структурного тестирования]] с замечанием, что со времени исходной публикации Маккейба выбор значения 10 получил весомые подтверждения, однако в некоторых случаях может быть целесообразно ослабить ограничение и разрешить модули со сложностью до 15. В данной методике признаётся, что иногда могут существовать причины для выхода за рамки согласованного лимита. Это сформулировано как рекомендация: «Для каждого модуля следует либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен».
{{начало цитаты|источник = Мак-Кейб<ref>{{cite web
| author = Мак-Кейб
| authorlink =
| coauthors =
| date =
| url = http://hissa.nist.gov/HHRFdata/Artifacts/ITLdoc/235/title.htm
| title = Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric
| format =
| work =
| publisher =
| accessdate = 2010-06-03
| lang = en
| description =
| archiveurl = http://www.webcitation.org/67CutLsR9
| archivedate = 2012-04-26
}}</ref>}} Для каждого модуля, либо ограничивай цикломатическую сложность (до оговоренного предела), либо предоставляй запись, поясняющую, почему ограничение должно быть превышено.
{{oq|en|For each module, either limit cyclomatic complexity to [the agreed-upon limit] or provide a written explanation of why the limit was exceeded.}}
{{конец цитаты}}


=== Применение при тестировании программного обеспечения ===
=== Применение при тестировании программного обеспечения ===
Другое применение цикломатической сложности — при [[детерминизм|детерминизме]] числа проведённых тестов, необходимых для достижения тщательного покрытия тестированием модуля.
Другое применение цикломатической сложности — определение количества [[Тестирование программного обеспечения|тестов]], необходимых для полного [[Покрытие кода|покрытия кода]].


Он полезен, поскольку цикломатическая сложность ''M'' имеет два свойства, для конкретного [[Модуль (программирование)|модуля]]:
Он полезен, поскольку цикломатическая сложность ''M'' имеет два свойства, для конкретного [[Модуль (программирование)|модуля]]:
* ''M'' — оценка сверху для количества тестов, обеспечивающих покрытие условий (точек ветвления);
* ''M'' — верхняя граница для числа произведённых тестов, которые необходимо достичь для полного [[Покрытие кода|покрытия ветки]];
* ''M'' — оценка снизу для количества маршрутов через граф потока управления и, таким образом, количества тестов для полного покрытия путей.
* ''M'' — пониженная граница для числа маршрутов через контролируемый поток графа (КПГ).


=== В составе других метрик ===
Допустим, тест применяется каждый раз для единственного маршрута, тогда необходимое количество раз применений теста
Цикломатическая сложность используется в качестве одного из параметров в [[индексе удобства сопровождения]] ({{lang-en|maintainability index}})<ref>{{публикация|книга|заглавие=Software Measurement and Estimation: A Practical Approach|автор=Linda M. Laird, M. Carol Brennan John|издательство=Wiley & Sons|год=2006}}</ref>.
определяется [[Покрытие кода|числом покрытия]], равного числу путей, которые действительно могут быть использованы при работе программы.

Но некоторые пути могут быть невозможными, так что, число путей через КПГ — это, несомненно, верхняя граница числа тестов, для обеспечения покрытия пути (''возможного'' пути), чей номер идёт последним, которое иногда может быть меньше чем ''M''.

Все три вышеуказанные числа могут быть равны: покрытие ветки <math>\leq</math> cyclomatic complexity <math>\leq</math> количества путей.

Для примера рассмотрим нижеприведённую программу, состоящую из последовательного применения двух операторов ''if-then-else''.

<source lang="c">
if( c1() )
f1();
else
f2();

if( c2() )
f3();
else
f4();
</source>

[[Файл:Control flow graph of function with two if else statements.svg|thumb|250px|right|В вышеуказанном графе управления потоком исходного кода красный кружок обозначает точку входа в функцию, синий кружок — точку выхода. Выход соединён со входом, что делает граф сильносвязанным.]]

=== Связность ===
{{Заготовка раздела}}

=== Корреляция числа дефектов ===
{{Заготовка раздела}}
* Сложность больше 50 означает очень высокий риск и практически не тестируемый код.<ref>[http://pyobject.ru/blog/2006/07/10/cyclomatic-complexity/ Цикломатическая сложность]</ref>

== См. также ==


== Примечания ==
== Примечания ==
{{примечания}}
{{reflist}}

== Ссылки ==
* [http://www.viva64.com/terminology/Cyclomatic_complexity_rus.html Цикломатическая сложность]

{{Computer-sci-stub}}
{{rq|translate|style}}


[[Категория:Качество программного обеспечения]]
[[Категория:Качество программного обеспечения]]

[[ar:مقياس مكابي]]
[[cs:Cyklomatická složitost]]
[[de:McCabe-Metrik]]
[[en:Cyclomatic complexity]]
[[es:Complejidad ciclomática]]
[[fr:Nombre cyclomatique]]
[[hu:Ciklomatikus komplexitás]]
[[it:Complessità ciclomatica]]
[[ja:循環的複雑度]]
[[pl:Złożoność cyklomatyczna]]
[[pt:Complexidade ciclomática]]
[[ta:கட்டுப்பாட்டு சிக்கல்தன்மை]]
[[uk:Цикломатична складність]]
[[zh:循環複雜度]]

Текущая версия от 06:38, 11 декабря 2021

Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.

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

Маккейб применял вычисление цикломатической сложности при тестировании. Предложенный им метод заключался в тестировании каждого линейно независимого маршрута через программу, в этом случае число необходимых тестов равно цикломатической сложности программы.[1]

Описание

[править | править код]
Граф управления потоком простой программы. Программа начинает выполняться с красного узла, затем идут циклы (после красного узла идут две группы по три узла). Выход из цикла осуществляется через условный оператор (нижняя группа узлов) и конечный выход из программы в синем узле. Для этого графа E = 9, N = 8 и P = 1, цикломатическая сложность программы равна 9 − 8 + 2 × 1 = 3 (рассчитано по первому варианту)

Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку есть только единственный маршрут через код. Если код имеет единственный оператор IF, содержащий простое условие, то существует два пути через код: один если условие оператора IF имеет значение TRUE и один — если FALSE.

Математически цикломатическая сложность структурированной программы[2] определяется с помощью ориентированного графа, узлами которого являются блоки программы, соединенные рёбрами, если управление может переходить с одного блока на другой. Тогда сложность определяется как:[3]:

M = E − N + 2P,

где:

M = цикломатическая сложность,
E = количество рёбер в графе,
N = количество узлов в графе,
P = количество компонент связности.
Сильносвязный граф управления потоком той же функции. Для этого графа E = 10, N = 8 и P = 1, следовательно, цикломатическая сложность программы, рассчитанная по второму варианту, также равна 10 − 8 + 1 =3

В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. В этом случае граф является сильносвязным, и цикломатическая сложность программы равна цикломатическому числу этого графа (также известному как первое число Бетти), которое определяется как[3]

M = E − N + P.

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

Для простой программы, или подпрограммы, или метода P всегда равно 1. Однако цикломатическая сложность может применяться к нескольким таким программам или подпрограммам (например, ко всем методам в классе), в таком случае P равно числу подпрограмм, о которых идёт речь, так как каждая подпрограмма может быть представлена как независимая часть графа.

Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек ветвления (то есть, операторов if или условных циклов), содержащихся в этой программе, плюс один.[3][4]

Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна[4][5]

π − s + 2,

где:

π — число точек ветвления в программе,
s — число точек выхода.

Формальное определение

[править | править код]

Формально, цикломатическая сложность может быть определена как относительное число Бетти:

то есть «первая гомология графа G относительно терминальных узлов t. Это другой способ сказать «число линейно независимых маршрутов через граф от входа к выходу».

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

Применение

[править | править код]

Ограничение сложности при разработке

[править | править код]

Одно из первоначально предложенных Маккейбом применений состоит в том, что необходимо ограничивать сложность программ во время их разработки. Он рекомендует, чтобы программистов обязывали вычислять сложность разрабатываемых ими модулей и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десять.[3] Эта практика была включена НИСТ-ом в методику структурного тестирования с замечанием, что со времени исходной публикации Маккейба выбор значения 10 получил весомые подтверждения, однако в некоторых случаях может быть целесообразно ослабить ограничение и разрешить модули со сложностью до 15. В данной методике признаётся, что иногда могут существовать причины для выхода за рамки согласованного лимита. Это сформулировано как рекомендация: «Для каждого модуля следует либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен».

Применение при тестировании программного обеспечения

[править | править код]

Другое применение цикломатической сложности — определение количества тестов, необходимых для полного покрытия кода.

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

  • M — оценка сверху для количества тестов, обеспечивающих покрытие условий (точек ветвления);
  • M — оценка снизу для количества маршрутов через граф потока управления и, таким образом, количества тестов для полного покрытия путей.

В составе других метрик

[править | править код]

Цикломатическая сложность используется в качестве одного из параметров в индексе удобства сопровождения (англ. maintainability index)[6].

Примечания

[править | править код]
  1. ↑ A. J. Sobey. Основной маршрут тестирования. Дата обращения: 2 мая 2009. Архивировано 26 апреля 2012 года.
  2. ↑ Здесь термин «структурированная» означает, что программа имеет только одну точку выхода.
  3. ↑ 1 2 3 4 McCabe. A Complexity Measure (англ.) // IEEE Transactions on Software Engineering[англ.] : journal. — 1976. — December. — P. 308—320. Архивировано 29 декабря 2009 года.
  4. ↑ 1 2 Belzer, Kent, Holzman and Williams. Encyclopedia of Computer Science and Technology (англ.). — CRC Press, 1992. — P. 367—368.
  5. ↑ Harrison. Applying Mccabe's complexity measure to multiple-exit programs (англ.) // Software: Practice and Experience : journal. — J Wiley & Sons, 1984. — October.
  6. ↑ Linda M. Laird, M. Carol Brennan John. Software Measurement and Estimation: A Practical Approach. — Wiley & Sons, 2006.
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Цикломатическая_сложность&oldid=118552456