McCabe度量法

McCabe度量法是由托馬斯·麥克凱提出的一種基於程式控制流的複雜性度量方法。McCabe複雜性度量又稱環路度量。它認為程式的複雜性很大程度上取決於程式圖的複雜性。單一的順序結構最為簡單,循環和選擇所構成的環路越多,程式就越複雜。這種方法以圖論為工具,先畫出程式圖,然後用該圖的環路數作為程式複雜性的度量值。程式圖是退化的程式流程圖。也就是說,把程式流程圖的每一個處理符號都退化成一個結點,原來連線不同處理符號的流線變成連線不同結點的有向弧,這樣得到的有向圖就叫做程式圖。

程式圖僅描述程式內部的控制流程,完全不表現對數據的具體操作分支和循環的具體條件。因此,它往往把一個簡單的IF語句與循環語句的複雜性看成是一樣的,把嵌套的IF語句與CASE的複雜性看成是一樣的。
根據圖論,在一個強連通的有向圖G中,環的個數V(G)由以下公式給出:
V(G)=m-n+2p其中,V(G)是有向圖G中環路數,m是圖G中弧數,n是圖G中結點數,p是圖G中強連通分量個數。在一個程式中,從程式圖的入口點總能到達圖中任何一個結點,因此,程式總是連通的,但不是強連通的。為了使圖成為強連通圖,從圖的出口點到入口點加一條用虛線表示的有向邊,使圖成為強連通圖。這樣就可以使用上式計算環路複雜性了。

相關詞條

熱門詞條

聯絡我們