算法設(shè)計(jì)與分析,湖南人文科技學(xué)院計(jì)算機(jī)系 授課：肖敏雷 郵箱：minlei_,關(guān)于本課程,課程目的：計(jì)算機(jī)算法設(shè)計(jì)與分析導(dǎo)引 不是一門試驗(yàn)或程序設(shè)計(jì)課程 也不是一門數(shù)學(xué)課程 教材：計(jì)算機(jī)算法設(shè)計(jì)與分析-王曉東 前導(dǎo)課：數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì) 參考資料： 算法設(shè)計(jì)與分析C+語言描述 陳慧南編 電子工業(yè)出版社 計(jì)算機(jī)算法基礎(chǔ)(第三版) 余祥宣 華中科技大學(xué),本課程的主要任務(wù) 算法學(xué)習(xí)將涉及5個(gè)方面的內(nèi)容： 1）設(shè)計(jì)算法：創(chuàng)造性的活動(dòng) 2）表示算法：思想的表示形式 3）確認(rèn)算法：證明算法的正確性 程序的證明 4）分析算法：算法時(shí)空特性分析 5）測(cè)試程序：調(diào)試和作出時(shí)空分布圖 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ),第1章 算法概述,學(xué)習(xí)要點(diǎn): 理解算法的概念。 理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。 掌握算法的計(jì)算復(fù)雜性概念。 掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。 掌握用C+語言描述算法的方法。,算法的研究?jī)?nèi)容,問題是否可解 1930s 研究集中于判斷特定問題在計(jì)算機(jī)上是否可解，基本方法為：選定一個(gè)計(jì)算模型，觀察是否能在該模型上創(chuàng)建能解決問題的算法。這些計(jì)算模型包括：Post machines、Turing machines等。這一階段的成果是：大部分問題為不可解。 高效率的解決方法 隨著計(jì)算機(jī)的發(fā)展和數(shù)據(jù)資源的增加，算法研究轉(zhuǎn)向針對(duì)可解的問題，找到高效率的解決方法。,算法的五個(gè)重要特性（其他教材的描述） 確定性、能行性、輸入、輸出、有窮性,1）確定性：算法的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：不符合確定性的運(yùn)算 5/0 將6或7與x相加,2）能行性（教材中沒有） 算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在有限的時(shí)間內(nèi)完成；它們可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。 例：整數(shù)的算術(shù)運(yùn)算是“能行”的 實(shí)數(shù)的算術(shù)運(yùn)算是“不能行”的，某些實(shí)數(shù)只能由無限長(zhǎng)的十進(jìn)制數(shù)表示，像這樣的2個(gè)數(shù)相加就違背了能行性這一特性。,3）輸入 每個(gè)算法有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合定義域（或值域）,4）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。,5）有窮性 一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。,程序(Program),程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。 程序可以不滿足算法的性質(zhì)(4)（有限性）。 例如操作系統(tǒng)，是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。 操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問題，每一個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。,問題求解(Problem Solving),理解問題,精確解或近似解 選擇數(shù)據(jù)結(jié)構(gòu) 算法設(shè)計(jì)策略,設(shè)計(jì)算法,算法復(fù)雜性分析,算法復(fù)雜性 = 算法所需要的計(jì)算機(jī)資源 算法的時(shí)間復(fù)雜性T(n)； 算法的空間復(fù)雜性S(n)。 其中n是問題的規(guī)模（輸入大?。?。,算法的時(shí)間復(fù)雜性,（1）最壞情況下的時(shí)間復(fù)雜性 Tmax(n) = max T(I) | size(I)=n （2）最好情況下的時(shí)間復(fù)雜性 Tmin(n) = min T(I) | size(I)=n （3）平均情況下的時(shí)間復(fù)雜性 Tavg(n) = 其中I是問題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。,對(duì)于：T(n) , as n ; 如果存在：(T(n) - t(n) )/ T(n) 0 ，as n; 就稱：t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。 在數(shù)學(xué)上， t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n) 簡(jiǎn)單。 比如：當(dāng) T(n) n2+4nlogn+7時(shí)， t(n)的一個(gè)答案是n2,介紹幾個(gè)漸近分析的記號(hào),大O記號(hào) (上界) 記號(hào) (下界) 記號(hào) (同階) 小o記號(hào) （低階）,1 大O記號(hào),定義1 設(shè)函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0，使得當(dāng)nn0時(shí)，有f(n)cg(n)，則記做f(n) = O(g(n)，稱為大O記號(hào)（big Oh notation）。 一個(gè)算法具有O(g(n)的運(yùn)行時(shí)間，是指當(dāng)n足夠大時(shí)，算法的運(yùn)行時(shí)間不超過g(n）的常數(shù)倍， g(n)是它的一個(gè)上界。,例1 f(n) = 2n + 3 = O(n) 當(dāng)n3時(shí)，2n+33n，所以，可選c = 3，n0 = 3。對(duì)于nn0，f(n) = 2n + 33n，所以，f(n) = O(n)，即2n + 3O(n)。這意味著，當(dāng)n3時(shí)，例1的程序步不會(huì)超過3n，2n + 3 = O(n)。,例2 f(n) = 10n2 + 4n + 2 = O(n2) 對(duì)于n2時(shí)，有10n2 + 4n + 210n2 + 5n，并且當(dāng)n5時(shí)，5nn2，因此，可選c = 11, n0 = 5；對(duì)于nn0，f(n) = 10n2 + 4n + 211n2，所以f(n) = O(n2)。,例3 f(n) = n！= O(nn) 對(duì)于n1，有n(n 1)(n 2) 1nn，因此，可選c = 1，n0 = 1。對(duì)于nn0，f(n) = n！nn，所以，f(n) = O(nn)。,定理1 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多項(xiàng)式，且am0，則f(n) = O(nm)。 證明：取n0 = 1，當(dāng)nn0時(shí)，有 f(n)= amnm + am1nm1 + + a1n + a0 |am|nm + |am1|nm1 + + |a1|n + |a0| (|am| + |am1|/n + + |a1|/nm1 + |a0|/nm) nm (|am| + |am1| + + |a1| + |a0|) nm 可取c= |am| + |am1| + + |a1| + |a0|，定理得證。,漸近時(shí)間復(fù)雜度 使用大O記號(hào)及下面定義的幾種漸近表示法表示的算法時(shí)間復(fù)雜度，稱為算法的漸近時(shí)間復(fù)雜度（asymptotic complexity）。 只要適當(dāng)選擇關(guān)鍵操作，算法的漸近時(shí)間復(fù)雜度可以由關(guān)鍵操作的執(zhí)行次數(shù)之和來計(jì)算。一般地，關(guān)鍵操作的執(zhí)行次數(shù)與問題的規(guī)模有關(guān)，是n的函數(shù)。 關(guān)鍵操作通常是位于算法最內(nèi)層循環(huán)的語句。,【程序1】 矩陣乘法 for（i=0; in; i+） /比較運(yùn)算n+1次 for（j=0; jn; j+） /比較運(yùn)算n(n+1)次 cij=0; /n2 for（k=0; kn; k+） /比較運(yùn)算n2(n+1) cij+=aik*bkj; /n3 程序中所有語句執(zhí)行次數(shù)為：(n)=2n3+3n2+2n+1 漸進(jìn)時(shí)間復(fù)雜度為：O(n3)； 如果將cij+=aik*bkj; 看成關(guān)鍵操作，它的執(zhí)行次數(shù)n3，同樣也可以得到O(n3)。,2 記號(hào),定義2 設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù) c和n0，使得當(dāng)nn0時(shí)，有f(n)cg(n)，則記做f(n)= (g(n)，稱為記號(hào)（omega notation）。 用于表示一個(gè)算法運(yùn)行時(shí)間的下界。稱一個(gè)算法具有(g(n)的運(yùn)行時(shí)間，是指當(dāng)n足夠大時(shí)，該算法至少需要g(n)的常數(shù)倍的時(shí)間量。,例1 f(n) = 2n + 3 = (n) 對(duì)所有n，2n+32n，可選c = 2，n0=0。對(duì)于nn0，f(n) = 2n+32n，所以，f(n) = (n)，即2n + 3(n)。,f(n) = 2n + 3 = O(n) 當(dāng)n3時(shí)，2n+33n，所以，可選c = 3，n0 = 3。對(duì)于nn0，f(n) = 2n + 33n，所以，f(n) = O(n)，即2n + 3O(n)。這意味著，當(dāng)n3時(shí)，例1的程序步不會(huì)超過3n，2n + 3 = O(n)。,例2 f(n) = 10n2 + 4n + 2 = (n2) 對(duì)所有n，10n2 + 4n + 210n2，可選c = 10，n0 = 0。對(duì)于nn0，f(n) = 10n2 + 4n + 210n2，所以，f(n) = (n2)。,f(n) = 10n2 + 4n + 2 = O(n2) 對(duì)于n2時(shí)，有10n2 + 4n + 210n2 + 5n，并且當(dāng)n5時(shí)，5nn2，因此，可選c = 11, n0 = 5；對(duì)于nn0，f(n) = 10n2 + 4n + 211n2，所以f(n) = O(n2)。,定理2 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多項(xiàng)式，且am0，則f(n) = (nm)。 證明：略。,3 記號(hào),定義3 設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在正常數(shù)c1，c2和n0，使得當(dāng)nn0時(shí)，有c1 g(n)f(n)c2 g(n)，則記做f(n) = (g(n)，稱為記號(hào)（Theta notation）。 用于表示算法運(yùn)行時(shí)間具有與g(n)相同的階。稱一個(gè)算法具有(g(n)的運(yùn)行時(shí)間，是指當(dāng)n足夠大時(shí)，該算法的運(yùn)行時(shí)間大約為g(n)的常數(shù)倍的時(shí)間量。,例1 f(n) = 2n + 3 = (n)，即2n + 3(n)。 例2 f(n) = 10n2 + 4n + 2 = (n2)。 定理3 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多項(xiàng)式，且am0，則f(n) = (nm)。,4 小o記號(hào),定義4 f(n) = o(g(n)當(dāng)且僅當(dāng)f(n) = O(g(n)且f(n) (g(n) 用于表示算法運(yùn)行時(shí)間f(n) 的階比g(n)低。 例1 f(n)=2n+3=o(n2)，即2n+3o(n2)。,計(jì)算時(shí)間的數(shù)量級(jí)對(duì)算法有效性的影響 數(shù)量級(jí)的大小對(duì)算法的有效性有決定性的影響。 例：假設(shè)解決同一個(gè)問題的兩個(gè)算法，它們都有n個(gè)輸入，計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運(yùn)算。 n=2048：分別需要4194304和22528次運(yùn)算。 分析：在n加倍的情況下，一個(gè)(n2)的算法計(jì)算時(shí)間增長(zhǎng)4 倍，而一個(gè)(nlogn)算法則只用兩倍多一點(diǎn)的時(shí)間即 可完成。,多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界的算法。 常見的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3) 指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時(shí)間限界函數(shù)： (2n) (n！) (nn) 說明：當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間 算法在計(jì)算時(shí)間上非常懸殊。,算法分類（計(jì)算時(shí)間）,典型的計(jì)算時(shí)間函數(shù)曲線,當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行具有比(nlogn)復(fù)雜度還高的算法是比較困難的。 指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。 要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算機(jī)的速度。,計(jì)算時(shí)間函數(shù)值比較,一個(gè)問題可以設(shè)計(jì)不同的算法來求解，針對(duì)同一個(gè)問題的算法也許基于完全不同的思路。 求兩個(gè)整數(shù)的最大公約數(shù)可以采用歐幾里德算法，也可以采用連續(xù)整數(shù)檢測(cè)算法，兩種算法的解題速度會(huì)有明顯的差異。 同一個(gè)算法也可以采用不同的形式來表示。例如，歐幾里德算法可以寫成遞歸形式，也可以寫成迭代形式。,歐幾里德算法(輾轉(zhuǎn)相除法) 計(jì)算兩個(gè)整數(shù)m和n（0mn)的最大公約數(shù)，記為gcd(m, n)。 輾轉(zhuǎn)相除法：若m=0，則n和m的最大公約數(shù)等于n；若m0，則n和m的最大公約數(shù)等于m和用n除m的余數(shù)的最大公約數(shù)。 注：輾轉(zhuǎn)相除法是由古希臘歐幾里德（約公元前330-275年）在他的幾何原本中提出的。,【程序1】 歐幾里德遞歸算法 void Swap(int ,【程序2】 歐幾里德迭代算法 int Gcd(int m,int n) if (m=0)return n; if (n=0)return m; if (mn) Swap(m,n); while(m0) int c=n%m;n=m;m=c; return n; ,【程序3】 Gcd的連續(xù)整數(shù)檢測(cè)算法 int Gcd(int m,int n) if (m=0)return n; if (n=0)return m; int t=mn?n:m; while (m%t | n%t) t-; return t; ,作業(yè): P5 算法分析題:1、2、3、4、5 P6 算法實(shí)現(xiàn)題：1,漢諾塔問題（tower of Hanoi） 假定有三個(gè)塔座：X，Y，Z，在塔座X上有n個(gè)直徑大小各不相同，按圓盤大小從小到大編號(hào)為1，2，n的圓盤?，F(xiàn)要求將X塔座上n個(gè)圓盤移到塔座Y上，并仍按同樣順序疊排。 圓盤移動(dòng)時(shí)必須遵循下列規(guī)則： （1）每次只能移動(dòng)一個(gè)圓盤； （2）圓盤可以加到塔座X，Y，Z中任意一個(gè)上； （3）任何時(shí)刻都不能將一個(gè)較大的圓盤放在較小的圓盤之上。,第一次實(shí)驗(yàn) C/C+環(huán)境及遞歸算法,漢諾塔問題 void Move(char x, char y) /將第n個(gè)圓盤從塔座x移到塔座y的頂部 cout “ y endl; ,void Hanoi(int n, char x, char y, char z) /將x上的n個(gè)圓盤移到y(tǒng)上順序不變，借助于z if (n0) Hanoi(n-1, x, z, y); /將x上的n-1個(gè)圓盤移到z上順序不變，借助于y Move(x,y); Hanoi(n-1, z, y, x); /將z上的n-1個(gè)圓盤移到y(tǒng)上順序不變，借助于z ,排列問題 設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。 設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。 集合X中元素的全排列記為perm(X)。 (ri)perm(X)表示