程序復(fù)雜性度量

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

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

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

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

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

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

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

8、用FORTRA語言寫出的交換排序的例子。圖 9-5-2 一個(gè)交換排序程序的例子 因此有：預(yù)測(cè)的詞匯量H= n1 log2n1+n2 log2n2 = 10 log210+7 Iog27 = 52.87實(shí)際的詞匯量 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表明程序中至少有兩個(gè)運(yùn)算符：賦值符“:=”和 函數(shù)調(diào)用符“f() ” , n2*表示輸入/輸出變量個(gè)數(shù)。對(duì)于圖 9-

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

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

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

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