【正文】 {m=n。 r=m%n。 } 運行結(jié)果： 請輸入兩個正整數(shù)： 56 32 56和 32的最大公約數(shù)是： 8 第 1章 算法與程序 算法的基本概念 算法的表示 算法的設(shè)計與評價 算法與程序 算法的設(shè)計與評價 評價算法的標準 算法的環(huán)路復(fù)雜度 算法的時空效率 常見的算法設(shè)計方法 評價算法的標準 ?評價一個算法優(yōu)劣的五條標準： ?正確性 ?可讀性 ?健壯性 ?高效性 ?簡潔性 ?一個好的算法是滿足這五條標準要求的算法 。 ?這就要求算法中的每一個步驟的描述是準確無歧義的 ， 并且是可以執(zhí)行的； ?要求算法能夠滿足問題要求 ， 并在有限步驟內(nèi)獲得結(jié)果； ?否則就不具備正確性要求 ， 更談不上解決給定的實際問題了 。 評價算法的“ 正確性 ” 標準（續(xù)） ?在將算法用程序語言表示為特定語言的程序后還必須注意： ?程序中不含有語法錯誤； ?對于一切合法的輸入數(shù)據(jù) ， 程序能夠產(chǎn)生滿足要求的輸出結(jié)果； ?對于一切非法的輸入數(shù)據(jù) ， 程序能夠得出滿足規(guī)格說明的結(jié)果； ?對于精心選擇的 ， 甚至是帶有刁難性的典型測試數(shù)據(jù) ，程序都有滿足要求的輸出結(jié)果 。 ?算法的可讀性好是保證正確性的前提，良好的可讀性有利于人們理解算法思想，減少出錯機會，便于檢查和修改。 評價算法的“ 健壯性 ” 標準 ?算法對意外情況的反映能力要強。 評價算法的“ 高效性 ” 標準 ?算法的執(zhí)行效率要高 。 ? 時間效率 是通過該算法轉(zhuǎn)化的程序在計算機上運行的時間耗費來確定 ， 在算法設(shè)計與分析階段用執(zhí)行基本操作的次數(shù) （ 是問題規(guī)模的函數(shù) ） 相對于問題規(guī)模的漸近階來表示 。一個高效算法是指執(zhí)行算法耗費時間少 ， 使用輔助存儲空間小的算法 。 ?對于同一問題所設(shè)計的不同算法 ， 越簡潔明了的越好 。 評價算法的標準（續(xù)） ?在評價一個算法時，要對這五個方面綜合考慮，不要片面追求某一指標。 算法的設(shè)計與評價 評價算法的標準 算法的環(huán)路復(fù)雜度 算法的時空效率 常見的算法設(shè)計方法 算法的環(huán)路復(fù)雜度 ?算法的復(fù)雜性很大程度上取決于控制流程的復(fù)雜性。 ?基于這一種觀點，針對算法的流程圖表示，我們先介紹算法的環(huán)路復(fù)雜度的概念和度量方法。 ?所謂 程序圖 可以看成是退化了的流程圖，也就是把算法（或程序）流程圖中的每個處理框都退化成為一個點，原來連接不同框之間的流程線變成連接不同點的有向弧，這樣得到的有向圖稱之為程序圖。 算法的環(huán)路復(fù)雜度舉例 ?例如圖 11所示的歐幾里德算法的流程圖所對應(yīng)的程序圖如圖 13所示。 環(huán)路復(fù)雜度的計算方法舉例 ?例 1：前述的歐幾里德算法的程序圖 （ 圖 13） 中 ，有 8條有向弧和 7個結(jié)點 ， 由該公式可以確定其環(huán)路復(fù)雜度如下： V(G)=87+1=2 圖 14 程序圖的復(fù)雜度 ?例 2：如圖 14所示的程序圖中 ， 有 11條弧和 7個結(jié)點 ， 由該公式 可如下確定其環(huán)路復(fù)雜度： V(G)=117+1=5 算法的環(huán)路復(fù)雜度的計算方法（續(xù)） ?除了應(yīng)用上述的公式法計算之外 ， 還有如下的兩種方法可以用來確定程序圖的環(huán)路復(fù)雜度： ? 觀察法 ， 即觀察強連通的程序圖在平面上所圍成的獨立區(qū)域的個數(shù) 。 算法的環(huán)路復(fù)雜度的計算方法（續(xù)） ? 利用判定語句計算法 ， 即把程序圖中所有出現(xiàn)的分支結(jié)點處所需要的判定的總個數(shù)加起來再加 1。 如圖 13中只有一個結(jié)點 （ 第四個 ） 是分支結(jié)點且為二路分支 ， 故所需要的判定為一個 ， 其環(huán)路復(fù)雜度 （ 即環(huán)路數(shù) ） 為 2；而圖 14中有兩個結(jié)點 （ 上數(shù)第二個和左下結(jié)點 ） 是分支結(jié)點且結(jié)點都為三路分支 ， 故所需的判定為 2+2=4個 ， 其環(huán)路復(fù)雜度為 5。 在設(shè)計算法時 ， 一般地應(yīng)控制模塊的環(huán)路復(fù)雜度在 10以內(nèi)為宜 。然而它也有許多不足之處，如沒有區(qū)分不同類型控制流的不同復(fù)雜性（如選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)之間，嵌套選擇結(jié)構(gòu)和多選擇結(jié)構(gòu)之間的不同復(fù)雜性）等。 算法的設(shè)計與評價 評價算法的標準 算法的環(huán)路復(fù)雜度 算法的時空效率 常見的算法設(shè)計方法 算法的時空效率 ?如果算法是用 NS圖 、 偽代碼 、 程序語言或其它方式表示的 ， 要度量其環(huán)路復(fù)雜度需要先把它們的表示轉(zhuǎn)化為流程圖表示 ， 然后把流程圖退化為程序圖再確定其環(huán)路數(shù) 。 ?下面我們再介紹一種適應(yīng)面更廣泛的定性評價算法復(fù)雜度的方法 ， 即 大 O方法 。 ?而每條語句的執(zhí)行時間則應(yīng)該是執(zhí)行該語句一次所需的時間與該語句執(zhí)行的次數(shù) （ 也稱之為頻度 ） 的乘積 。 所以 ， 我們可以假設(shè)執(zhí)行每條語句所需的時間均為單位時間 。 大 O方法計算舉例 ?兩個 n*n矩陣相乘的算法描述如下： ⑴ for(i=1。i++) /* n+1次 */ ⑵ for(j=1。j++) /* n(n+1)次 */ ⑶ {c[i][j]=0。k=n。 /* n3次 */ ⑹ } 大 O方法計算舉例（續(xù)） ?其中 ， 每一條語句的頻度說明在注釋中 。并且當 n→∞ 時 ， T(n)/n3→ 2。引入大 O記號可記作 T(n)=O(n3) 時間復(fù)雜度 ?引入大 O記號表示的算法的時間耗費 T(n)通常稱之為算法的 時間復(fù)雜度 ， 如矩陣相乘算法的時間復(fù)雜度為 O(n3)。 ?問題的規(guī)模 是指算法中要處理的數(shù)據(jù)量的規(guī)模 ，通常用一個整型量 n來表示 。 時間復(fù)雜度（續(xù)） ?時間復(fù)雜性的漸近階表示 ， 是對算法時間性能優(yōu)劣的宏觀定性評價 。 ?由于是宏觀的定性評價 ， 算法中頻度最大的語句的頻度 ， 與算法中每條語句頻度的和 T(n)是同階函數(shù)； ?所以人們在計算算法時間復(fù)雜度時 ， 往往只需考慮算法中頻度最大的語句的頻度就可以了 。 for(i=1。i++) for(j=1。j++) for(k=1。k++) x++。 簡明實用的程序分析法則 ?執(zhí)行一條基本操作如讀寫或賦值語句等 ， 需要 O(1)的時間花費 。 ?對于選擇結(jié)構(gòu)如 if語句 ， 主要時間耗費是執(zhí)行 then子句或else子句所用的時間；此外 ， 檢驗條件還需用 O(1)的時間 。 ?對于循環(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)體 ⑸ 開始分析：