《《算法與數(shù)據(jù)結(jié)構(gòu)》第1章算法與程序ppt.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第1章算法與程序ppt.ppt（93頁(yè)珍藏版）》請(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章 樹(shù)和二叉樹(shù) 第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ù)的最大公因子的解題步驟。要求解的問(wèn)題描述為：“給定兩個(gè)正整數(shù)m和n，求它們的最大公因子，即能同時(shí)整除m和n

2、的最大整數(shù)”。歐幾里德當(dāng)時(shí)給出的算法如下： 以n除m，并令所得余數(shù)為r（必有rn）； 若r=0，輸出結(jié)果n，算法結(jié)束；否則繼續(xù)步驟； 令m=n和n=r，返回步驟繼續(xù)進(jìn)行。,什么是算法（續(xù)）,由此，我們可以得出這樣的結(jié)論，算法就是求解問(wèn)題的方法和步驟。這里的方法和步驟是一組嚴(yán)格定義了運(yùn)算順序的規(guī)則；每一個(gè)規(guī)則都是有效的，且是明確的；按此順序?qū)⒃谟邢薮螖?shù)下終止。 有關(guān)算法（Algorithm）一詞的定義不少，但其內(nèi)涵基本上是一致的。最為著名的定義是計(jì)算機(jī)科學(xué)家D.E.Kunth在其巨著計(jì)算機(jī)程序的藝術(shù)（ Art of Computer Program）第一卷中所做的有關(guān)描述。其非形式化的定義是：

3、一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則定義了一個(gè)解決某一特定類型問(wèn)題的運(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è)輸入元素x均為一個(gè)計(jì)算序列

4、，即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 自然語(yǔ)言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語(yǔ)言表示,自然語(yǔ)言表示,自然語(yǔ)言即人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，如漢語(yǔ)、

5、英語(yǔ)、日語(yǔ)、法語(yǔ)、德語(yǔ)等等。使用自然語(yǔ)言描述算法，人們比較容易接受和理解。如前面的歐幾里德算法就是用自然語(yǔ)言描述的。然而，自然語(yǔ)言也具有許多缺點(diǎn)，在使用自然語(yǔ)言描述算法時(shí)一定要引起注意： 自然語(yǔ)言存在著歧義性，容易導(dǎo)致算法的不確定性； 自然語(yǔ)言容易冗長(zhǎng)，使得描述不夠簡(jiǎn)潔； 自然語(yǔ)言的表示形式是順序的，描述分支選擇和轉(zhuǎn)移時(shí)不夠直觀； 自然語(yǔ)言與計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的差別較大，不易轉(zhuǎn)換為程序。,1.2 算法的表示,1.2.1 自然語(yǔ)言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語(yǔ)言表示,流程圖表示,流程圖是描述算法的圖形工具，它采用如下所示的一組圖形

6、符號(hào)來(lái)表示算法：,起止框，表示算法的開(kāi)始或結(jié)束；只有一個(gè)入口或一個(gè)出口。 輸入輸出框，表示算法中數(shù)據(jù)信息的輸入和輸出；有一個(gè)入口和一個(gè)出口。 判斷框，表示條件判斷；有一個(gè)入口和多個(gè)出口。 處理框，表示算法中的一個(gè)（或一組）運(yùn)算或處理；有一個(gè)入口和一個(gè)出口。 流程線，表示算法中各步驟之間的次序關(guān)系。 連接點(diǎn)，表示算法中的連接位置，主要用于同一算法在不同頁(yè)描述時(shí)的接續(xù)等情況。 注釋框，用于對(duì)算法中某些操作的注釋說(shuō)明。,流程圖表示舉例,歐幾里德算法的流程圖描述如圖1-1所示,流程圖表示（續(xù)）,同自然語(yǔ)言相比，用流程圖描述算法直觀，可以一目了然；算法步驟間用流程線連接，次序關(guān)系清楚，容易理解；可以很方

7、便地表示順序、選擇和循環(huán)結(jié)構(gòu)，不依賴于任何計(jì)算機(jī)和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，有利于不同環(huán)境下的程序設(shè)計(jì)。但是，流程圖也還存在一些缺點(diǎn)，諸如： 不易于表示算法的層次結(jié)構(gòu)； 不易于表示數(shù)據(jù)結(jié)構(gòu)和模塊調(diào)用關(guān)系等重要信息； 容易使人過(guò)早地考慮算法的控制流程，而忽視算法的全局結(jié)構(gòu)； 用流程線代表控制流，控制轉(zhuǎn)移隨意性較大。若對(duì)流程線的使用不加限制，隨著求解問(wèn)題規(guī)模和復(fù)雜度的增加，流程圖會(huì)變得很復(fù)雜，使人難以閱讀、理解和修改，從而使算法的可靠性難以保證。,1.2 算法的表示,1.2.1 自然語(yǔ)言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語(yǔ)言表示,NS圖表示,為

8、了克服傳統(tǒng)流程圖的缺點(diǎn)，1973年美國(guó)學(xué)者納斯（I.Nassi）和施內(nèi)德曼（B.Shneiderman）提出了一種表示算法的較好工具N-S圖。 它獨(dú)立于任何計(jì)算機(jī)和計(jì)算機(jī)語(yǔ)言，又能很方便地轉(zhuǎn)換為計(jì)算機(jī)語(yǔ)言程序； 它去掉了流程線全部用矩形方框來(lái)描述，限制了算法流程轉(zhuǎn)移控制的隨意性，又節(jié)省了篇幅； 它很容易表示算法中的嵌套關(guān)系和模塊中的層次關(guān)系，功能域可以從框圖中直接反映出來(lái)； 它仍是圖形工具，閱讀起來(lái)直觀、明確、容易理解。,NS圖表示（續(xù)）,N-S圖的基本圖形符號(hào)如下：,順序結(jié)構(gòu)，由兩個(gè)或多個(gè)矩形框組成。其中A和B可以是基本操作，也可以是其它基本結(jié)構(gòu)（如選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)）。 選擇結(jié)構(gòu)，當(dāng)條件P

9、成立時(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 自然語(yǔ)言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語(yǔ)言表示,偽代碼表示,偽代碼是介乎于自然語(yǔ)言和計(jì)算機(jī)程序語(yǔ)言之間的一種表示算法的工具。 它用文字和符號(hào)描述問(wèn)題的求解方法和步驟而不使用圖形符號(hào)。 如同一篇文章自上而下書(shū)寫，每行寫一個(gè)基本操作，而用若干行

10、寫出一個(gè)基本結(jié)構(gòu)。 因而書(shū)寫方便，格式緊湊，清晰易讀好理解，也更容易轉(zhuǎn)化為某一計(jì)算機(jī)程序語(yǔ)言表示的程序。 和圖形工具相比較，便于修改，但直觀性能較弱。,偽代碼表示（續(xù)）,下面，我們給出歐幾里德算法的一種偽代碼描述如下： Begin(算法開(kāi)始) Read(m,n) m mod nr while r0 do nm rn m mod nr write(n) End(算法結(jié)束),1.2 算法的表示,1.2.1 自然語(yǔ)言表示 1.2.2 流程圖表示 1.2.3 NS圖表示 1.2.4 偽代碼表示 1.2.5 程序語(yǔ)言表示,程序語(yǔ)言表示,計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，是計(jì)算機(jī)能夠接受、理解和執(zhí)行的算法描述工具。 計(jì)

11、算機(jī)不能直接識(shí)別自然語(yǔ)言、流程圖、N-S圖和偽代碼等工具描述的算法，而設(shè)計(jì)算法的目的就是要用計(jì)算機(jī)來(lái)解決問(wèn)題，算法最終都要用某一具體的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)表示。 從這個(gè)意義上講，流程圖、N-S圖和偽代碼都僅僅是為了求解問(wèn)題而設(shè)計(jì)算法時(shí)的輔助工具。 為了更好更準(zhǔn)確地描述算法，人們使用圖形或表格還創(chuàng)造了許多專用的算法設(shè)計(jì)輔助工具，如PAD圖、判定表、數(shù)據(jù)流圖、Warnier-rr圖等等。,程序語(yǔ)言表示（續(xù)）,和自然語(yǔ)言一樣，計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言也是串行的描述，很不直觀。 對(duì)于較復(fù)雜的問(wèn)題，人們很難用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言直接寫出程序。 所以在算法設(shè)計(jì)階段，一般是先采用某個(gè)專用的輔助工具來(lái)描述算法，在算法

12、設(shè)計(jì)好之后，再把它轉(zhuǎn)化為某一具體程序設(shè)計(jì)語(yǔ)言描述的程序。,程序語(yǔ)言表示（續(xù)）,作為例子，下面我們給出歐幾里德算法的C語(yǔ)言描述如下： #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à)算法的標(biāo)準(zhǔn) 1.3.2 算法的環(huán)路復(fù)雜度 1.3.3 算法的時(shí)空效率 1.3.4 常見(jiàn)的算法設(shè)計(jì)方

13、法,評(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ì)出來(lái)的算法要能夠正確求解給定的問(wèn)題。 這就要求算法中的每一個(gè)步驟的描述是準(zhǔn)確無(wú)歧義的，并且是可以執(zhí)行的； 要求算法能夠滿足問(wèn)題要求，并在有限步驟內(nèi)獲得結(jié)果； 否則就不具備正確性要求，更談不上解決給定的實(shí)際問(wèn)題了。 算法要能經(jīng)得起一切可能的輸入數(shù)據(jù)的考驗(yàn)。,評(píng)價(jià)算法的“正確性”標(biāo)準(zhǔn)（續(xù)）,在將算法用程序語(yǔ)言表示為特定語(yǔ)言的程序后還必須注意： 程序中不含有語(yǔ)法錯(cuò)誤； 對(duì)于一切合法的輸入數(shù)據(jù)，程序能夠產(chǎn)生滿足要求的輸出結(jié)果； 對(duì)于一切非法

14、的輸入數(shù)據(jù)，程序能夠得出滿足規(guī)格說(shuō)明的結(jié)果； 對(duì)于精心選擇的，甚至是帶有刁難性的典型測(cè)試數(shù)據(jù)，程序都有滿足要求的輸出結(jié)果。,評(píng)價(jià)算法的“可讀性”標(biāo)準(zhǔn),表示出來(lái)的算法要能夠方便地供人們閱讀、理解和交流。 算法的可讀性好是保證正確性的前提，良好的可讀性有利于人們理解算法思想，減少出錯(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ù)開(kāi)平方等，算法應(yīng)能做出相應(yīng)的處理，給出錯(cuò)誤信息或終止算法執(zhí)行，避免產(chǎn)生錯(cuò)誤的或莫明其妙的輸出結(jié)果。,評(píng)價(jià)算法的“高效性”標(biāo)準(zhǔn),算法的執(zhí)行效率要高。 算法的效率可分為

15、時(shí)間效率和空間效率。 時(shí)間效率是通過(guò)該算法轉(zhuǎn)化的程序在計(jì)算機(jī)上運(yùn)行的時(shí)間耗費(fèi)來(lái)確定，在算法設(shè)計(jì)與分析階段用執(zhí)行基本操作的次數(shù)（是問(wèn)題規(guī)模的函數(shù)）相對(duì)于問(wèn)題規(guī)模的漸近階來(lái)表示。 空間效率主要考慮除存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)之外的輔助存儲(chǔ)空間。一個(gè)高效算法是指執(zhí)行算法耗費(fèi)時(shí)間少，使用輔助存儲(chǔ)空間小的算法。,評(píng)價(jià)算法的“簡(jiǎn)潔性 ”標(biāo)準(zhǔn),所設(shè)計(jì)出來(lái)的算法要盡可能地簡(jiǎn)潔。 對(duì)于同一問(wèn)題所設(shè)計(jì)的不同算法，越簡(jiǎn)潔明了的越好。 越簡(jiǎn)潔的算法可讀性越好，越易于理解、編碼和調(diào)試、測(cè)試，越受人們歡迎。,評(píng)價(jià)算法的標(biāo)準(zhǔn)（續(xù)）,在評(píng)價(jià)一個(gè)算法時(shí)，要對(duì)這五個(gè)方面綜合考慮，不要片面追求某一指標(biāo)。 有些指標(biāo)之間往往是相互制約的，如時(shí)間效率

16、與空間效率，簡(jiǎn)潔性與高效性等等； 要學(xué)會(huì)針對(duì)具體問(wèn)題要求和軟硬件實(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 常見(jiàn)的算法設(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ù)）,算法（或程序）的環(huán)路復(fù)雜度度量方法，以圖論為工具，先畫(huà)出程序圖，然后用該程序圖的環(huán)路作為算法（或程

17、序）復(fù)雜性的度量值。 所謂程序圖可以看成是退化了的流程圖，也就是把算法（或程序）流程圖中的每個(gè)處理框都退化成為一個(gè)點(diǎn)，原來(lái)連接不同框之間的流程線變成連接不同點(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ì)算方法,強(qiáng)連通圖中線性無(wú)關(guān)的環(huán)路個(gè)數(shù)我們可以用如下的公式確定： V(G)=e-n+p 其中：

18、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)用上述的公式法計(jì)算之外，還有如下的兩種方法可以用來(lái)確定程序圖的環(huán)路復(fù)雜度： 觀察法，即觀察強(qiáng)連通的程序圖在平面上所圍

19、成的獨(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ù)）,利用判定語(yǔ)句計(jì)算法，即把程序圖中所有出現(xiàn)的分支結(jié)點(diǎn)處所需要的判定的總個(gè)數(shù)加起來(lái)再加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)路復(fù)雜度（即環(huán)路數(shù)）為2；而圖1-4中有兩個(gè)結(jié)點(diǎn)（上數(shù)第二個(gè)和左下結(jié)點(diǎn)）是分支結(jié)點(diǎn)且結(jié)點(diǎn)都為三路分支，故所

20、需的判定為2+2=4個(gè)，其環(huán)路復(fù)雜度為5。,算法的環(huán)路復(fù)雜度（續(xù)）,算法的環(huán)路復(fù)雜度越高，說(shuō)明算法的控制越復(fù)雜，在轉(zhuǎn)化為程序時(shí)的難度就越大，轉(zhuǎn)化后的程序測(cè)試難度也就越大問(wèn)題越多。在設(shè)計(jì)算法時(shí)，一般地應(yīng)控制模塊的環(huán)路復(fù)雜度在10以內(nèi)為宜。 環(huán)路復(fù)雜度的度量方法的最大優(yōu)點(diǎn)在于它的簡(jiǎn)明性，只要知道算法中的判定個(gè)數(shù)即可。然而它也有許多不足之處，如沒(méi)有區(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é)合其它方法一塊使用。,1.3 算法的設(shè)計(jì)與評(píng)價(jià),1.3.1 評(píng)價(jià)算法的標(biāo)準(zhǔn) 1.3.2 算法的環(huán)路復(fù)雜度 1.

21、3.3 算法的時(shí)空效率 1.3.4 常見(jiàn)的算法設(shè)計(jì)方法,算法的時(shí)空效率,如果算法是用N-S圖、偽代碼、程序語(yǔ)言或其它方式表示的，要度量其環(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)，即算法中每條語(yǔ)句在計(jì)算機(jī)上執(zhí)行的時(shí)間總和，大致上可以認(rèn)為它等于計(jì)算機(jī)執(zhí)行一種基本操作（如賦值運(yùn)算、比較運(yùn)算、移動(dòng)操作等）所需的時(shí)間與算法中進(jìn)行基本操作總次數(shù)的乘積

22、。 而每條語(yǔ)句的執(zhí)行時(shí)間則應(yīng)該是執(zhí)行該語(yǔ)句一次所需的時(shí)間與該語(yǔ)句執(zhí)行的次數(shù)（也稱之為頻度）的乘積。 某條語(yǔ)句執(zhí)行一次所需的時(shí)間一般地是隨機(jī)器而異的，取決于具體機(jī)器的性能、速度和編譯代碼的質(zhì)量，是由機(jī)器本身的軟、硬件環(huán)境所決定的，與算法無(wú)關(guān)。所以，我們可以假設(shè)執(zhí)行每條語(yǔ)句所需的時(shí)間均為單位時(shí)間。 因此，對(duì)算法執(zhí)行時(shí)間的討論就可以轉(zhuǎn)化為對(duì)算法中所有語(yǔ)句的執(zhí)行次數(shù)（即頻度）的討論。,大O方法計(jì)算舉例,兩個(gè)n*n矩陣相乘的算法描述如下： for(i=1;i=n;i+) /* n+1次 */ for(j=1;j=n;j+) /* n(n+1)次 */ cij=0; /* n2次 */ for(k=1;k

23、=n;k+) /* n2(n+1)次 */ cij=cij+aik*bkj; /* n3次 */ ,大O方法計(jì)算舉例（續(xù)）,其中，每一條語(yǔ)句的頻度說(shuō)明在注釋中。我們把算法所耗費(fèi)的時(shí)間定義為該算法中每條語(yǔ)句的頻度之和，則該算法的時(shí)間耗費(fèi)T(n)可表示為 T(n)=2n3+3n2+2n+1 顯然，它是矩陣的階（該問(wèn)題的規(guī)模）n的函數(shù)。并且當(dāng)n時(shí)，T(n)/n32。這表示當(dāng)n趨于無(wú)窮大時(shí)，T(n)與n3是同階函數(shù)或者說(shuō)是同量級(jí)的。引入大O記號(hào)可記作 T(n)=O(n3),時(shí)間復(fù)雜度,引入大O記號(hào)表示的算法的時(shí)間耗費(fèi)T(n)通常稱之為算法的時(shí)間復(fù)雜度，如矩陣相乘算法的時(shí)間復(fù)雜度為O(n3)。 這種時(shí)間

24、復(fù)雜度的大O表示法，實(shí)質(zhì)上是把算法的基本操作總數(shù)表示為問(wèn)題規(guī)模n的函數(shù)之后，尋找出當(dāng)問(wèn)題規(guī)模n趨于無(wú)窮大時(shí)該函數(shù)的同階最簡(jiǎn)形式即漸近性態(tài)下的同階最簡(jiǎn)函數(shù)，有時(shí)也簡(jiǎn)稱之為漸近階。 問(wèn)題的規(guī)模是指算法中要處理的數(shù)據(jù)量的規(guī)模，通常用一個(gè)整型量n來(lái)表示。對(duì)于求解不同的問(wèn)題，規(guī)模n具有不同的值。,時(shí)間復(fù)雜度（續(xù)）,時(shí)間復(fù)雜性的漸近階表示，是對(duì)算法時(shí)間性能優(yōu)劣的宏觀定性評(píng)價(jià)。 例如，為了求解同一問(wèn)題所設(shè)計(jì)的兩個(gè)不同的算法A1和A2，其時(shí)間耗費(fèi)分別為T1(n)=40n2和T2(n)=5n3；顯然當(dāng)問(wèn)題規(guī)模nT2(n)，算法A2比A1時(shí)間花費(fèi)少；利用漸近階表示的時(shí)間復(fù)雜度O(n2)和O(n3)反映了對(duì)這兩個(gè)算

25、法時(shí)間性能優(yōu)劣的宏觀定性評(píng)價(jià)結(jié)論。 由于是宏觀的定性評(píng)價(jià)，算法中頻度最大的語(yǔ)句的頻度，與算法中每條語(yǔ)句頻度的和T(n)是同階函數(shù)； 所以人們?cè)谟?jì)算算法時(shí)間復(fù)雜度時(shí)，往往只需考慮算法中頻度最大的語(yǔ)句的頻度就可以了。,時(shí)間復(fù)雜度計(jì)算舉例,例如對(duì)于下面的程序段： x=0; for(i=1;in;i+) for(j=1;ji;j+) for(k=1;kj;k+) x+; 我們只須關(guān)心程序段中執(zhí)行頻度最大的語(yǔ)句最內(nèi)層循環(huán)的循環(huán)體語(yǔ)句x+，它的執(zhí)行次數(shù)是 由于n3是它的漸近性態(tài)下的同階最簡(jiǎn)函數(shù)，可得上述程序段的時(shí)間復(fù)雜度為T(n)= O(n3)。,簡(jiǎn)明實(shí)用的程序分析法則,執(zhí)行一條基本操作如讀寫或賦值語(yǔ)句等

26、，需要O(1)的時(shí)間花費(fèi)。 對(duì)于順序結(jié)構(gòu)，需要執(zhí)行一系列語(yǔ)句，所用時(shí)間用求和準(zhǔn)則估計(jì)。 對(duì)于選擇結(jié)構(gòu)如if語(yǔ)句，主要時(shí)間耗費(fèi)是執(zhí)行then子句或else子句所用的時(shí)間；此外，檢驗(yàn)條件還需用O(1)的時(shí)間。多選擇結(jié)構(gòu)的時(shí)間耗費(fèi)與if語(yǔ)句類同。 對(duì)于循環(huán)結(jié)構(gòu)，執(zhí)行時(shí)間為多次迭代中循環(huán)體的執(zhí)行和檢驗(yàn)循環(huán)條件的耗時(shí)，常用乘法準(zhǔn)則估計(jì)。 對(duì)于復(fù)雜算法，可以將它分成幾個(gè)容易估算的部分分別估計(jì)，然后利用求和準(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) （不相同問(wèn)題規(guī)模時(shí)） 則T1(m)+ T2(n)=O(f(m

27、)+g(n) 若T1(n)=O(f(n)，T2(n)=O(g(n) （相同問(wè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) （不相同問(wèn)題規(guī)模時(shí)） 則T1(m)*T2(n)=O(f(m)*g(n) 若T1(n)=O(f(n)，T2(n)=O(g(n) （相同問(wèn)題規(guī)模時(shí)） 則T1(n)*T2(n)=O(f(n)*g(n) 若c是一個(gè)正常數(shù) （特殊運(yùn)算規(guī)則） 則O(cf(n)=O(f

28、(n),程序分析法則舉例,如對(duì)前述的矩陣相乘算法，它是三層嵌套的循環(huán)結(jié)構(gòu)，我們可以從最內(nèi)層循環(huán)的循環(huán)體開(kāi)始分析： 是賦值語(yǔ)句，與問(wèn)題規(guī)模無(wú)關(guān)，時(shí)間復(fù)雜度為常數(shù)階O(1)，即T5(n)=O(1)； 對(duì)于第條語(yǔ)句，T4(n)=O(n)，它與第條語(yǔ)句是循環(huán)關(guān)系應(yīng)該用乘法準(zhǔn)則，即T4(n)*T5(n)=O(1*n)=O(n)； 對(duì)于第條語(yǔ)句T3(n)=O(1)，它與第、是順序結(jié)構(gòu)應(yīng)該用求和準(zhǔn)則，即T3(n)+T4(n)* T5(n)=O(max(1,n)=O(n)； 第條語(yǔ)句其T2(n)=O(n)，到是它的循環(huán)體適用乘法準(zhǔn)則，故有T2(n)*(T3(n)+T4(n)*T5(n)=O(n*n)=O(n2

29、)； 第條語(yǔ)句的耗時(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(yǔ)句執(zhí)行頻度的總和關(guān)于問(wèn)題規(guī)模的函數(shù)表達(dá)后求漸近階得出的結(jié)果一致，但卻省去了計(jì)算所有語(yǔ)句執(zhí)行頻度總和的麻煩。 實(shí)際上，算法或程序的執(zhí)行時(shí)間不僅依賴于所求解問(wèn)題的規(guī)模，還與它所處理的數(shù)據(jù)的狀態(tài)有關(guān)。 一般在不做任何說(shuō)明的情況下，討論其時(shí)間復(fù)雜度是指在最壞情況下的時(shí)間復(fù)雜度，通?？捎涀鱐max(n)；有時(shí)還要討論其平均情

30、況下的時(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í)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間。這部分空間是與算法本身密切相關(guān)的，因算法設(shè)計(jì)的不同而異，是我們討論算法的空間代價(jià)時(shí)所要著重討論的方面。 度量一個(gè)算法或程序在執(zhí)行過(guò)程中所花費(fèi)的額外存儲(chǔ)開(kāi)銷（即臨時(shí)存儲(chǔ)工作單元）的大小也是用大O方法，度量的結(jié)果稱之為算法的空間復(fù)雜度?？臻g復(fù)雜度和時(shí)間復(fù)雜度一樣，也是用相對(duì)于問(wèn)題規(guī)模函數(shù)

31、的漸近階形式給出，如O(1)、O(n)等。,時(shí)（空）間復(fù)雜度,常見(jiàn)的時(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)問(wèn)題規(guī)模n稍大時(shí)就無(wú)法使用。,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 常見(jiàn)的算法設(shè)計(jì)方法,常見(jiàn)的算法設(shè)計(jì)方法,為了獲得有效的算法，必須了解一些解題的基本思想和方法。對(duì)于許多問(wèn)題，只要仔細(xì)分析了數(shù)據(jù)對(duì)象后，相應(yīng)的處理方法就有了；對(duì)于有些問(wèn)題則不然。然而，作為探

32、尋問(wèn)題求解思路的基本思想和方法，對(duì)于任何算法設(shè)計(jì)都是有用的。下面我們簡(jiǎn)要介紹一些常用的算法設(shè)計(jì)方法和技術(shù)： 窮舉法 迭代法 遞推法 遞歸法 回溯法 貪婪法 分治法,1.窮舉法,窮舉法亦稱作枚舉法。它的基本思想是： 首先根據(jù)求解問(wèn)題的部分條件確定答案的大致范圍，即列舉出解的所有可能的情況； 然后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，若某個(gè)情況經(jīng)過(guò)驗(yàn)證符合問(wèn)題條件則為一個(gè)解，若全部情況驗(yàn)證后均不符合題目條件則問(wèn)題無(wú)解，從而得出求解問(wèn)題的完整解。 例如要找出200到500之間的所有素?cái)?shù)，我們只要對(duì)這個(gè)范圍內(nèi)的每一個(gè)數(shù)逐個(gè)用素?cái)?shù)的定義去判斷就行了。 窮舉法的特點(diǎn)是算法簡(jiǎn)單，但有時(shí)運(yùn)算量大效率較低。在可以

33、確定解的取值范圍，但一時(shí)又找不到更好的算法時(shí)，就可以使用窮舉法求解。,2.迭代法,迭代法的基本思想是，由一個(gè)量的原值求出它的新值，不斷地再用新值替代原值求出它的下一個(gè)新值，直到得到滿意的解。新值與原值之間存在一定的關(guān)系，這種關(guān)系可以用一個(gè)公式來(lái)表示，稱之為迭代公式。 迭代法主要用于那些很難用或無(wú)法用解析法求解的一類計(jì)算問(wèn)題，如高次方程和超越方程等；使得復(fù)雜問(wèn)題的求解過(guò)程，轉(zhuǎn)化為相對(duì)較簡(jiǎn)單的迭代算式的重復(fù)執(zhí)行過(guò)程，用數(shù)值方法求出問(wèn)題的近似解。,迭代法（續(xù)）,使用迭代法構(gòu)造這一類問(wèn)題求解算法的基本方法是： 先確定一個(gè)收斂性能好（即收斂速度快）的迭代公式，選取解的一個(gè)近似值（即迭代初值）和解的精度要

34、求（即允許的最大誤差范圍）， 然后用循環(huán)處理實(shí)現(xiàn)迭代過(guò)程，終止循環(huán)的條件是前后兩次得到的近似值之差的絕對(duì)值小于解的精度要求，并認(rèn)為最后一次得到的近似解為問(wèn)題的解。 這種迭代方法稱作逼近迭代，如著名的牛頓迭代法就是這種逼近迭代方法。 此外，精確值的計(jì)算也可以使用迭代法。例如計(jì)算s=1+2+3+1000，可選取迭代公式s+is和迭代初值0（即0s）。,3.遞推法,遞推法是從前面的一些量推出后面的一些量的一種方法，它從已知的初始條件出發(fā)，逐次推出所需要求解的各中間結(jié)果和最終結(jié)果。 遞推過(guò)程往往表現(xiàn)為迭代，即由一些量的原值推出它的新值，不斷地用新值替代原值推出下一個(gè)新值，直到推出最終結(jié)果，新值與原值之

35、間的關(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ì)說(shuō)，如果使用通項(xiàng)公式計(jì)算豈不更方便嗎？事實(shí)上，有些遞推問(wèn)題的通項(xiàng)公式是很難找出的，即使找出通項(xiàng)公式計(jì)算也不一定簡(jiǎn)便。如Fibonacci數(shù)列的通項(xiàng)公式為 顯而易見(jiàn)，找出這個(gè)通項(xiàng)公式不易，利用它計(jì)算F(n)也相當(dāng)費(fèi)力。相反地，若利用遞推初值和遞推公式計(jì)算F(n)就容易和方便多了。,4.遞歸法,如果一個(gè)過(guò)程直接或間接地調(diào)用它自身，

36、則稱該過(guò)程是遞歸的；直接調(diào)用自身稱作直接遞歸，間接調(diào)用自身則稱作間接遞歸。 遞歸是構(gòu)造算法的一種基本方法，它將一個(gè)復(fù)雜問(wèn)題歸結(jié)為若干個(gè)較為簡(jiǎn)單的問(wèn)題，然后將這些較為簡(jiǎn)單的問(wèn)題進(jìn)一步歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程一直進(jìn)行下去直到歸結(jié)為最簡(jiǎn)單的問(wèn)題時(shí)為止。這個(gè)最簡(jiǎn)單的問(wèn)題即為遞歸終止條件，也稱作遞歸出口。 在高級(jí)語(yǔ)言程序設(shè)計(jì)課程中介紹的著名的漢諾（Hanoi）塔問(wèn)題的求解算法和后續(xù)章節(jié)中介紹的有關(guān)樹(shù)和二叉樹(shù)的許多算法，都是遞歸法的典型運(yùn)用。,遞歸法和遞推法比較,遞歸和遞推是既有區(qū)別又有聯(lián)系的兩個(gè)概念。 遞推是從已知初始條件出發(fā)逐次推出最后所求的值； 遞歸則是從函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過(guò)程

37、直到遞歸出口，然后再?gòu)睦锵蛲獾雇苹貋?lái)得到最終的值。 一般地說(shuō)，一個(gè)遞推算法總可以轉(zhuǎn)換為一個(gè)遞歸算法。對(duì)于同一問(wèn)題所設(shè)計(jì)的遞歸算法往往要比相應(yīng)的非遞歸算法（如遞推算法）付出更多的執(zhí)行時(shí)間代價(jià)和更多的輔助存儲(chǔ)空間開(kāi)銷。,遞歸法和遞推法比較（續(xù)）,然而，利用遞歸方法分析和設(shè)計(jì)算法可使難度大幅度降低，且程序設(shè)計(jì)語(yǔ)言中一般都提供遞歸機(jī)制；利用遞歸過(guò)程描述問(wèn)題求解算法不僅非常自然，而且算法的正確性證明要比相應(yīng)的非遞歸算法容易得多；另外有成熟的方法和技術(shù)，可以很方便地把遞歸算法改寫為非遞歸算法。 所以，遞歸技術(shù)是算法設(shè)計(jì)的基本技術(shù)，遞歸方法是降低分析設(shè)計(jì)難度提高設(shè)計(jì)效率的重要手段和工具。,5.回溯法,回溯法

38、是算法設(shè)計(jì)中的一種基本策略，它通過(guò)對(duì)問(wèn)題的分析找出一個(gè)解決問(wèn)題的線索，然后沿這個(gè)線索逐步試探。 對(duì)于每一步試探，若成功就繼續(xù)下一步試探；若不成功就逐步退回?fù)Q別的路線再進(jìn)行試探，直至探索成功得到問(wèn)題的解或試探完所有的線索問(wèn)題無(wú)解。 在那些涉及到尋找一組解的問(wèn)題或者滿足某些約束條件的最優(yōu)解的問(wèn)題中，許多都可以用回溯法來(lái)求解。 例如，在國(guó)際象棋棋盤上的騎士周游問(wèn)題和我們平時(shí)參加的走迷宮游戲，都是使用回溯法進(jìn)行的。,6.貪婪法,貪婪法也稱作貪心算法，它是通過(guò)一系列的選擇來(lái)得到問(wèn)題的一個(gè)解。 貪婪法在每一步所做出的選擇，都總是在當(dāng)前狀態(tài)下看來(lái)是最好的選擇即貪婪選擇，并希望通過(guò)每次所作的貪婪選擇導(dǎo)致最終結(jié)

39、果是求解問(wèn)題的一個(gè)最優(yōu)解。 換句話說(shuō)，貪婪法并不從整體最優(yōu)上加以考慮，它做出的選擇只是在某種意義上的局部最優(yōu)選擇，但希望算法得到的最終結(jié)果也是整體最優(yōu)的。雖然這種貪婪策略不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，然而在許多情況下的確能夠產(chǎn)生整體最優(yōu)解。 在一些情況下，即使貪婪算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。,7.分治法,求解一個(gè)復(fù)雜問(wèn)題時(shí)，盡可能地把這個(gè)問(wèn)題分解為若干較小的子問(wèn)題，在找出各個(gè)較小問(wèn)題的解之后再組合成為整個(gè)問(wèn)題的解，這就是所謂的分治法。 使用分治法時(shí)，往往要按問(wèn)題的輸入規(guī)模來(lái)衡量問(wèn)題的大小；當(dāng)要求解問(wèn)題的輸入規(guī)模相當(dāng)大時(shí)，應(yīng)選擇適當(dāng)策略將輸入劃分成若干子集合得到一組

40、子問(wèn)題，在求出各子問(wèn)題的解之后用適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€(gè)問(wèn)題的解，分治法便應(yīng)用成功了。 如果得到的子問(wèn)題還相對(duì)過(guò)大，可再次使用分治法將這些子問(wèn)題進(jìn)一步劃分成更小的子問(wèn)題。,第1章 算法與程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的設(shè)計(jì)與評(píng)價(jià) 1.4 算法與程序,算法與程序,算法與程序是密切相關(guān)的兩個(gè)概念。 研究和討論算法是為了設(shè)計(jì)出更好的程序，設(shè)計(jì)好的算法都要轉(zhuǎn)化為某種語(yǔ)言描述的程序才能在計(jì)算機(jī)上運(yùn)行； 或者說(shuō)程序是算法表示的最終形態(tài)，程序只有裝入計(jì)算機(jī)中運(yùn)行（即程序的執(zhí)行）時(shí)才能夠起到對(duì)實(shí)際問(wèn)題求解的作用。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問(wèn)

41、題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,程序的基本概念,在低級(jí)語(yǔ)言中，程序表現(xiàn)為一組指令和有關(guān)數(shù)據(jù)； 在高級(jí)語(yǔ)言中，程序表現(xiàn)為一組說(shuō)明和語(yǔ)句。 程序既是軟件的固有部分，又是軟件研究的對(duì)象，程序的質(zhì)量決定著軟件的質(zhì)量。 衡量一個(gè)程序的質(zhì)量，除了對(duì)程序結(jié)構(gòu)進(jìn)行靜態(tài)考察外，還必須考察其執(zhí)行過(guò)程。 與執(zhí)行無(wú)關(guān)的特性稱之為程序的靜態(tài)特性， 與執(zhí)行有關(guān)的特性稱之為程序的動(dòng)態(tài)特性。,程序的特征,程序描述解決某一問(wèn)題的特定任務(wù)與功能，回答“解決什么問(wèn)題”或“做什么”的問(wèn)題。 程序遵循一定的規(guī)則和步驟，而不是指令或語(yǔ)句的隨意堆砌。 程序的執(zhí)行者是計(jì)算機(jī)。 程序是由人來(lái)編寫

42、或設(shè)計(jì)的，是人針對(duì)要處理和解決的問(wèn)題而設(shè)計(jì)的求解方法和步驟交由計(jì)算機(jī)操作、運(yùn)算和處理的說(shuō)明。 程序的運(yùn)行是自動(dòng)完成的。 程序是算法的程序設(shè)計(jì)語(yǔ)言描述，但程序并不一定就是算法，因?yàn)槌绦驔](méi)有有窮性要求。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問(wèn)題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,解決一個(gè)實(shí)際問(wèn)題的一般過(guò)程,明確問(wèn)題要求。 建立數(shù)學(xué)模型。 算法設(shè)計(jì)。 編寫程序。 調(diào)試程序。 運(yùn)行及結(jié)果分析。 編寫程序文檔。,程序文檔的內(nèi)容,編寫文檔是最容易被忽視了的一個(gè)重要環(huán)節(jié)。沒(méi)有文檔資料對(duì)于軟件的維護(hù)會(huì)帶來(lái)許多困難，即使是設(shè)計(jì)者自己也不例外。文檔

43、資料要寫得完整、清楚和準(zhǔn)確，一般應(yīng)包含如下內(nèi)容： 算法或程序的功能描述和適用范圍； 運(yùn)行環(huán)境，包括機(jī)型、操作系統(tǒng)平臺(tái)、語(yǔ)言種類、占用空間等； 使用說(shuō)明，即使用該程序的操作命令、I/O格式、各種情況下的操作等說(shuō)明； 流程圖及說(shuō)明； 程序清單及注釋。,實(shí)現(xiàn)策略,在拿到一個(gè)設(shè)計(jì)問(wèn)題之后，有兩種不同的方法可供選擇： 一種是自頂向下逐步求精細(xì)化； 一種是自底向上逐步堆砌積累。 由于人腦思維很難一下子觸及問(wèn)題細(xì)節(jié)，所以自底向上方法較難運(yùn)用；即使運(yùn)用，也難設(shè)計(jì)出清晰的程序?qū)哟谓Y(jié)構(gòu)。 結(jié)構(gòu)化程序設(shè)計(jì)提倡自頂向下逐步求精細(xì)化的分析設(shè)計(jì)方法，從求解問(wèn)題本身到得出一系列基本操作逐層次展開(kāi)細(xì)化，是一種將問(wèn)題求解方法由

44、抽象逐步到具體化的過(guò)程。 采用自頂向下逐步求精細(xì)化的設(shè)計(jì)方法，易于保證和驗(yàn)證程序的正確性。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問(wèn)題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,程序調(diào)試,程序調(diào)試是開(kāi)發(fā)過(guò)程中最艱巨的腦力勞動(dòng)。面對(duì)錯(cuò)誤征兆，如何在浩如煙海的程序元素中找出有錯(cuò)誤的元素，這是調(diào)試過(guò)程中最關(guān)鍵的技術(shù)問(wèn)題。 現(xiàn)有的調(diào)試技術(shù)有如下三類： 輸出存儲(chǔ)器內(nèi)容。常以八進(jìn)制或十六進(jìn)制形式打印出存儲(chǔ)器內(nèi)容并檢查分析。 在程序中插入打印語(yǔ)句，調(diào)試結(jié)束后要將為了調(diào)試而插入的語(yǔ)句刪掉。 借助調(diào)試工具。調(diào)試工具可以提供程序動(dòng)態(tài)行為的有關(guān)信息，但不需要修

45、改源程序。例如，在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è)想并列出所有可能產(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)是否

46、都符合設(shè)計(jì)要求，這種方法稱之為白盒子測(cè)試。 無(wú)論使用哪一種方法，對(duì)程序的窮舉測(cè)試是不可能的，我們所能做到的是通過(guò)有限的測(cè)試盡可能多地發(fā)現(xiàn)錯(cuò)誤。測(cè)試只能發(fā)現(xiàn)錯(cuò)誤，而不能保證程序沒(méi)有錯(cuò)誤。查錯(cuò)的關(guān)鍵在于設(shè)計(jì)好測(cè)試用例，即確定一組最有可能發(fā)現(xiàn)某個(gè)或某類錯(cuò)誤的測(cè)試數(shù)據(jù)的設(shè)計(jì)。,常用的測(cè)試用例設(shè)計(jì)方法,邏輯覆蓋。它是一種白盒子測(cè)試技術(shù)。常用的邏輯覆蓋有語(yǔ)句覆蓋、分支覆蓋、條件覆蓋、分支/條件覆蓋、多重覆蓋和循環(huán)覆蓋等。 等價(jià)類劃分。是一種黑盒子測(cè)試技術(shù)。 邊界值分析。是一種黑盒子測(cè)試技術(shù)。 圖形技術(shù)。它提供設(shè)計(jì)測(cè)試用例的工具，常見(jiàn)的有因果圖和程序圖。 測(cè)試的目的是為了發(fā)現(xiàn)錯(cuò)誤，而糾錯(cuò)則是確定錯(cuò)誤在程序中

47、的確切位置和性質(zhì)并改正它。糾錯(cuò)的關(guān)鍵在于確定錯(cuò)誤的位置（即錯(cuò)誤定位），常用的糾錯(cuò)技術(shù)有試探法、回溯法、對(duì)分查找法、歸納法和演譯法。,1.4 算法與程序,1.4.1 程序的基本概念 1.4.2 問(wèn)題求解與實(shí)現(xiàn)策略 1.4.3 程序調(diào)試與查錯(cuò)策略 1.4.4 程序設(shè)計(jì)方法概述,程序設(shè)計(jì)方法概述,程序是軟件的重要組成部分，程序設(shè)計(jì)是軟件開(kāi)發(fā)的重要方面。 程序設(shè)計(jì)方法對(duì)程序設(shè)計(jì)工作的質(zhì)量以及所設(shè)計(jì)出來(lái)的程序的質(zhì)量影響重大，因而對(duì)程序設(shè)計(jì)方法的研究也越來(lái)越受到人們的重視。 程序設(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ì)過(guò)程是結(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ì),