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