Цикломати́чна скла́дність — метрика програмного забезпечення, розроблена . Використовується для оцінки складності програм. Обчислює кількість лінійно незалежних шляхів в алгоритмі роботи програми на основі її вихідних текстів.
Концепція метрики, але не метод, в дечому схожа на концепцію метрики загальної складності текстів Флеша-Кінкейда.
Цикломатична складність обчислюється на основі графу, що відображає цикл роботи програми. Вершинам графу зіставляють команди програми. Ребро сполучає дві вершини якщо друга команда може бути виконана одразу після першої.
Визначення
Цикломатична складність відтинку початкового коду — кількість лінійно незалежних шляхів в сирцевому коді. Наприклад, якщо початковий код не містить місць прийняття рішень таких як IF тверджень або FOR циклів, складність дорівнює 1, через наявність лиш одного шляху в сирцевому коді. якщо код містить один IF, тоді наявні два шляхи в сирцевому коді, один якщо твердження IF оцінюється як TRUE і другий якщо як FALSE.
Математично, цикломатична складність структурної програми визначається за допомогою (орієнтованого графу) утворенного базовими блоками програми, з ребрами між двома базовими блоками якщо керування може бути передане від першого до другого (граф потоку керування програми). Тоді складність визначається як:
- M = E − N + 2P
де
- M = цикломатична складність
- E = кількість ребер в графі
- N = кількість вершин в графі
- P = кількість (компонент зв'язності)
Альтернативний спосіб це використання графу в якому кінцева вершина зв'язана з вхідною. В цьому випадку, кажуть, що граф є сильно зв'язним, і цикломатична складність програми дорівнює цикломатичному числу графу (також відомому як перше число Бетті), яке визначається як:
- M = E − N + P
На це можна дивитись як на підрахунок числа лінійно незалежних циклів, що існують в графі. Зауважимо, що з'єднання кінцевої і вхідної вершин програми, гарантує наявність щонайменше одного такого циклу.
Для однієї програми (або підпрограми), P завжди дорівнює 1. Однак, цикломатична складність може бути обчислена і для декількох таких програм або підпрограм одночасно (наприклад, для всіх методів класу), в цьому випадку P буде дорівнювати кількості підпрограм в питанні, кожна підпрограма буде з'являтись як незв'язана підмножина графу.
Можна сказати, що цикломатична складність будь-якої структурної програми тільки з однією точкою входу і однією виходу дорівнює кількості місць прийняття рішень (тобто, IF тверджень або умовних циклів), що містяться в цій програмі плюс один.
Цикломатичну складність можна обчислювати і для програм з багатьма точками виходу; в цьому випадку вона дорівнює:
- π - s + 2
де π це кількість місць прийняття рішень в програмі, а s це кількість точок виходу.
Формальне визначення
Формально, цикломатична складність може бути визначена як відносне число Бетті, розмір [en] групи:
це читається як «перший однорідний граф G, відносно термінальної вершини t». Це технічний шлях сказати «кількість лінійно незалежних маршрутів через граф від входу до виходу».
Етимологія
Назва Цикломатична складність призводить до певної плутанини, через те, що ця метрика не тільки підраховує цикли в програмі. Натомість, ця назва пов'язана з кількістю різних циклів в графі потоку керування програми, після додання уявного переходу із кінцевої вершини до вхідної вершини.
На думку Томаса Мак Кабе кращою назвою для повсюдного використання була б умовна складність (англ. Conditional Complexity).
Див. також
- Цикломатичне число — характеристика графів.
Примітки
- Тут "структурність" особливо значить "з єдиним виходом у кожній функції".
- 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).
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ciklomati chna skla dnist metrika programnogo zabezpechennya rozroblena Vikoristovuyetsya dlya ocinki skladnosti program Obchislyuye kilkist linijno nezalezhnih shlyahiv v algoritmi roboti programi na osnovi yiyi vihidnih tekstiv Koncepciya metriki ale ne metod v dechomu shozha na koncepciyu metriki zagalnoyi skladnosti tekstiv Flesha Kinkejda Ciklomatichna skladnist obchislyuyetsya na osnovi grafu sho vidobrazhaye cikl roboti programi Vershinam grafu zistavlyayut komandi programi Rebro spoluchaye dvi vershini yaksho druga komanda mozhe buti vikonana odrazu pislya pershoyi ViznachennyaGraf potoku keruvannya prostoyi programi Programa pochinaye vikonannya v chervonij vershini todi vhodit v cikl grupa z troh vershin bezposeredno za chervonoyu Po vihodi z ciklu znahoditsya umovnij operator grupa nastupna za ciklom i nasamkinec programa zavershuyetsya v blakitnij vershini Dlya cogo grafu E 9 N 8 i P 1 tobto ciklomatichna skladnist ciyeyi programi 3 Ciklomatichna skladnist vidtinku pochatkovogo kodu kilkist linijno nezalezhnih shlyahiv v sircevomu kodi Napriklad yaksho pochatkovij kod ne mistit misc prijnyattya rishen takih yak IF tverdzhen abo FOR cikliv skladnist dorivnyuye 1 cherez nayavnist lish odnogo shlyahu v sircevomu kodi yaksho kod mistit odin IF todi nayavni dva shlyahi v sircevomu kodi odin yaksho tverdzhennya IF ocinyuyetsya yak TRUE i drugij yaksho yak FALSE Matematichno ciklomatichna skladnist strukturnoyi programi viznachayetsya za dopomogoyu oriyentovanogo grafu utvorennogo bazovimi blokami programi z rebrami mizh dvoma bazovimi blokami yaksho keruvannya mozhe buti peredane vid pershogo do drugogo graf potoku keruvannya programi Todi skladnist viznachayetsya yak M E N 2P de M ciklomatichna skladnist E kilkist reber v grafi N kilkist vershin v grafi P kilkist komponent zv yaznosti Iz tiyeyu samoyu funkciyeyu sho j nagori pokazanij yak silno zv znij graf potoku keruvannya dlya obrahunku cherez alternativnij sposib Dlya cogo grafu E 10 N 8 i P 1 tozh ciklomatichna skladnist zalishayetsya 3 Alternativnij sposib ce vikoristannya grafu v yakomu kinceva vershina zv yazana z vhidnoyu V comu vipadku kazhut sho graf ye silno zv yaznim i ciklomatichna skladnist programi dorivnyuye ciklomatichnomu chislu grafu takozh vidomomu yak pershe chislo Betti yake viznachayetsya yak M E N P Na ce mozhna divitis yak na pidrahunok chisla linijno nezalezhnih cikliv sho isnuyut v grafi Zauvazhimo sho z yednannya kincevoyi i vhidnoyi vershin programi garantuye nayavnist shonajmenshe odnogo takogo ciklu Dlya odniyeyi programi abo pidprogrami P zavzhdi dorivnyuye 1 Odnak ciklomatichna skladnist mozhe buti obchislena i dlya dekilkoh takih program abo pidprogram odnochasno napriklad dlya vsih metodiv klasu v comu vipadku P bude dorivnyuvati kilkosti pidprogram v pitanni kozhna pidprograma bude z yavlyatis yak nezv yazana pidmnozhina grafu Mozhna skazati sho ciklomatichna skladnist bud yakoyi strukturnoyi programi tilki z odniyeyu tochkoyu vhodu i odniyeyu vihodu dorivnyuye kilkosti misc prijnyattya rishen tobto IF tverdzhen abo umovnih cikliv sho mistyatsya v cij programi plyus odin Ciklomatichnu skladnist mozhna obchislyuvati i dlya program z bagatma tochkami vihodu v comu vipadku vona dorivnyuye p s 2 de p ce kilkist misc prijnyattya rishen v programi a s ce kilkist tochok vihodu Formalne viznachennya Formalno ciklomatichna skladnist mozhe buti viznachena yak vidnosne chislo Betti rozmir en grupi M b 1 G t rank H 1 G t displaystyle M b 1 G t operatorname rank H 1 G t ce chitayetsya yak pershij odnoridnij graf G vidnosno terminalnoyi vershini t Ce tehnichnij shlyah skazati kilkist linijno nezalezhnih marshrutiv cherez graf vid vhodu do vihodu Etimologiya Nazva Ciklomatichna skladnist prizvodit do pevnoyi plutanini cherez te sho cya metrika ne tilki pidrahovuye cikli v programi Natomist cya nazva pov yazana z kilkistyu riznih cikliv v grafi potoku keruvannya programi pislya dodannya uyavnogo perehodu iz kincevoyi vershini do vhidnoyi vershini Na dumku Tomasa Mak Kabe krashoyu nazvoyu dlya povsyudnogo vikoristannya bula b umovna skladnist angl Conditional Complexity Div takozhCiklomatichne chislo harakteristika grafiv PrimitkiTut strukturnist osoblivo znachit z yedinim vihodom u kozhnij funkciyi McCabe December 1976 A Complexity Measure nedostupne posilannya z 01 05 2010 IEEE Transactions on Software Engineering 308 320 Belzer Kent Holzman and Williams 1992 Encyclopedia of Computer Science and Technology CRC Press s 367 368 Harrison October 1984 Applying Mccabe s complexity measure to multiple exit programs Software Practice and Experience J Wiley amp Sons McCabe December 1976 A Complexity Measure IEEE Transactions on Software Engineering 315 Posilannya A Complexity Measure angl originalna pracya Mak Kabe 1976