Цикломатична складність
Цикломати́чна скла́дність — метрика програмного забезпечення, розроблена Томасом Мак Кабе. Використовується для оцінки складності програм. Обчислює кількість лінійно незалежних шляхів в алгоритмі роботи програми на основі її вихідних текстів.
Концепція метрики, але не метод, в дечому схожа на концепцію метрики загальної складності текстів Флеша-Кінкейда.
Цикломатична складність обчислюється на основі графу, що відображає цикл роботи програми. Вершинам графу зіставляють команди програми. Ребро сполучає дві вершини якщо друга команда може бути виконана одразу після першої.
Цикломатична складність відтинку початкового коду — кількість лінійно незалежних шляхів в сирцевому коді. Наприклад, якщо початковий код не містить місць прийняття рішень таких як IF тверджень або FOR циклів, складність дорівнює 1, через наявність лиш одного шляху в сирцевому коді. якщо код містить один IF, тоді наявні два шляхи в сирцевому коді, один якщо твердження IF оцінюється як TRUE і другий якщо як FALSE.
Математично, цикломатична складність структурної програми[note 1] визначається за допомогою орієнтованого графу утворенного базовими блоками програми, з ребрами між двома базовими блоками якщо керування може бути передане від першого до другого (граф потоку керування програми). Тоді складність визначається як:[1]
- M = E − N + 2P
де
- M = цикломатична складність
- E = кількість ребер в графі
- N = кількість вершин в графі
- P = кількість компонент зв'язності
Альтернативний спосіб це використання графу в якому кінцева вершина зв'язана з вхідною. В цьому випадку, кажуть, що граф є сильно зв'язним, і цикломатична складність програми дорівнює цикломатичному числу графу (також відомому як перше число Бетті), яке визначається як:[1]
- M = E − N + P
На це можна дивитись як на підрахунок числа лінійно незалежних циклів, що існують в графі. Зауважимо, що з'єднання кінцевої і вхідної вершин програми, гарантує наявність щонайменше одного такого циклу.
Для однієї програми (або підпрограми), P завжди дорівнює 1. Однак, цикломатична складність може бути обчислена і для декількох таких програм або підпрограм одночасно (наприклад, для всіх методів класу), в цьому випадку P буде дорівнювати кількості підпрограм в питанні, кожна підпрограма буде з'являтись як незв'язана підмножина графу.
Можна сказати, що цикломатична складність будь-якої структурної програми тільки з однією точкою входу і однією виходу дорівнює кількості місць прийняття рішень (тобто, IF тверджень або умовних циклів), що містяться в цій програмі плюс один.[1][2]
Цикломатичну складність можна обчислювати і для програм з багатьма точками виходу; в цьому випадку вона дорівнює:
- π - s + 2
де π це кількість місць прийняття рішень в програмі, а s це кількість точок виходу.[2][3]
Формально, цикломатична складність може бути визначена як відносне число Бетті, розмір відноснооднородної[en] групи:
це читається як «перший однорідний граф G, відносно термінальної вершини t». Це технічний шлях сказати «кількість лінійно незалежних маршрутів через граф від входу до виходу».
Назва Цикломатична складність призводить до певної плутанини, через те, що ця метрика не тільки підраховує цикли в програмі. Натомість, ця назва пов'язана з кількістю різних циклів в графі потоку керування програми, після додання уявного переходу із кінцевої вершини до вхідної вершини.[1]
На думку Томаса Мак Кабе кращою назвою для повсюдного використання була б умовна складність (англ. Conditional Complexity).[4]
- Цикломатичне число — характеристика графів.
- ↑ Тут "структурність" особливо значить "з єдиним виходом у кожній функції".
- ↑ а б в г McCabe (December 1976). A Complexity Measure ([недоступне посилання з 01.05.2010]). IEEE Transactions on Software Engineering: 308—320.
- ↑ а б Belzer, Kent, Holzman and Williams (1992). Encyclopedia of Computer Science and Technology. CRC Press. с. 367—368.
- ↑ Harrison (October 1984). Applying Mccabe's complexity measure to multiple-exit programs. Software: Practice and Experience. J Wiley & Sons.
- ↑ McCabe (December 1976). A Complexity Measure. IEEE Transactions on Software Engineering: 315.
- A Complexity Measure (англ.) — оригінальна праця Мак Кабе (1976).