程序復(fù)雜性度量

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

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

3、線性相關(guān)的。隨著程序的增大，出錯(cuò)率以非線性方式增長(zhǎng)。所以，代碼行度量法只是一 個(gè)簡(jiǎn)單的，估計(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)= m n + 2其中，V (G)是有向圖G中的環(huán)路個(gè)數(shù)，m是圖G中有向弧個(gè)數(shù)，n是圖G中結(jié)點(diǎn)個(gè)數(shù)。以圖9-5-1為例，其中，結(jié)點(diǎn)數(shù)n=

4、11,弧數(shù)m= 12,則有V (G)= m n+ 2= 12 11 + 2= 3。即McCabe環(huán)路復(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í)間與 McCabe環(huán)路復(fù)雜度度量值有明顯的關(guān) 系。Myers建議，對(duì)于復(fù)合判定，例如(A= 0) n (C= D) U (X=A)算做三 個(gè)判定。利用McCabe環(huán)路復(fù)

5、雜度度量時(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ù)雜性、數(shù)據(jù)結(jié)構(gòu)、錄入與打亂輸入卡片的錯(cuò)誤可以 忽略不計(jì)。三

6、、Halstead的軟件科學(xué)Halstead軟件科學(xué)研究確定計(jì)算機(jī)軟件開發(fā)中的一些定量規(guī)律，它采用以 下一組基本的度量值,這些度量值通常在程序產(chǎn)生之后得出,或者在設(shè)計(jì)完成 之后估算出。1程序長(zhǎng)度，即預(yù)測(cè)的Halstead長(zhǎng)度令 n1 表示程序中不同運(yùn)算符（包括保留字）的個(gè)數(shù),令n2 表示程序中不同運(yùn)算對(duì)象的個(gè)數(shù)，令H表示程序長(zhǎng)度”則有H= n1 Iog2 n1 +n 2log2 n2這里, H 是程序長(zhǎng)度的預(yù)測(cè)值,它不等于程序中語(yǔ)句個(gè)數(shù)。在定義中,運(yùn)算符包括：算術(shù)運(yùn)算符賦值符（二或：=）數(shù)組操作符邏輯運(yùn)算符分界符（，或；或:） 子程序調(diào)用符關(guān)系運(yùn)算符括號(hào)運(yùn)算符循環(huán)操作符等特別地,成對(duì)的運(yùn)算符,

7、例 如 “BEGIN,END”、 “FOR,TO”、 “REPEAT,UNT、I”L “WHILE,DO”、 “IF,THEN,ELS、E” “（ , ） ”等都當(dāng)做單一運(yùn)算符。運(yùn)算對(duì)象包括變量名和常數(shù)。實(shí)際的Halstead長(zhǎng)度設(shè)N1為程序中實(shí)際出現(xiàn)的運(yùn)算符總個(gè)數(shù)，N2為程序中實(shí)際出現(xiàn)的運(yùn)算對(duì) 象總個(gè)數(shù)，N為實(shí)際的Halstead長(zhǎng)度，則有N= N1+N2程序的詞匯表Halstead定義程序的詞匯表為不同的運(yùn)算符種類數(shù)和不同的運(yùn)算對(duì)象種類 數(shù)的總和。若令n為程序的詞匯表，則有n= n1+ n2圖9-5-2是用FORTRAN語(yǔ)言寫出的交換排序的例子。圖 9-5-2 一個(gè)交換排序程序的例子因此有

8、：預(yù)測(cè)的詞匯量H= n1 Iog2n1+ n2log2n2= 10 Iog210+7log27= 52.87實(shí)際的詞匯量 N= N1+N2= 28+22= 50程序的詞匯表n = n1+ n2= 10+7= 17程序量 V程序量V,可用下式算得V=(N1+N2)log2(n1+n2)它表明了程序在 “詞匯上的復(fù)雜性 ”。其最小值為 V*=(2+n2*) log2(2+n2*)這里, 2表明程序中至少有兩個(gè)運(yùn)算符：賦值符 “=:”和函數(shù)調(diào)用符 “f(),” 門2*表示輸入/輸出變量個(gè)數(shù)。對(duì)于圖 9-5-2的例子，利用n1, N1, n2, N2,可 以計(jì)算得： V=(28+22)log2(10+

9、7)=204等效的匯編語(yǔ)言程序的 V= 328。這說明匯編語(yǔ)言比FORTRAN語(yǔ)言需要更多 的信息量(以 bit 表示)。程序量比率(語(yǔ)言的抽象級(jí)別)L= V* /V或 L= (2 / n1) - (n2 / N2)這里，N2 = n2log2n2。它表明了一個(gè)程序的最緊湊形式的程序量與實(shí)際程 序量之比，反映了程序的效率。其倒數(shù)：D= 1 /L表明了實(shí)現(xiàn)算法的困難程度。有時(shí)，用 L表達(dá)語(yǔ)言的抽象級(jí)別，即用L衡 量在表達(dá)程序過程時(shí)的抽象程度。對(duì)于高級(jí)語(yǔ)言，它接近于 1，對(duì)于低級(jí)語(yǔ)言， 它在01之間。下面列出的是根據(jù)經(jīng)驗(yàn)得出的一些常用語(yǔ)言的語(yǔ)言抽象級(jí)別。語(yǔ)言L的平均值En glish Prose

10、(英語(yǔ)散文)PL/1ALGOL68FORTRANAssembler (匯編語(yǔ)言)程序員工作量E= V/程序的潛在錯(cuò)誤Halstead度量可以用來預(yù)測(cè)程序中的錯(cuò)誤。認(rèn)為程序中可能存在的差錯(cuò)應(yīng) 與程序的容量成正比。因而預(yù)測(cè)公式為B= (N1+N2) log2(n1+ n2)/ V003000B表示該程序的錯(cuò)誤數(shù)。例如，一個(gè)程序?qū)?75個(gè)數(shù)據(jù)庫(kù)項(xiàng)共訪問1300 次，對(duì) 1 50個(gè)運(yùn)算符共使用了 1200次，那么預(yù)測(cè)該程序的錯(cuò)誤數(shù)：B= (1300+1200) log2(75+150) =/635020.1.532.121.140.88即預(yù)測(cè)該程序中可能包含67個(gè)錯(cuò)誤。Halstead的重要結(jié)論之一是

11、：程序的實(shí)際 Halstead長(zhǎng)度N可以由詞匯表n 算出。即使程序還未編制完成，也能預(yù)先算出程序的實(shí)際 Halstead長(zhǎng)度N,雖 然它沒有明確指出程序中到底有多少個(gè)語(yǔ)句。這個(gè)結(jié)論非常有用。經(jīng)過多次驗(yàn)證，預(yù)測(cè)的Halstead長(zhǎng)度與實(shí)際的Halstead長(zhǎng)度是非常接近的。Halstead度量是目前最好的度量方法。但它也有缺點(diǎn)：沒有區(qū)別自己編的程序與別人編的程序。這是與實(shí)際經(jīng)驗(yàn)相違背的。這時(shí)應(yīng)將外部調(diào)用乘上一個(gè) 大于1的的常數(shù)Kf （應(yīng)在15之間，它與文檔資料的清晰度有關(guān)）。沒有考慮非執(zhí)行語(yǔ)句。補(bǔ)救辦法：在統(tǒng)計(jì) n1、n2、N1、N2時(shí)，可以把非 執(zhí)行語(yǔ)句中出現(xiàn)的運(yùn)算對(duì)象，運(yùn)算符統(tǒng)計(jì)在內(nèi)。在允許混合運(yùn)算的語(yǔ)言中，每種運(yùn)算符必須與它的運(yùn)算對(duì)象相關(guān)。如果一 種語(yǔ)言有整型、實(shí)型、雙精度型三種不同類型的運(yùn)算對(duì)象，則任何一種基本算 術(shù)運(yùn)算符（ +、 X /）實(shí)際上代表了 4種運(yùn)算符。如果語(yǔ)言中有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è)率。沒有把不