程序復(fù)雜性度量

1、程序復(fù)雜性度量程序復(fù)雜性主要指模塊內(nèi)程序的復(fù)雜性。 它直接關(guān)聯(lián)到軟 件開發(fā)費用的多少， 開發(fā)周期的長短和軟件內(nèi)部潛伏錯誤的多 少。同時它也是軟件可理解性的另一種度量。減少程序復(fù)雜性，可提高軟件的簡單性和可理解性，并使 軟件開發(fā)費用減少，開發(fā)周期縮短，軟件內(nèi)部潛藏錯誤減少一、代碼行度量法 度量程序的復(fù)雜性， 最簡單的方法就是統(tǒng)計程序的源 代碼行數(shù)。此方法基于兩個前提：（1） 程序復(fù)雜性隨著程序規(guī)模的增加不均衡地增長；（ 2） 控制程序規(guī)模的方法最好是采用分而治之的辦法。將一個大程序分解成若干個簡單的可理解的程序段。方法的基本考慮是統(tǒng)計一個程序模塊的源代碼行數(shù)目， 并 以源代碼行數(shù)做為程序復(fù)雜性的

2、度量。 若設(shè)每行代碼的出錯率 為每 100 行源程序中可能有的錯誤數(shù)目， 例如每行代碼的出 錯率為 1，則是指每 100 行源程序中可能有一個錯誤。Thayer曾指出，程序出錯率的估算范圍是從0.04 %7 % 之間，即每100行源程序中可能存在0.047個錯誤。他還指 出，每行代碼的出錯率與源程序行數(shù)之間不存在簡單的線性關(guān) 系。 Lipow 進一步指出，對于小程序，每行代碼的出錯率為1.3 %1.8 %;對于大程序，每行代碼的出錯率增加到2.7 %3.2 之間，但這只是考慮了程序的可執(zhí)行部分，沒有包括程 序中的說明部分。 Lipow 及其他研究者得出一個結(jié)論：對于少 于 100 個語句的小程

3、序，源代碼行數(shù)與出錯率是線性相關(guān)的。 隨著程序的增大，出錯率以非線性方式增長。所以，代碼行度 量法只是一個簡單的，估計得很粗糙的方法。二、McCabe度量法McCabe度量法是一種基于程序控制流的復(fù)雜性度量 方法。McCabe定義的程序復(fù)雜性度量值又稱環(huán)路復(fù)雜度，它基于一個程序模塊的程序圖中環(huán)路的個數(shù)。如果把程序流程圖中每個處理符號都退化成一個結(jié)點， 原 來聯(lián)結(jié)不同處理符號的流線變成連接不同結(jié)點的有向弧， 這樣 得到的有向圖就叫做程序圖。計算有向圖G的環(huán)路復(fù)雜性的公式：V(G)= mn n + 2其中，V(G)是有向圖G中的環(huán)路個數(shù),m是圖G中有向弧個數(shù),n是圖G中結(jié)點個數(shù)。以圖9-5-1為例

4、，其中，結(jié)點數(shù)n= 11,弧數(shù)m 12,則有V (G = mn n + 2= 12- 11 + 2= 3。即McCabes路復(fù)雜度度量值為3。它也可以看做由程序 圖中的有向弧所封閉的區(qū)域個數(shù)。圖 9-5-1 程序圖的例子當(dāng)分支或循環(huán)的數(shù)目增加時, 程序中的環(huán)路也隨之增 加，因此McCabe環(huán)路復(fù)雜度度量值實際上是為軟件測試的難 易程度提供了一個定量度量的方法, 同時也間接地表示了軟件 的可靠性。實驗表明，源程序中存在的錯誤數(shù)以及為了診斷和 糾正這些錯誤所需的時間與 McCabes路復(fù)雜度度量值有明顯 的關(guān)系。Myers建議,對于復(fù)合判定，例如(A= 0) Q (C= D) U( X='

5、A')算做三個判定。利用McCabe環(huán)路復(fù)雜度度量時，有幾點說明。環(huán)路復(fù)雜度取決于程序控制結(jié)構(gòu)的復(fù)雜度。當(dāng)程序 的分支數(shù)目或循環(huán)數(shù)目增加時其復(fù)雜度也增加 。環(huán)路復(fù)雜度 與程序中覆蓋的路徑條數(shù)有關(guān)。環(huán)路復(fù)雜度是可加的。例如，模塊A的復(fù)雜度為3 ,模 塊B的復(fù)雜度為4,則模塊A與模塊B的復(fù)雜度是7。 McCabe建議，對于復(fù)雜度超過10的程序，應(yīng)分成幾個 小程序，以減少程序中的錯誤 。 Walsh 用實例證實了這個建 議的正確性。他發(fā)現(xiàn)，在McCabe復(fù)雜度為10的附近，存在 出錯率的間斷躍變。 McCabe環(huán)路復(fù)雜度隱含的前提是：錯誤與程序的判定加 上例行子程序的調(diào)用數(shù)目成正比。而加工復(fù)

6、雜性、數(shù)據(jù)結(jié)構(gòu)、 錄入與打亂輸入卡片的錯誤可以忽略不計。三、Halstead的軟件科學(xué)Halstead 軟件科學(xué)研究確定計算機軟件開發(fā)中的一 些定量規(guī)律，它采用以下一組基本的度量值，這些度量值通常 在程序產(chǎn)生之后得出，或者在設(shè)計完成之后估算出。1. 程序長度，即預(yù)測的 Halstead 長度令 n1 表示程序中不同運算符（包括保留字）的個數(shù)，令 n2表示程序中不同運算對象的個數(shù)，令 H表示“程序長度”， 則有H= n1 Iog2n1 +n2 log2n2這里，H是程序長度的預(yù)測值，它不等于程序中語句個數(shù)在定義中，運算符包括：算術(shù)運算符賦值符（=或:=）數(shù)組操作符邏輯運算符分界符（，或；或 :）

7、子程序調(diào)用符關(guān)系運算符括號運算符循環(huán)操作符等特別地，成對的運算符，例如 “ BEGIN, END”、 FOR, TO ”、“REPEA,T UNTIL”、“WHILE, DO”、 IF, THEN, ELSE”、“ （ , ）”等都當(dāng)做單一運算符。運算對象包括變量名和常數(shù)2. 實際的 Halstead 長度設(shè)N1為程序中實際出現(xiàn)的運算符總個數(shù)，N2為程序中實 際出現(xiàn)的運算對象總個數(shù)，N為實際的Halstead長度，則有N =N1+N23. 程序的詞匯表Halstead 定義程序的詞匯表為不同的運算符種類數(shù)和不同的運算對象種類數(shù)的總和。若令 n 為程序的詞匯表，則有 n=n1+n2圖9-5-2是

8、用FORTRA語言寫出的交換排序的例子。圖 9-5-2 一個交換排序程序的例子 因此有：預(yù)測的詞匯量H= n1 log2n1+n2 log2n2 = 10 log210+7 Iog27 = 52.87實際的詞匯量 N= N1 +N2= 28+22= 50程序的詞匯表 n=n1+n2=10+7=174. 程序量 V 程序量V可用下式算得V= (N1+N2) Iog2(n1+ n2)它表明了程序在 “詞匯上的復(fù)雜性 ”。其最小值為V*= (2+n2*) Iog2(2+n2*)這里，2表明程序中至少有兩個運算符：賦值符“:=”和 函數(shù)調(diào)用符“f() ” , n2*表示輸入/輸出變量個數(shù)。對于圖 9-

9、5-2的例子，利用nl, N1, n2, N2,可以計算得：V= (28+22) log2(10+7) = 204等效的匯編語言程序的 V = 328。這說明匯編語言比 FORTRA語言需要更多的信息量(以 bit表示)。5. 程序量比率(語言的抽象級別)L = V*/ V或 L= (2 / n 1) (n2 / N2)這里，N2= n2 log2n2。它表明了一個程序的最緊湊形式 的程序量與實際程序量之比，反映了程序的效率。其倒數(shù)：D= 1/ L表明了實現(xiàn)算法的困難程度。有時，用 L表達語言的抽象 級別，即用L衡量在表達程序過程時的抽象程度。對于高級語 言，它接近于1,對于低級語言，它在01

10、之間。下面列出 的是根據(jù)經(jīng)驗得出的一些常用語言的語言抽象級別。語言L的平均值En glish Prose (英語散文)2.16PL/11.53ALGOL682.12FORTRAN1.14Assembler (匯編語言)0.886.程序員工作量E= V/ L7.程序的潛在錯誤Halstead度量可以用來預(yù)測程序中的錯誤。認為程序中可能存在的差錯應(yīng)與程序的容量成正比。因而預(yù)測公式為B= (N1+N2) Iog2(n1+n2) / 3000= V/ 3000B表示該程序的錯誤數(shù)。例如，一個程序?qū)?5個數(shù)據(jù)庫 項共訪問1300次，對150個運算符共使用了 1200次，那么預(yù) 測該程序的錯誤數(shù)：B= (

11、1300+1200) - log2(75+150) / 3000= 6.5即預(yù)測該程序中可能包含67個錯誤Halstead 的重要結(jié)論之一是： 程序的實際 Halstead 長度 N可以由詞匯表n算出。即使程序還未編制完成，也能預(yù)先算 出程序的實際 Halstead 長度 N， 雖然它沒有明確指出程序中 到底有多少個語句。這個結(jié)論非常有用。經(jīng)過多次驗證，預(yù)測的 Halstead 長 度與實際的 Halstead 長度是非常接近的。Halstead 度量是目前最好的度量方法。但它也有缺點：沒有區(qū)別自己編的程序 與別人編的程序。這是與實際 經(jīng)驗相違背的。這時應(yīng)將外部調(diào)用乘上一個大于 1 的的常數(shù)

12、Kf （應(yīng)在15之間，它與文檔資料的清晰度有關(guān)）。沒有考慮非執(zhí)行語句。補救辦法：在統(tǒng)計 n1、n2、N1、 N2時，可以把非執(zhí)行語句中出現(xiàn)的運算對象，運算符統(tǒng)計在內(nèi)。 在允許混合運算的語言中， 每種運算符必須與它的運算 對象相關(guān)。如果一種語言有整型、實型、雙精度型三種不同類 型的運算對象，則任何一種基本算術(shù)運算符（+、X、/） 實際上代表了 4 種運算符。如果語言中有 4 種不同類型的算術(shù)運算對象，那么每一種基本算術(shù)運算符實際上代表了種運算 符。在計算時應(yīng)考慮這種因數(shù)據(jù)類型而引起差異的情況。沒有注意調(diào)用的深度。Halstead公式應(yīng)當(dāng)對調(diào)用子程序 的不同深度區(qū)別對待。在計算嵌套調(diào)用的運算符和運算對象 時，應(yīng)乘上一個調(diào)用深度因子。這樣可以增大嵌套調(diào)用時的錯 誤預(yù)測率。沒有把不同類型的