淺談程序復雜度計算方法

摘 要 隨著計算機應用的普及和社會對軟件產品的更高要求，軟件產品的研發也越來越復雜。程序復雜度已經成為評估軟件質量的一個重要指標之一。程序復雜度的度量可以估算程序中的錯誤，也可以科學計算程序員的編程工作量。正確地降低程序復雜度可以降低研發成本，提高研發效率。

關鍵詞 計算機應用 軟件質量 程序復雜度

中圖分類號：TP311.11 文獻標識碼：A

Study on Calculation Method of Program Complexity

ZHAO Zhibin， LI Bingchuan

（Chongqing Creation Vocational College， Chongqing 412160）

Abstract With the popularity of computer application and the higher requirement of society for the software products， software products research and development is becoming more and more complex. The complexity of program has become one of the important indicators to evaluate software quality， which can estimate errors in the program and also can scientifically calculate the amount of programming for programmers. Correctly reduction of program complexity can decrease the cost of research and development and improve the efficiency.

Key words computer application； software quality； program complexity

程序復雜度的度量是指一種代碼復雜度的衡量標準。它關系到開發經費、開發周期和軟件內部bug的多少。正確降低軟件復雜度可以提高對軟件的理解和軟件的可維護性。

那么程序的復雜度怎么計算？下面我們探討常見的兩種復雜度度量方法：

1 統計程序的源代碼行數來估量程序的復雜度

該方法的基本思想是統計程序中代碼有效行數，以統計的源代碼行數做為程序復雜度的度量估計值。值得注意的是在統計程序代碼行數時該統計的行數不應該包括空白、注釋、括號以及成員、類型和命名空間的聲明等。假設程序的出錯概率為每100行源程序代碼中可能有的bug數，我們可以設程序中每100行源代碼中出現一個錯誤，則該程序的出錯概率被估算為百分之一，記為1%。經驗告訴我們，程序出錯概率的估算范圍大約是在百分之零點零四至百分之七之間，在IT行業領域中，當軟件測試工程師在測試過程中對于一個小程序的可執行程序代碼部分，經過測試后得到的經驗推導出每一行代碼的出錯率應為百分之一至百分之二之間；對于一個大程序的可執行代碼部分，每一行代碼的出錯率增加到百分之二點六八至百分之三點一八之間。基于此我們推導出一個結論：代碼行度量法是一個估量不夠準確的程序復雜度計算方法。對于程序代碼少于100行的規模不大的小程序，其源代碼出錯概率隨源代碼行數呈線性遞增或遞減；但規模較大的程序例外，其程序的出錯概率與程序的代碼行數是非線性函數關系。

有效控制所編寫程序規模，弱化因程序錯誤而帶來的風險，要求每個軟件工程師應該科學降低程序復雜度，其最好的的辦法是利用模塊化程序設計的思想將軟件功能模塊進行自頂向下逐層分解。那么任何一個大規模程序都會被分解成若干個功能單一的程序模塊。這樣就可以弱化程序出錯的風險。

2 McCabe度量法

該方法在軟件領域中，被稱為軟件圈復雜度度量方法，該方法被認為是業界中一種較常用、較優秀和較科學的程序代碼復雜度的衡量方法。可以用這種方法來衡量一個程序模塊的條件判定結構的程序復雜度，度量原則是數量上表現為程序流程圖中獨立現行路徑條數，經研究發現一個程序中的圈復雜度主要跟程序流程圖中的分支結構的數量成正比例關系。當一個程序的圈復雜度度量較大的時，這可以說明該程序的編碼質量不高，在開發后期軟件測試工程師對其難以測試和維護。經研究發現，在編程過程所積累的經驗表明，一個程序中的bug數與圈復雜度有著很大的關系，當圈復雜度較大時，其程序中的bug數就較多，當圈復雜度較小時，其程序中的bug數就較小。

計算圈復雜度時，可以通過程序控制流圖來計算。其具體方法是先按功能模塊的具體設計說明，正確的做出程序流程圖；然后將程序流程圖轉換為正確的程序流圖，其轉換原則是：將程序流程圖中每個處理語句都轉換成一個結點，將程序流程圖中聯結不同語句的連線轉變成不同結點間的有向邊，這樣就會得到一個有向圖，我們將其稱為程序流圖。如圖1所示：

基于程序流圖來計算一個程序的圈復雜度具體的方法有三種：

（1） 利用有向邊和結點數來計算程序的圈復雜度

基本思想：程序的圈復雜度就是有向圖中的邊的數量減去有向圖中的結點數量，再加上2。

假設復雜度用V（G）表示，i表示有向邊，j表示結點，那么我們就會得到有向圖G的環路復雜度的公式：V（G）=ij+2

以圖1為例，我們先計算流圖中有向邊的數量是11，結點數量是9，按照上述公式可以計算如下：

V（G） = i j + 2 = 119 + 2 = 4

即該程序的圈復雜度度量值為4 。

（2） 利用判定結點數計算圈復雜度

基本思想：一個程序的復雜性和規模的大小，都直接與該程序中的判定及判定中的條件的數量相關聯，且成正比例關系。根據在實際工作中所積累的經驗，研究發現一個程序的圈復雜度實際上該程序中所有的判定的數量再加上1。

V（G） = P+1，P是流圖中G中判定結點的數量。

以圖1為例，流圖中的1、2和4結點屬于判定結點，其判定結點數量為3，所以該程序的圈復雜度V（G）=P+1=3+1=4

（3） 利用控制流圖中的區域數計算圈復雜度。

計算公式：V（G）=區域數

以圖1為例，區域數分別為三個封閉區域1-2-3-7b、2-3-4-5-7a-7b、4-5-6-7a和一個外區域。所以該程序的圈復雜度V（G）=4

利用McCabe環路復雜度（圈復雜度）度量時，做如下說明：（1）在軟件研發過程中，利用圈復雜度可以為軟件測試中白盒測試提供一個度量的方法，利用圈發雜度可以界定一個軟件的可靠性和可維護性。（2）對于程序中的復合判定，在進行復雜度度量時候應該將該符合判定分解，例如（A = 0）and（BA）or（X = 65）算做四個判定。（3）程序中圈復雜度的度量值的大小取決于該程序控制結構的難易成度。當程序中的判定或條件分支數目或循環次數增加時，該程序的圈復雜度也會隨之增加。（4）一個程序的圈復雜度是可以疊加計算的。假設程序模塊A的復雜度為6 ，程序模塊B的復雜度為2，則兩個程序模塊A和B的復雜度經疊加為8。（5）大量實踐經驗表明，當程序中的圈復雜度在10的左右時，程序的錯誤率存間斷躍升。所以對于程序復雜度超過10的程序，在具體設計時候應該分解成幾個功能單一的小程序，以減少程序中出現的bug數量 ，以提高程序的健壯性和可靠性。（6）程序中的錯誤數量與該程序的判斷數或條件數量加上子程序被調用數量成正比關系。

參考文獻

[1] 戴蒙，高建華.軟件錯誤分類、原因及特征[J].福建電腦，2003（5）.

[2] 陸兵.軟件開發與管理.北京：清華大學出版社，2009.