Цикломатична складність

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Цикломати́чна скла́дність — метрика програмного забезпечення, розроблена Томасом Мак Кабе. Використовується для оцінки складності програм. Обчислює кількість лінійно незалежних шляхів в алгоритмі роботи програми на основі її вихідних текстів.

Концепція метрики, але не метод, в дечому схожа на концепцію метрики загальної складності текстів Флеша-Кінкейда.

Цикломатична складність обчислюється на основі графу, що відображає цикл роботи програми. Вершинам графа зіставляють команди програми. Ребро сполучає дві вершини якщо друга команда може бути виконана одразу після першої.

Визначення[ред.ред. код]

Граф потоку керування простої програми. Програма починає виконання в червоній вершині, тоді входить в цикл (група з трьох вершин безпосередньо за червоною). По виході з циклу знаходиться умовний оператор (група наступна за циклом), і насамкінець програма завершується в блакитній вершині. Для цього графа E = 9, N = 8 і P = 1, тобто цикломатична складність цієї програми 3.

Цикломатична складність відтинку сирцевого коду — кількість лінійно незалежних шляхів в сирцевому коді. Наприклад, якщо сирцевий код не містить місць прийняття рішень таких як IF тверджень або FOR циклів, складність дорівнює 1, через наявність лиш одного шляху в сирцевому коді. якщо код містить один IF, тоді наявні два шляхи в сирцевому коді, один якщо твердження IF оцінюється як TRUE і другий якщо як FALSE.

Математично, цикломатична складність структурної програми[note 1] визначається за допомогою орієнтованого графа утворенного базовими блоками програми, з ребрами між двома базовими блоками якщо керування може бути передане від першого до другого (граф потоку керування програми). Тоді складність визначається як:[1]

M = EN + 2P

де

M = цикломатична складність
E = кількість ребер в графі
N = кількість вершин в графі
P = кількість компонент зв'язності
Із тією самою функцією, що й нагорі, показаний як сильно-зв'зний граф потоку керування, для обрахунку через альтернативний спосіб. Для цього графа E = 10, N = 8 і P = 1, тож цикломатична складність залишається 3.

Альтернативний спосіб це використання графа в якому кінцева вершина зв'язана з вхідною. В цьому випадку, кажуть, що граф є сильно зв'язним, і цикломатична складність прогами дорівнює цикломатичному числу графа (також відомому як перше число Бетті), яке визначається як:[1]

M = EN + P

На це можна дивитись як на підрахунок числа лінійно незалежних циклів, що існують в графі. Зауважимо, що з'єднання кінцевої і вхідної вершин програми, гарантує наявність щонайменше одного такого циклу.

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

Можна показати, що цикломатична складність будь-якої структурної програми тільки з однією точкою входу і однією виходу дорівнює кількості місць прийняття рішень (тобто, IF тверджень або умовних циклів), що містяться в цій програмі плюс один.[1][2]

Цикломатичну складність можна обчислювати і для програм з багатьма точками виходу; в цьому випадку вона дорівнює:

π - s + 2

де π це кількість місць прийняття рішень в програмі, а s це кількість точек виходу.[2][3]

Формальне визначення[ред.ред. код]

формально, цикломатична складність може бути визначена як відносне число Бетті, розмір відноснооднородної групи:

M := b_1(G,t) := \operatorname{rank}\,H_1(G,t)

це читається як «перший однорідний граф G, відносно термінальної вершини t». Це технічний шлях сказати «кількість лінійно незалежних маршрутів через граф від входу до виходу».

Етимологія[ред.ред. код]

Назва Цикломатична складність призводить до певної плутанини, через те, що ця метрика не тільки підраховує цикли в програмі. Натомість, ця назва пов'язана з кількістю різних циклів в графі потоку керування програми, після додання уявного переходу із кінцевої вершини до вхідної вершинри.[1]

На думку Томаса Мак Кабе кращою назвою для повсюдного використання була б умовна складність (англ. Conditional Complexity).[4]

Дивіться також[ред.ред. код]

Примітки[ред.ред. код]

  1. Тут "структурність" особливо значить "з єдиним виходом у кожній функції".
  1. а б в г McCabe A Complexity Measure ([недійсне посилання]) // IEEE Transactions on Software Engineering, (December 1976) С. 308–320.
  2. а б Belzer, Kent, Holzman and Williams (1992). Encyclopedia of Computer Science and Technology. CRC Press. с. 367–368. 
  3. Harrison Applying Mccabe's complexity measure to multiple-exit programs // Software: Practice and Experience, J Wiley & Sons (October 1984).
  4. McCabe A Complexity Measure // IEEE Transactions on Software Engineering, (December 1976) С. 315.

Посилання[ред.ред. код]