《算法與數(shù)據(jù)結(jié)構(gòu)》第1章算法與程序ppt.ppt

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