《算法與數(shù)據(jù)結(jié)構(gòu)》第1章算法與程序ppt.ppt
《《算法與數(shù)據(jù)結(jié)構(gòu)》第1章算法與程序ppt.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第1章算法與程序ppt.ppt(93頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、算法與數(shù)據(jù)結(jié)構(gòu),第1章 算法與程序 第2章 常用數(shù)據(jù)結(jié)構(gòu) 第3章 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu) 第4章 樹和二叉樹 第5章 圖與網(wǎng) 第6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 第7章 檢索及基本算法 第8章 排序及基本算法,算法與數(shù)據(jù)結(jié)構(gòu),第1章 算法與程序,第1章 算法與程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的設(shè)計(jì)與評(píng)價(jià) 1.4 算法與程序,1.1 算法的基本概念,1.1.1 什么是算法 1.1.2 算法的基本特性,什么是算法,早在公元前300年左右出現(xiàn)的著名的歐幾里德算法,就描述了求解兩個(gè)整數(shù)的最大公因子的解題步驟。要求解的問題描述為:“給定兩個(gè)正整數(shù)m和n,求它們的最大公因子,即能同時(shí)整除m和n
2、的最大整數(shù)”。歐幾里德當(dāng)時(shí)給出的算法如下: 以n除m,并令所得余數(shù)為r(必有r 3、定義是: 一個(gè)算法,就是一個(gè)有窮規(guī)則的集合,其中之規(guī)則定義了一個(gè)解決某一特定類型問題的運(yùn)算序列。,什么是算法(續(xù)),算法的形式化定義如下所述: 算法是一個(gè)四元組,即(Q,I,,F(xiàn))。 其中: Q是一個(gè)包含子集I和的集合,它表示計(jì)算的狀態(tài); I表示計(jì)算的輸入集合; 表示計(jì)算的輸出集合; F表示計(jì)算的規(guī)則,它是由Q至它自身的函數(shù),且具有自反性,即對(duì)任何一個(gè)元素q Q,有F(q)=q。,什么是算法(續(xù)),一個(gè)算法是對(duì)于任何的輸入元素x,都在有窮步驟內(nèi)終止的一個(gè)計(jì)算方法。 在算法的形式化定義中,對(duì)任何一個(gè)元素xI,x均滿足性質(zhì) x0=x,xk+1=F(xk),(k0) 該性質(zhì)表示任何一個(gè)輸入元素 4、x均為一個(gè)計(jì)算序列,即x0,x1,x2,,xk;該序列在第k步結(jié)束計(jì)算。,1.1 算法的基本概念,1.1.1 什么是算法 1.1.2 算法的基本特性,算法的基本特性,輸入(Input) 輸出(Output) 確定性(Definiteness) 有窮性(Finiteness) 有效性(Effectiveness),第1章 算法與程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的設(shè)計(jì)與評(píng)價(jià) 1.4 算法與程序,1.2 算法的表示,1.2.1 自然語言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語言表示,自然語言表示,自然語言即人們?nèi)粘?/p>
5、使用的語言,如漢語、英語、日語、法語、德語等等。使用自然語言描述算法,人們比較容易接受和理解。如前面的歐幾里德算法就是用自然語言描述的。然而,自然語言也具有許多缺點(diǎn),在使用自然語言描述算法時(shí)一定要引起注意: 自然語言存在著歧義性,容易導(dǎo)致算法的不確定性; 自然語言容易冗長(zhǎng),使得描述不夠簡(jiǎn)潔; 自然語言的表示形式是順序的,描述分支選擇和轉(zhuǎn)移時(shí)不夠直觀; 自然語言與計(jì)算機(jī)程序設(shè)計(jì)語言的差別較大,不易轉(zhuǎn)換為程序。,1.2 算法的表示,1.2.1 自然語言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語言表示,流程圖表示,流程圖是描述算法的圖形工具,它采 6、用如下所示的一組圖形符號(hào)來表示算法:,起止框,表示算法的開始或結(jié)束;只有一個(gè)入口或一個(gè)出口。 輸入輸出框,表示算法中數(shù)據(jù)信息的輸入和輸出;有一個(gè)入口和一個(gè)出口。 判斷框,表示條件判斷;有一個(gè)入口和多個(gè)出口。 處理框,表示算法中的一個(gè)(或一組)運(yùn)算或處理;有一個(gè)入口和一個(gè)出口。 流程線,表示算法中各步驟之間的次序關(guān)系。 連接點(diǎn),表示算法中的連接位置,主要用于同一算法在不同頁描述時(shí)的接續(xù)等情況。 注釋框,用于對(duì)算法中某些操作的注釋說明。,流程圖表示舉例,歐幾里德算法的流程圖描述如圖1-1所示,流程圖表示(續(xù)),同自然語言相比,用流程圖描述算法直觀,可以一目了然;算法步驟間用流程線連接,次序關(guān)系清楚 7、,容易理解;可以很方便地表示順序、選擇和循環(huán)結(jié)構(gòu),不依賴于任何計(jì)算機(jī)和計(jì)算機(jī)程序設(shè)計(jì)語言,有利于不同環(huán)境下的程序設(shè)計(jì)。但是,流程圖也還存在一些缺點(diǎn),諸如: 不易于表示算法的層次結(jié)構(gòu); 不易于表示數(shù)據(jù)結(jié)構(gòu)和模塊調(diào)用關(guān)系等重要信息; 容易使人過早地考慮算法的控制流程,而忽視算法的全局結(jié)構(gòu); 用流程線代表控制流,控制轉(zhuǎn)移隨意性較大。若對(duì)流程線的使用不加限制,隨著求解問題規(guī)模和復(fù)雜度的增加,流程圖會(huì)變得很復(fù)雜,使人難以閱讀、理解和修改,從而使算法的可靠性難以保證。,1.2 算法的表示,1.2.1 自然語言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語言 8、表示,NS圖表示,為了克服傳統(tǒng)流程圖的缺點(diǎn),1973年美國學(xué)者納斯(I.Nassi)和施內(nèi)德曼(B.Shneiderman)提出了一種表示算法的較好工具N-S圖。 它獨(dú)立于任何計(jì)算機(jī)和計(jì)算機(jī)語言,又能很方便地轉(zhuǎn)換為計(jì)算機(jī)語言程序; 它去掉了流程線全部用矩形方框來描述,限制了算法流程轉(zhuǎn)移控制的隨意性,又節(jié)省了篇幅; 它很容易表示算法中的嵌套關(guān)系和模塊中的層次關(guān)系,功能域可以從框圖中直接反映出來; 它仍是圖形工具,閱讀起來直觀、明確、容易理解。,NS圖表示(續(xù)),N-S圖的基本圖形符號(hào)如下:,順序結(jié)構(gòu),由兩個(gè)或多個(gè)矩形框組成。其中A和B可以是基本操作,也可以是其它基本結(jié)構(gòu)(如選擇結(jié)構(gòu),循環(huán)結(jié)構(gòu))。 9、 選擇結(jié)構(gòu),當(dāng)條件P成立時(shí)執(zhí)行操作A,否則執(zhí)行操作B。 當(dāng)型循環(huán)結(jié)構(gòu)。當(dāng)條件P成立時(shí)反復(fù)執(zhí)行操作A,直到條件P不成立時(shí)止。 直到型循環(huán)結(jié)構(gòu)。反復(fù)執(zhí)行操作A,直到條件P成立時(shí)止。,NS圖表示舉例,由于N-S圖象一個(gè)多層的盒子,所以也稱作盒圖。用N-S圖表示歐幾里德算法如圖1-2所示。,1.2 算法的表示,1.2.1 自然語言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語言表示,偽代碼表示,偽代碼是介乎于自然語言和計(jì)算機(jī)程序語言之間的一種表示算法的工具。 它用文字和符號(hào)描述問題的求解方法和步驟而不使用圖形符號(hào)。 如同一篇文章自上而下書寫,每行寫一個(gè) 10、基本操作,而用若干行寫出一個(gè)基本結(jié)構(gòu)。 因而書寫方便,格式緊湊,清晰易讀好理解,也更容易轉(zhuǎn)化為某一計(jì)算機(jī)程序語言表示的程序。 和圖形工具相比較,便于修改,但直觀性能較弱。,偽代碼表示(續(xù)),下面,我們給出歐幾里德算法的一種偽代碼描述如下: Begin(算法開始) Read(m,n) m mod nr while r0 do nm rn m mod nr write(n) End(算法結(jié)束),1.2 算法的表示,1.2.1 自然語言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語言表示,程序語言表示 11、,計(jì)算機(jī)程序設(shè)計(jì)語言,是計(jì)算機(jī)能夠接受、理解和執(zhí)行的算法描述工具。 計(jì)算機(jī)不能直接識(shí)別自然語言、流程圖、N-S圖和偽代碼等工具描述的算法,而設(shè)計(jì)算法的目的就是要用計(jì)算機(jī)來解決問題,算法最終都要用某一具體的計(jì)算機(jī)程序設(shè)計(jì)語言來表示。 從這個(gè)意義上講,流程圖、N-S圖和偽代碼都僅僅是為了求解問題而設(shè)計(jì)算法時(shí)的輔助工具。 為了更好更準(zhǔn)確地描述算法,人們使用圖形或表格還創(chuàng)造了許多專用的算法設(shè)計(jì)輔助工具,如PAD圖、判定表、數(shù)據(jù)流圖、Warnier-rr圖等等。,程序語言表示(續(xù)),和自然語言一樣,計(jì)算機(jī)程序設(shè)計(jì)語言也是串行的描述,很不直觀。 對(duì)于較復(fù)雜的問題,人們很難用計(jì)算機(jī)程序設(shè)計(jì)語言直接寫出程序。 12、 所以在算法設(shè)計(jì)階段,一般是先采用某個(gè)專用的輔助工具來描述算法,在算法設(shè)計(jì)好之后,再把它轉(zhuǎn)化為某一具體程序設(shè)計(jì)語言描述的程序。,程序語言表示(續(xù)),作為例子,下面我們給出歐幾里德算法的C語言描述如下: #include ”stdio.h” main() int m,n,r; printf(“請(qǐng)輸入兩個(gè)正整數(shù):”); scanf(“%d%d”, ,運(yùn)行結(jié)果: 請(qǐng)輸入兩個(gè)正整數(shù):56 32 56和32的最大公約數(shù)是:8,第1章 算法與程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的設(shè)計(jì)與評(píng)價(jià) 1.4 算法與程序,1.3 算法的設(shè)計(jì)與評(píng)價(jià),1.3.1 評(píng)價(jià)算法的 13、標(biāo)準(zhǔn) 1.3.2 算法的環(huán)路復(fù)雜度 1.3.3 算法的時(shí)空效率 1.3.4 常見的算法設(shè)計(jì)方法,評(píng)價(jià)算法的標(biāo)準(zhǔn),評(píng)價(jià)一個(gè)算法優(yōu)劣的五條標(biāo)準(zhǔn): 正確性 可讀性 健壯性 高效性 簡(jiǎn)潔性 一個(gè)好的算法是滿足這五條標(biāo)準(zhǔn)要求的算法。,評(píng)價(jià)算法的“正確性”標(biāo)準(zhǔn),所設(shè)計(jì)出來的算法要能夠正確求解給定的問題。 這就要求算法中的每一個(gè)步驟的描述是準(zhǔn)確無歧義的,并且是可以執(zhí)行的; 要求算法能夠滿足問題要求,并在有限步驟內(nèi)獲得結(jié)果; 否則就不具備正確性要求,更談不上解決給定的實(shí)際問題了。 算法要能經(jīng)得起一切可能的輸入數(shù)據(jù)的考驗(yàn)。,評(píng)價(jià)算法的“正確性”標(biāo)準(zhǔn)(續(xù)),在將算法用程序語言表示為特定語言的程序后還必須注意: 程 14、序中不含有語法錯(cuò)誤; 對(duì)于一切合法的輸入數(shù)據(jù),程序能夠產(chǎn)生滿足要求的輸出結(jié)果; 對(duì)于一切非法的輸入數(shù)據(jù),程序能夠得出滿足規(guī)格說明的結(jié)果; 對(duì)于精心選擇的,甚至是帶有刁難性的典型測(cè)試數(shù)據(jù),程序都有滿足要求的輸出結(jié)果。,評(píng)價(jià)算法的“可讀性”標(biāo)準(zhǔn),表示出來的算法要能夠方便地供人們閱讀、理解和交流。 算法的可讀性好是保證正確性的前提,良好的可讀性有利于人們理解算法思想,減少出錯(cuò)機(jī)會(huì),便于檢查和修改。 可適當(dāng)?shù)卦黾幼⑨?,增?qiáng)算法或程序的可讀性。,評(píng)價(jià)算法的“健壯性”標(biāo)準(zhǔn),算法對(duì)意外情況的反映能力要強(qiáng)。 當(dāng)輸入數(shù)據(jù)非法、0作除數(shù)、負(fù)數(shù)開平方等,算法應(yīng)能做出相應(yīng)的處理,給出錯(cuò)誤信息或終止算法執(zhí)行,避免產(chǎn)生錯(cuò) 15、誤的或莫明其妙的輸出結(jié)果。,評(píng)價(jià)算法的“高效性”標(biāo)準(zhǔn),算法的執(zhí)行效率要高。 算法的效率可分為時(shí)間效率和空間效率。 時(shí)間效率是通過該算法轉(zhuǎn)化的程序在計(jì)算機(jī)上運(yùn)行的時(shí)間耗費(fèi)來確定,在算法設(shè)計(jì)與分析階段用執(zhí)行基本操作的次數(shù)(是問題規(guī)模的函數(shù))相對(duì)于問題規(guī)模的漸近階來表示。 空間效率主要考慮除存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)之外的輔助存儲(chǔ)空間。一個(gè)高效算法是指執(zhí)行算法耗費(fèi)時(shí)間少,使用輔助存儲(chǔ)空間小的算法。,評(píng)價(jià)算法的“簡(jiǎn)潔性 ”標(biāo)準(zhǔn),所設(shè)計(jì)出來的算法要盡可能地簡(jiǎn)潔。 對(duì)于同一問題所設(shè)計(jì)的不同算法,越簡(jiǎn)潔明了的越好。 越簡(jiǎn)潔的算法可讀性越好,越易于理解、編碼和調(diào)試、測(cè)試,越受人們歡迎。,評(píng)價(jià)算法的標(biāo)準(zhǔn)(續(xù)),在評(píng)價(jià)一個(gè)算法 16、時(shí),要對(duì)這五個(gè)方面綜合考慮,不要片面追求某一指標(biāo)。 有些指標(biāo)之間往往是相互制約的,如時(shí)間效率與空間效率,簡(jiǎn)潔性與高效性等等; 要學(xué)會(huì)針對(duì)具體問題要求和軟硬件實(shí)現(xiàn)環(huán)境進(jìn)行綜合平衡,設(shè)計(jì)出滿足需要的好算法。,1.3 算法的設(shè)計(jì)與評(píng)價(jià),1.3.1 評(píng)價(jià)算法的標(biāo)準(zhǔn) 1.3.2 算法的環(huán)路復(fù)雜度 1.3.3 算法的時(shí)空效率 1.3.4 常見的算法設(shè)計(jì)方法,算法的環(huán)路復(fù)雜度,算法的復(fù)雜性很大程度上取決于控制流程的復(fù)雜性。單一的順序結(jié)構(gòu)最簡(jiǎn)單; 循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu)所構(gòu)成的環(huán)路越多算法就越復(fù)雜。 基于這一種觀點(diǎn),針對(duì)算法的流程圖表示,我們先介紹算法的環(huán)路復(fù)雜度的概念和度量方法。,算法的環(huán)路復(fù)雜度(續(xù)),算法( 17、或程序)的環(huán)路復(fù)雜度度量方法,以圖論為工具,先畫出程序圖,然后用該程序圖的環(huán)路作為算法(或程序)復(fù)雜性的度量值。 所謂程序圖可以看成是退化了的流程圖,也就是把算法(或程序)流程圖中的每個(gè)處理框都退化成為一個(gè)點(diǎn),原來連接不同框之間的流程線變成連接不同點(diǎn)的有向弧,這樣得到的有向圖稱之為程序圖。 程序圖是連通圖,這是因?yàn)閺乃惴鞒痰娜肟邳c(diǎn)總是能夠到達(dá)圖中的任何一個(gè)結(jié)點(diǎn);如果我們?cè)僭黾右粭l由出口到達(dá)入口的虛弧,則從圖中任何一個(gè)結(jié)點(diǎn)出發(fā)都可以到達(dá)其它所有結(jié)點(diǎn),使得程序圖變?yōu)閺?qiáng)連通的有向圖。,算法的環(huán)路復(fù)雜度舉例,例如圖1-1所示的歐幾里德算法的流程圖所對(duì)應(yīng)的程序圖如圖1-3所示。,算法的環(huán)路復(fù)雜度的計(jì)算 18、方法,強(qiáng)連通圖中線性無關(guān)的環(huán)路個(gè)數(shù)我們可以用如下的公式確定: V(G)=e-n+p 其中: V(G)是圖G中環(huán)路的個(gè)數(shù); e是圖G中有向弧的條數(shù),包括由出口到入口增加的一條虛??; n是圖G中結(jié)點(diǎn)的個(gè)數(shù); p是圖G中連通分量的個(gè)數(shù),對(duì)于連通圖而言p恒為1。,環(huán)路復(fù)雜度的計(jì)算方法舉例,例1:前述的歐幾里德算法的程序圖(圖1-3)中,有8條有向弧和7個(gè)結(jié)點(diǎn),由該公式可以確定其環(huán)路復(fù)雜度如下: V(G)=8-7+1=2,例2:如圖1-4所示的程序圖中, 有11條弧和7個(gè)結(jié)點(diǎn),由該公式 可如下確定其環(huán)路復(fù)雜度: V(G)=11-7+1=5,算法的環(huán)路復(fù)雜度的計(jì)算方法(續(xù)),除了應(yīng)用上述的公式 19、法計(jì)算之外,還有如下的兩種方法可以用來確定程序圖的環(huán)路復(fù)雜度: 觀察法,即觀察強(qiáng)連通的程序圖在平面上所圍成的獨(dú)立區(qū)域的個(gè)數(shù)。如圖1-3中由有向?。ê摶?,下同)和結(jié)點(diǎn)圍成的獨(dú)立區(qū)域有兩個(gè),即環(huán)路數(shù)為2,環(huán)路復(fù)雜度為2;而圖1-4中的獨(dú)立區(qū)域有五個(gè),環(huán)路數(shù)為5,環(huán)路復(fù)雜度為5。,算法的環(huán)路復(fù)雜度的計(jì)算方法(續(xù)),利用判定語句計(jì)算法,即把程序圖中所有出現(xiàn)的分支結(jié)點(diǎn)處所需要的判定的總個(gè)數(shù)加起來再加1。每一個(gè)分支結(jié)點(diǎn)處所需要的判定數(shù)為該結(jié)點(diǎn)分支數(shù)(即出度)減1,即二路分支需要一個(gè)判定,三路分支需要兩個(gè)判定,依此類推。如圖1-3中只有一個(gè)結(jié)點(diǎn)(第四個(gè))是分支結(jié)點(diǎn)且為二路分支,故所需要的判定為一個(gè),其環(huán)路 20、復(fù)雜度(即環(huán)路數(shù))為2;而圖1-4中有兩個(gè)結(jié)點(diǎn)(上數(shù)第二個(gè)和左下結(jié)點(diǎn))是分支結(jié)點(diǎn)且結(jié)點(diǎn)都為三路分支,故所需的判定為2+2=4個(gè),其環(huán)路復(fù)雜度為5。,算法的環(huán)路復(fù)雜度(續(xù)),算法的環(huán)路復(fù)雜度越高,說明算法的控制越復(fù)雜,在轉(zhuǎn)化為程序時(shí)的難度就越大,轉(zhuǎn)化后的程序測(cè)試難度也就越大問題越多。在設(shè)計(jì)算法時(shí),一般地應(yīng)控制模塊的環(huán)路復(fù)雜度在10以內(nèi)為宜。 環(huán)路復(fù)雜度的度量方法的最大優(yōu)點(diǎn)在于它的簡(jiǎn)明性,只要知道算法中的判定個(gè)數(shù)即可。然而它也有許多不足之處,如沒有區(qū)分不同類型控制流的不同復(fù)雜性(如選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)之間,嵌套選擇結(jié)構(gòu)和多選擇結(jié)構(gòu)之間的不同復(fù)雜性)等。在評(píng)價(jià)和度量算法復(fù)雜性時(shí),可根據(jù)實(shí)際需要結(jié)合其它 21、方法一塊使用。,1.3 算法的設(shè)計(jì)與評(píng)價(jià),1.3.1 評(píng)價(jià)算法的標(biāo)準(zhǔn) 1.3.2 算法的環(huán)路復(fù)雜度 1.3.3 算法的時(shí)空效率 1.3.4 常見的算法設(shè)計(jì)方法,算法的時(shí)空效率,如果算法是用N-S圖、偽代碼、程序語言或其它方式表示的,要度量其環(huán)路復(fù)雜度需要先把它們的表示轉(zhuǎn)化為流程圖表示,然后把流程圖退化為程序圖再確定其環(huán)路數(shù)。 環(huán)路復(fù)雜度是一種定量地評(píng)價(jià)算法復(fù)雜度的方法。 下面我們?cè)俳榻B一種適應(yīng)面更廣泛的定性評(píng)價(jià)算法復(fù)雜度的方法,即大O方法。,算法的時(shí)空效率(續(xù)),執(zhí)行一個(gè)算法的時(shí)間代價(jià),是指將該算法轉(zhuǎn)化為程序后在計(jì)算機(jī)上運(yùn)行的時(shí)間耗費(fèi),即算法中每條語句在計(jì)算機(jī)上執(zhí)行的時(shí)間總和,大致上可以認(rèn)為它 22、等于計(jì)算機(jī)執(zhí)行一種基本操作(如賦值運(yùn)算、比較運(yùn)算、移動(dòng)操作等)所需的時(shí)間與算法中進(jìn)行基本操作總次數(shù)的乘積。 而每條語句的執(zhí)行時(shí)間則應(yīng)該是執(zhí)行該語句一次所需的時(shí)間與該語句執(zhí)行的次數(shù)(也稱之為頻度)的乘積。 某條語句執(zhí)行一次所需的時(shí)間一般地是隨機(jī)器而異的,取決于具體機(jī)器的性能、速度和編譯代碼的質(zhì)量,是由機(jī)器本身的軟、硬件環(huán)境所決定的,與算法無關(guān)。所以,我們可以假設(shè)執(zhí)行每條語句所需的時(shí)間均為單位時(shí)間。 因此,對(duì)算法執(zhí)行時(shí)間的討論就可以轉(zhuǎn)化為對(duì)算法中所有語句的執(zhí)行次數(shù)(即頻度)的討論。,大O方法計(jì)算舉例,兩個(gè)n*n矩陣相乘的算法描述如下: for(i=1;i<=n;i++) /* n+1次 */ 23、 for(j=1;j<=n;j++) /* n(n+1)次 */ cij=0; /* n2次 */ for(k=1;k<=n;k++) /* n2(n+1)次 */ cij=cij+aik*bkj; /* n3次 */ ,大O方法計(jì)算舉例(續(xù)),其中,每一條語句的頻度說明在注釋中。我們把算法所耗費(fèi)的時(shí)間定義為該算法中每條語句的頻度之和,則該算法的時(shí)間耗費(fèi)T(n)可表示為 T(n)=2n3+3n2+2n+1 顯然,它是矩陣的階(該問題的規(guī)模)n的函數(shù)。并且當(dāng)n時(shí),T(n)/n32。這表示當(dāng)n趨于無窮大時(shí),T(n)與n3是同階函數(shù)或者說是同量級(jí)的。引入大O記號(hào) 24、可記作 T(n)=O(n3),時(shí)間復(fù)雜度,引入大O記號(hào)表示的算法的時(shí)間耗費(fèi)T(n)通常稱之為算法的時(shí)間復(fù)雜度,如矩陣相乘算法的時(shí)間復(fù)雜度為O(n3)。 這種時(shí)間復(fù)雜度的大O表示法,實(shí)質(zhì)上是把算法的基本操作總數(shù)表示為問題規(guī)模n的函數(shù)之后,尋找出當(dāng)問題規(guī)模n趨于無窮大時(shí)該函數(shù)的同階最簡(jiǎn)形式即漸近性態(tài)下的同階最簡(jiǎn)函數(shù),有時(shí)也簡(jiǎn)稱之為漸近階。 問題的規(guī)模是指算法中要處理的數(shù)據(jù)量的規(guī)模,通常用一個(gè)整型量n來表示。對(duì)于求解不同的問題,規(guī)模n具有不同的值。,時(shí)間復(fù)雜度(續(xù)),時(shí)間復(fù)雜性的漸近階表示,是對(duì)算法時(shí)間性能優(yōu)劣的宏觀定性評(píng)價(jià)。 例如,為了求解同一問題所設(shè)計(jì)的兩個(gè)不同的算法A1和A2,其時(shí)間耗費(fèi) 25、分別為T1(n)=40n2和T2(n)=5n3;顯然當(dāng)問題規(guī)模nT2(n),算法A2比A1時(shí)間花費(fèi)少;利用漸近階表示的時(shí)間復(fù)雜度O(n2)和O(n3)反映了對(duì)這兩個(gè)算法時(shí)間性能優(yōu)劣的宏觀定性評(píng)價(jià)結(jié)論。 由于是宏觀的定性評(píng)價(jià),算法中頻度最大的語句的頻度,與算法中每條語句頻度的和T(n)是同階函數(shù); 所以人們?cè)谟?jì)算算法時(shí)間復(fù)雜度時(shí),往往只需考慮算法中頻度最大的語句的頻度就可以了。,時(shí)間復(fù)雜度計(jì)算舉例,例如對(duì)于下面的程序段: x=0; for(i=1;i 26、大的語句最內(nèi)層循環(huán)的循環(huán)體語句x++,它的執(zhí)行次數(shù)是 由于n3是它的漸近性態(tài)下的同階最簡(jiǎn)函數(shù),可得上述程序段的時(shí)間復(fù)雜度為T(n)= O(n3)。,簡(jiǎn)明實(shí)用的程序分析法則,執(zhí)行一條基本操作如讀寫或賦值語句等,需要O(1)的時(shí)間花費(fèi)。 對(duì)于順序結(jié)構(gòu),需要執(zhí)行一系列語句,所用時(shí)間用求和準(zhǔn)則估計(jì)。 對(duì)于選擇結(jié)構(gòu)如if語句,主要時(shí)間耗費(fèi)是執(zhí)行then子句或else子句所用的時(shí)間;此外,檢驗(yàn)條件還需用O(1)的時(shí)間。多選擇結(jié)構(gòu)的時(shí)間耗費(fèi)與if語句類同。 對(duì)于循環(huán)結(jié)構(gòu),執(zhí)行時(shí)間為多次迭代中循環(huán)體的執(zhí)行和檢驗(yàn)循環(huán)條件的耗時(shí),常用乘法準(zhǔn)則估計(jì)。 對(duì)于復(fù)雜算法,可以將它分成幾個(gè)容易估算的部分分別估計(jì),然后利用求 27、和準(zhǔn)則和乘法準(zhǔn)則計(jì)算整個(gè)算法的時(shí)間復(fù)雜度。,簡(jiǎn)明實(shí)用的程序分析法則(續(xù)),大O下的求和準(zhǔn)則 若T1(m)=O(f(m)),T2(n)=O(g(n)) (不相同問題規(guī)模時(shí)) 則T1(m)+ T2(n)=O(f(m)+g(n)) 若T1(n)=O(f(n)),T2(n)=O(g(n)) (相同問題規(guī)模時(shí)) 則T1(n)+ T2(n)=O(max(f(n), g(n))) 若g(n) =O(f(n)) (特殊運(yùn)算規(guī)則) 則O(f(n)) +O(g(n))=O(f(n)),簡(jiǎn)明實(shí)用的程序分析法則(續(xù)),大O下的乘法準(zhǔn)則 若T1(m)=O(f(m)),T2(n)=O(g(n) 28、) (不相同問題規(guī)模時(shí)) 則T1(m)*T2(n)=O(f(m)*g(n)) 若T1(n)=O(f(n)),T2(n)=O(g(n)) (相同問題規(guī)模時(shí)) 則T1(n)*T2(n)=O(f(n)*g(n)) 若c是一個(gè)正常數(shù) (特殊運(yùn)算規(guī)則) 則O(cf(n))=O(f(n)),程序分析法則舉例,如對(duì)前述的矩陣相乘算法,它是三層嵌套的循環(huán)結(jié)構(gòu),我們可以從最內(nèi)層循環(huán)的循環(huán)體開始分析: 是賦值語句,與問題規(guī)模無關(guān),時(shí)間復(fù)雜度為常數(shù)階O(1),即T5(n)=O(1); 對(duì)于第條語句,T4(n)=O(n),它與第條語句是循環(huán)關(guān)系應(yīng)該用乘法準(zhǔn)則,即T4(n)*T5(n)=O(1*n)=O 29、(n); 對(duì)于第條語句T3(n)=O(1),它與第、是順序結(jié)構(gòu)應(yīng)該用求和準(zhǔn)則,即T3(n)+T4(n)* T5(n)=O(max(1,n))=O(n); 第條語句其T2(n)=O(n),到是它的循環(huán)體適用乘法準(zhǔn)則,故有T2(n)*(T3(n)+T4(n)*T5(n))=O(n*n)=O(n2); 第條語句的耗時(shí)T1(n)=O(n),到是它的循環(huán)體適用乘法準(zhǔn)則,所以有T1(n)*(T2(n)*(T3(n)+T4(n)*T5(n)))=O(n* n2)=O(n3)。,時(shí)間復(fù)雜度(續(xù)),利用這組程序分析法則可得矩陣相乘算法的時(shí)間復(fù)雜度為T(n)=O(n3),它與我們?cè)谇懊嬗盟姓Z句執(zhí)行頻度的總和關(guān)于 30、問題規(guī)模的函數(shù)表達(dá)后求漸近階得出的結(jié)果一致,但卻省去了計(jì)算所有語句執(zhí)行頻度總和的麻煩。 實(shí)際上,算法或程序的執(zhí)行時(shí)間不僅依賴于所求解問題的規(guī)模,還與它所處理的數(shù)據(jù)的狀態(tài)有關(guān)。 一般在不做任何說明的情況下,討論其時(shí)間復(fù)雜度是指在最壞情況下的時(shí)間復(fù)雜度,通??捎涀鱐max(n);有時(shí)還要討論其平均情況下的時(shí)間復(fù)雜度Tavg(n)。,空間復(fù)雜度,衡量一個(gè)算法優(yōu)劣的另一個(gè)因素是空間代價(jià),即執(zhí)行由算法轉(zhuǎn)化的程序時(shí)所占用存儲(chǔ)空間的大小。為了執(zhí)行算法所占用的存儲(chǔ)空間包括如下三個(gè)方面: 為了在計(jì)算機(jī)上存儲(chǔ)程序本身所占用的存儲(chǔ)空間。 算法或程序中的輸入和輸出數(shù)據(jù)所占用的存儲(chǔ)空間。 算法或程序在執(zhí)行過程中臨時(shí)占用 31、的存儲(chǔ)空間。這部分空間是與算法本身密切相關(guān)的,因算法設(shè)計(jì)的不同而異,是我們討論算法的空間代價(jià)時(shí)所要著重討論的方面。 度量一個(gè)算法或程序在執(zhí)行過程中所花費(fèi)的額外存儲(chǔ)開銷(即臨時(shí)存儲(chǔ)工作單元)的大小也是用大O方法,度量的結(jié)果稱之為算法的空間復(fù)雜度。空間復(fù)雜度和時(shí)間復(fù)雜度一樣,也是用相對(duì)于問題規(guī)模函數(shù)的漸近階形式給出,如O(1)、O(n)等。,時(shí)(空)間復(fù)雜度,常見的時(shí)間(或空間)復(fù)雜度有: 常數(shù)階O(1) 對(duì)數(shù)階O(log2n) 線性階O(n) 線性對(duì)數(shù)階O(nlog2n) 平方階O(n2) 立方階O(n3) 指數(shù)階O(2n) 指數(shù)階的算法效率極低,當(dāng)問題規(guī)模n稍大時(shí)就無法使用。,1.3 算法的設(shè) 32、計(jì)與評(píng)價(jià),1.3.1 評(píng)價(jià)算法的標(biāo)準(zhǔn) 1.3.2 算法的環(huán)路復(fù)雜度 1.3.3 算法的時(shí)空效率 1.3.4 常見的算法設(shè)計(jì)方法,常見的算法設(shè)計(jì)方法,為了獲得有效的算法,必須了解一些解題的基本思想和方法。對(duì)于許多問題,只要仔細(xì)分析了數(shù)據(jù)對(duì)象后,相應(yīng)的處理方法就有了;對(duì)于有些問題則不然。然而,作為探尋問題求解思路的基本思想和方法,對(duì)于任何算法設(shè)計(jì)都是有用的。下面我們簡(jiǎn)要介紹一些常用的算法設(shè)計(jì)方法和技術(shù): 窮舉法 迭代法 遞推法 遞歸法 回溯法 貪婪法 分治法,1.窮舉法,窮舉法亦稱作枚舉法。它的基本思想是: 首先根據(jù)求解問題的部分條件確定答案的大致范圍,即列舉出解的所有可能的情況; 然后在此范圍內(nèi) 33、對(duì)所有可能的情況逐一驗(yàn)證,若某個(gè)情況經(jīng)過驗(yàn)證符合問題條件則為一個(gè)解,若全部情況驗(yàn)證后均不符合題目條件則問題無解,從而得出求解問題的完整解。 例如要找出200到500之間的所有素?cái)?shù),我們只要對(duì)這個(gè)范圍內(nèi)的每一個(gè)數(shù)逐個(gè)用素?cái)?shù)的定義去判斷就行了。 窮舉法的特點(diǎn)是算法簡(jiǎn)單,但有時(shí)運(yùn)算量大效率較低。在可以確定解的取值范圍,但一時(shí)又找不到更好的算法時(shí),就可以使用窮舉法求解。,2.迭代法,迭代法的基本思想是,由一個(gè)量的原值求出它的新值,不斷地再用新值替代原值求出它的下一個(gè)新值,直到得到滿意的解。新值與原值之間存在一定的關(guān)系,這種關(guān)系可以用一個(gè)公式來表示,稱之為迭代公式。 迭代法主要用于那些很難用或無法用解析 34、法求解的一類計(jì)算問題,如高次方程和超越方程等;使得復(fù)雜問題的求解過程,轉(zhuǎn)化為相對(duì)較簡(jiǎn)單的迭代算式的重復(fù)執(zhí)行過程,用數(shù)值方法求出問題的近似解。,迭代法(續(xù)),使用迭代法構(gòu)造這一類問題求解算法的基本方法是: 先確定一個(gè)收斂性能好(即收斂速度快)的迭代公式,選取解的一個(gè)近似值(即迭代初值)和解的精度要求(即允許的最大誤差范圍), 然后用循環(huán)處理實(shí)現(xiàn)迭代過程,終止循環(huán)的條件是前后兩次得到的近似值之差的絕對(duì)值小于解的精度要求,并認(rèn)為最后一次得到的近似解為問題的解。 這種迭代方法稱作逼近迭代,如著名的牛頓迭代法就是這種逼近迭代方法。 此外,精確值的計(jì)算也可以使用迭代法。例如計(jì)算s=1+2+3++1000, 35、可選取迭代公式s+is和迭代初值0(即0s)。,3.遞推法,遞推法是從前面的一些量推出后面的一些量的一種方法,它從已知的初始條件出發(fā),逐次推出所需要求解的各中間結(jié)果和最終結(jié)果。 遞推過程往往表現(xiàn)為迭代,即由一些量的原值推出它的新值,不斷地用新值替代原值推出下一個(gè)新值,直到推出最終結(jié)果,新值與原值之間的關(guān)系用遞推公式表示。 例如Fibonacci數(shù)列存在著遞推關(guān)系 F(1)=1,F(xiàn)(2)=1,F(xiàn)(n)= F(n-1)+ F(n-2) (n2),遞推法(續(xù)),需要求出Fibonacci數(shù)列中某一項(xiàng)的值,利用遞推公式逐步求出F(3),F(xiàn)(4)直到求出該項(xiàng)的值,也許有人會(huì)說,如果使用通項(xiàng)公式計(jì)算豈不更 36、方便嗎?事實(shí)上,有些遞推問題的通項(xiàng)公式是很難找出的,即使找出通項(xiàng)公式計(jì)算也不一定簡(jiǎn)便。如Fibonacci數(shù)列的通項(xiàng)公式為 顯而易見,找出這個(gè)通項(xiàng)公式不易,利用它計(jì)算F(n)也相當(dāng)費(fèi)力。相反地,若利用遞推初值和遞推公式計(jì)算F(n)就容易和方便多了。,4.遞歸法,如果一個(gè)過程直接或間接地調(diào)用它自身,則稱該過程是遞歸的;直接調(diào)用自身稱作直接遞歸,間接調(diào)用自身則稱作間接遞歸。 遞歸是構(gòu)造算法的一種基本方法,它將一個(gè)復(fù)雜問題歸結(jié)為若干個(gè)較為簡(jiǎn)單的問題,然后將這些較為簡(jiǎn)單的問題進(jìn)一步歸結(jié)為更簡(jiǎn)單的問題,這個(gè)過程一直進(jìn)行下去直到歸結(jié)為最簡(jiǎn)單的問題時(shí)為止。這個(gè)最簡(jiǎn)單的問題即為遞歸終止條件,也稱作遞歸出口 37、。 在高級(jí)語言程序設(shè)計(jì)課程中介紹的著名的漢諾(Hanoi)塔問題的求解算法和后續(xù)章節(jié)中介紹的有關(guān)樹和二叉樹的許多算法,都是遞歸法的典型運(yùn)用。,遞歸法和遞推法比較,遞歸和遞推是既有區(qū)別又有聯(lián)系的兩個(gè)概念。 遞推是從已知初始條件出發(fā)逐次推出最后所求的值; 遞歸則是從函數(shù)本身出發(fā),逐次上溯調(diào)用其本身求解過程直到遞歸出口,然后再從里向外倒推回來得到最終的值。 一般地說,一個(gè)遞推算法總可以轉(zhuǎn)換為一個(gè)遞歸算法。對(duì)于同一問題所設(shè)計(jì)的遞歸算法往往要比相應(yīng)的非遞歸算法(如遞推算法)付出更多的執(zhí)行時(shí)間代價(jià)和更多的輔助存儲(chǔ)空間開銷。,遞歸法和遞推法比較(續(xù)),然而,利用遞歸方法分析和設(shè)計(jì)算法可使難度大幅度降低,且程 38、序設(shè)計(jì)語言中一般都提供遞歸機(jī)制;利用遞歸過程描述問題求解算法不僅非常自然,而且算法的正確性證明要比相應(yīng)的非遞歸算法容易得多;另外有成熟的方法和技術(shù),可以很方便地把遞歸算法改寫為非遞歸算法。 所以,遞歸技術(shù)是算法設(shè)計(jì)的基本技術(shù),遞歸方法是降低分析設(shè)計(jì)難度提高設(shè)計(jì)效率的重要手段和工具。,5.回溯法,回溯法是算法設(shè)計(jì)中的一種基本策略,它通過對(duì)問題的分析找出一個(gè)解決問題的線索,然后沿這個(gè)線索逐步試探。 對(duì)于每一步試探,若成功就繼續(xù)下一步試探;若不成功就逐步退回?fù)Q別的路線再進(jìn)行試探,直至探索成功得到問題的解或試探完所有的線索問題無解。 在那些涉及到尋找一組解的問題或者滿足某些約束條件的最優(yōu)解的問題中,許 39、多都可以用回溯法來求解。 例如,在國際象棋棋盤上的騎士周游問題和我們平時(shí)參加的走迷宮游戲,都是使用回溯法進(jìn)行的。,6.貪婪法,貪婪法也稱作貪心算法,它是通過一系列的選擇來得到問題的一個(gè)解。 貪婪法在每一步所做出的選擇,都總是在當(dāng)前狀態(tài)下看來是最好的選擇即貪婪選擇,并希望通過每次所作的貪婪選擇導(dǎo)致最終結(jié)果是求解問題的一個(gè)最優(yōu)解。 換句話說,貪婪法并不從整體最優(yōu)上加以考慮,它做出的選擇只是在某種意義上的局部最優(yōu)選擇,但希望算法得到的最終結(jié)果也是整體最優(yōu)的。雖然這種貪婪策略不能對(duì)所有問題都得到整體最優(yōu)解,然而在許多情況下的確能夠產(chǎn)生整體最優(yōu)解。 在一些情況下,即使貪婪算法不能得到整體最優(yōu)解,其最終結(jié) 40、果卻是最優(yōu)解的很好近似。,7.分治法,求解一個(gè)復(fù)雜問題時(shí),盡可能地把這個(gè)問題分解為若干較小的子問題,在找出各個(gè)較小問題的解之后再組合成為整個(gè)問題的解,這就是所謂的分治法。 使用分治法時(shí),往往要按問題的輸入規(guī)模來衡量問題的大小;當(dāng)要求解問題的輸入規(guī)模相當(dāng)大時(shí),應(yīng)選擇適當(dāng)策略將輸入劃分成若干子集合得到一組子問題,在求出各子問題的解之后用適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€(gè)問題的解,分治法便應(yīng)用成功了。 如果得到的子問題還相對(duì)過大,可再次使用分治法將這些子問題進(jìn)一步劃分成更小的子問題。,第1章 算法與程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的設(shè)計(jì)與評(píng)價(jià) 1.4 算法與程序,算法與程序,算 41、法與程序是密切相關(guān)的兩個(gè)概念。 研究和討論算法是為了設(shè)計(jì)出更好的程序,設(shè)計(jì)好的算法都要轉(zhuǎn)化為某種語言描述的程序才能在計(jì)算機(jī)上運(yùn)行; 或者說程序是算法表示的最終形態(tài),程序只有裝入計(jì)算機(jī)中運(yùn)行(即程序的執(zhí)行)時(shí)才能夠起到對(duì)實(shí)際問題求解的作用。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,程序的基本概念,在低級(jí)語言中,程序表現(xiàn)為一組指令和有關(guān)數(shù)據(jù); 在高級(jí)語言中,程序表現(xiàn)為一組說明和語句。 程序既是軟件的固有部分,又是軟件研究的對(duì)象,程序的質(zhì)量決定著軟件的質(zhì)量。 衡量一個(gè)程序的質(zhì)量,除了對(duì)程序結(jié)構(gòu)進(jìn)行靜 42、態(tài)考察外,還必須考察其執(zhí)行過程。 與執(zhí)行無關(guān)的特性稱之為程序的靜態(tài)特性, 與執(zhí)行有關(guān)的特性稱之為程序的動(dòng)態(tài)特性。,程序的特征,程序描述解決某一問題的特定任務(wù)與功能,回答“解決什么問題”或“做什么”的問題。 程序遵循一定的規(guī)則和步驟,而不是指令或語句的隨意堆砌。 程序的執(zhí)行者是計(jì)算機(jī)。 程序是由人來編寫或設(shè)計(jì)的,是人針對(duì)要處理和解決的問題而設(shè)計(jì)的求解方法和步驟交由計(jì)算機(jī)操作、運(yùn)算和處理的說明。 程序的運(yùn)行是自動(dòng)完成的。 程序是算法的程序設(shè)計(jì)語言描述,但程序并不一定就是算法,因?yàn)槌绦驔]有有窮性要求。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào) 43、試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,解決一個(gè)實(shí)際問題的一般過程,明確問題要求。 建立數(shù)學(xué)模型。 算法設(shè)計(jì)。 編寫程序。 調(diào)試程序。 運(yùn)行及結(jié)果分析。 編寫程序文檔。,程序文檔的內(nèi)容,編寫文檔是最容易被忽視了的一個(gè)重要環(huán)節(jié)。沒有文檔資料對(duì)于軟件的維護(hù)會(huì)帶來許多困難,即使是設(shè)計(jì)者自己也不例外。文檔資料要寫得完整、清楚和準(zhǔn)確,一般應(yīng)包含如下內(nèi)容: 算法或程序的功能描述和適用范圍; 運(yùn)行環(huán)境,包括機(jī)型、操作系統(tǒng)平臺(tái)、語言種類、占用空間等; 使用說明,即使用該程序的操作命令、I/O格式、各種情況下的操作等說明; 流程圖及說明; 程序清單及注釋。,實(shí)現(xiàn)策略,在拿到一個(gè)設(shè)計(jì)問題之后,有兩種不同的方法 44、可供選擇: 一種是自頂向下逐步求精細(xì)化; 一種是自底向上逐步堆砌積累。 由于人腦思維很難一下子觸及問題細(xì)節(jié),所以自底向上方法較難運(yùn)用;即使運(yùn)用,也難設(shè)計(jì)出清晰的程序?qū)哟谓Y(jié)構(gòu)。 結(jié)構(gòu)化程序設(shè)計(jì)提倡自頂向下逐步求精細(xì)化的分析設(shè)計(jì)方法,從求解問題本身到得出一系列基本操作逐層次展開細(xì)化,是一種將問題求解方法由抽象逐步到具體化的過程。 采用自頂向下逐步求精細(xì)化的設(shè)計(jì)方法,易于保證和驗(yàn)證程序的正確性。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,程序調(diào)試,程序調(diào)試是開發(fā)過程中最艱巨的腦力勞動(dòng)。面對(duì)錯(cuò)誤征兆,如 45、何在浩如煙海的程序元素中找出有錯(cuò)誤的元素,這是調(diào)試過程中最關(guān)鍵的技術(shù)問題。 現(xiàn)有的調(diào)試技術(shù)有如下三類: 輸出存儲(chǔ)器內(nèi)容。常以八進(jìn)制或十六進(jìn)制形式打印出存儲(chǔ)器內(nèi)容并檢查分析。 在程序中插入打印語句,調(diào)試結(jié)束后要將為了調(diào)試而插入的語句刪掉。 借助調(diào)試工具。調(diào)試工具可以提供程序動(dòng)態(tài)行為的有關(guān)信息,但不需要修改源程序。例如,在turbo C中提供了專門的程序調(diào)試工具debugger程序。,調(diào)試策略,試探法 回溯法 對(duì)分查找法 歸納法。其步驟為: 收集已知的使程序出錯(cuò)與不出錯(cuò)的一切數(shù)據(jù); 整理數(shù)據(jù)以發(fā)現(xiàn)規(guī)律或矛盾; 提出關(guān)于故障的若干假設(shè); 證明假設(shè)并據(jù)此設(shè)法排除故障。 演繹法。其步驟為: 設(shè)想并列出所 46、有可能產(chǎn)生錯(cuò)誤的原因; 利用已有的數(shù)據(jù)排除不正確的假設(shè); 精化剩余的假設(shè); 證明假設(shè)并據(jù)此設(shè)法排除故障。,查錯(cuò)策略,查錯(cuò)策略主要有兩種:黑盒子測(cè)試和白盒子測(cè)試 如果已知產(chǎn)品的功能,可以測(cè)試它的每一個(gè)功能是否都達(dá)到了預(yù)期的要求,這種方法叫黑盒子測(cè)試。 如果已知產(chǎn)品的內(nèi)部活動(dòng)方式,可以測(cè)試它的內(nèi)部活動(dòng)是否都符合設(shè)計(jì)要求,這種方法稱之為白盒子測(cè)試。 無論使用哪一種方法,對(duì)程序的窮舉測(cè)試是不可能的,我們所能做到的是通過有限的測(cè)試盡可能多地發(fā)現(xiàn)錯(cuò)誤。測(cè)試只能發(fā)現(xiàn)錯(cuò)誤,而不能保證程序沒有錯(cuò)誤。查錯(cuò)的關(guān)鍵在于設(shè)計(jì)好測(cè)試用例,即確定一組最有可能發(fā)現(xiàn)某個(gè)或某類錯(cuò)誤的測(cè)試數(shù)據(jù)的設(shè)計(jì)。,常用的測(cè)試用例設(shè)計(jì)方法,邏輯 47、覆蓋。它是一種白盒子測(cè)試技術(shù)。常用的邏輯覆蓋有語句覆蓋、分支覆蓋、條件覆蓋、分支/條件覆蓋、多重覆蓋和循環(huán)覆蓋等。 等價(jià)類劃分。是一種黑盒子測(cè)試技術(shù)。 邊界值分析。是一種黑盒子測(cè)試技術(shù)。 圖形技術(shù)。它提供設(shè)計(jì)測(cè)試用例的工具,常見的有因果圖和程序圖。 測(cè)試的目的是為了發(fā)現(xiàn)錯(cuò)誤,而糾錯(cuò)則是確定錯(cuò)誤在程序中的確切位置和性質(zhì)并改正它。糾錯(cuò)的關(guān)鍵在于確定錯(cuò)誤的位置(即錯(cuò)誤定位),常用的糾錯(cuò)技術(shù)有試探法、回溯法、對(duì)分查找法、歸納法和演譯法。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,程序設(shè)計(jì)方法概述,程序是 48、軟件的重要組成部分,程序設(shè)計(jì)是軟件開發(fā)的重要方面。 程序設(shè)計(jì)方法對(duì)程序設(shè)計(jì)工作的質(zhì)量以及所設(shè)計(jì)出來的程序的質(zhì)量影響重大,因而對(duì)程序設(shè)計(jì)方法的研究也越來越受到人們的重視。 程序設(shè)計(jì)方法學(xué)主要研究涉及用于指導(dǎo)程序設(shè)計(jì)工作的原理和原則,研究基于這些原理和原則的具體設(shè)計(jì)方法和技術(shù),研究各種方法的共性和理論基礎(chǔ)。,程序設(shè)計(jì)方法概述(續(xù)),程序設(shè)計(jì)方法可以分為兩類: 全局性的 局部性的 全局性的。如結(jié)構(gòu)化程序設(shè)計(jì)方法,它不僅要求編出的程序結(jié)構(gòu)良好,而且要求程序設(shè)計(jì)過程是結(jié)構(gòu)化、層次式、逐層降低抽象級(jí)別的。 局部性的。如子例程方法、協(xié)同例程方法等。,程序設(shè)計(jì)方法與技術(shù),結(jié)構(gòu)化程序設(shè)計(jì) 軟件工程方法 面向?qū)ο蟮某绦蛟O(shè)計(jì) 多媒體程序設(shè)計(jì) 可視化編程 函數(shù)程序設(shè)計(jì) 邏輯程序設(shè)計(jì) 并行程序設(shè)計(jì) 分布式程序設(shè)計(jì) 文化程序設(shè)計(jì),
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 優(yōu)化工作流程提高工作效率
- 文化創(chuàng)新優(yōu)秀課件
- 急性白血病免疫分型ppt課件
- 圓錐曲線性質(zhì)的探討與幾何證明的簡(jiǎn)單應(yīng)用
- 材料作文寫作技巧
- 機(jī)械制圖螺紋畫法
- 低價(jià)中標(biāo)合理性的確定和約束機(jī)制的研究報(bào)告
- 綜合性學(xué)習(xí)的復(fù)習(xí)
- 函數(shù)的極值與最值
- 醫(yī)療衛(wèi)生類通用PPT模板
- 中國最美的100個(gè)地方
- 住院醫(yī)師規(guī)范化培訓(xùn)發(fā)展歷程
- 六年級(jí)數(shù)學(xué)上冊(cè)百分?jǐn)?shù)解決問題
- 某工程有限公司項(xiàng)目入廠安全培訓(xùn)教材
- 液態(tài)光學(xué)膠應(yīng)用