程序設(shè)計(jì)算法概述.ppt

1、算法概述,楊秋妹 ,程序=數(shù)據(jù)結(jié)構(gòu)+算法,乘汽車旅行的人總希望找出到目的地的盡可能的短的行程。如果有一張地圖并在圖上標(biāo)出每對十字路口之間的距離，如何找出這一最短行程？,建立解題模型數(shù)據(jù)結(jié)構(gòu) 解決方法,什么是算法,算法是一個(gè)有窮的解決問題的指令序列。每條指令都必須有清楚的含義并且在有窮長的時(shí)間內(nèi)用有窮的動作完成。 一個(gè)算法無論接受任何輸入，都必須在有窮步內(nèi)停止。,排序問題,輸入：由n個(gè)數(shù)構(gòu)成的一個(gè)序列 輸出：對輸入序列的一個(gè)排列（重排），使得a1=a2=an 算法：插入排序，冒泡排序，快速排序，合并排序等,算法的幾個(gè)特性,算法是指解決問題的一種方法或一個(gè)過程。 滿足性質(zhì)： (1)輸入：有零個(gè)或多

2、個(gè)外部提供的量作為算法的輸入。 (2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。 (3)確定性：組成算法的每條指令是清晰，無歧義的。 (4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。,什么是程序,程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn) 程序可以不滿足算法的有窮性,算法的描述,自然語言； 程序設(shè)計(jì)語言； 類程序語言,算法可以解決的問題,人類基因的目標(biāo)是找出人類DNA的所有十萬種基因，確定構(gòu)成人類DNA的30億種化學(xué)基對的各種序列，將這些信息存儲在數(shù)據(jù)庫中，并開發(fā)出用于進(jìn)行這方面數(shù)據(jù)分析的工具。 因特網(wǎng)快速地訪問和檢索大量的信息,電子商務(wù)保持信用卡號、密碼、銀行結(jié)單等信息的私

3、密性，公共密鑰加密技術(shù)和數(shù)字簽名技術(shù) 制造業(yè)和其他商業(yè)應(yīng)用中，是否能最有效地分配稀有資源，例如，石油公司確定在何處打井，以求最大化預(yù)期效益；美國總統(tǒng)候選人希望確定該把宣傳的資金花在何處，以求贏得競選的可能性最大；,常用的算法設(shè)計(jì)方法,遞歸法（Recursion） 分治法(Divide-and Conquer)、 貪心法(Greedy) 動態(tài)規(guī)劃(Dynamic Programming)、 回溯（Backtracking） 分支限界法（Branch and Bound） 近似算法(Approximation),問題求解,理解問題,精確解或近似解 選擇數(shù)據(jù)結(jié)構(gòu) 算法設(shè)計(jì)策略,設(shè)計(jì)算法,算法的設(shè)計(jì)目

4、標(biāo),算法應(yīng)易于理解、編程和調(diào)試 算法應(yīng)盡可能有效地利用計(jì)算機(jī)的資源，特別地，應(yīng)盡可能快地運(yùn)行,好算法的判斷標(biāo)準(zhǔn),1.正確性 2.健壯性 3.時(shí)間復(fù)雜性 4.空間復(fù)雜性 5.可讀性 6. 靈活性（Flexibility）、可重用性(Reuseabale)等,算法復(fù)雜度分析,算法復(fù)雜性,體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源多少上 所需資源越多，該算法的復(fù)雜性越高 所需資源越少，該算法的復(fù)雜性越低,時(shí)間復(fù)雜性：算法執(zhí)行需要的時(shí)間資源 空間復(fù)雜性：算法執(zhí)行需要的空間資源,百雞問題,公元5世紀(jì)末,我國古代數(shù)學(xué)家張丘建在他所撰寫的算經(jīng)中，提出了這樣的一個(gè)問題：“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一

5、。百錢買百雞，問雞翁、母、雛各幾何？”,a：公雞數(shù) b：母雞數(shù) c：小雞數(shù) a + b + c = 100 5a + 3b + c/3 = 100 c % 3 = 0,void chicken_question(int n, int ,算法有三重循環(huán) 內(nèi)循環(huán)體的執(zhí)行次數(shù)為(n+1)(n+1)(n+1),void chicken_problem(int n, int ,算法有兩重循環(huán) 內(nèi)循環(huán)體執(zhí)行次數(shù)為(n/5 + 1)(n/3 + 1),貨郎擔(dān)問題,貨郎擔(dān)問題是一個(gè)經(jīng)典問題。某售貨員要到若干個(gè)城市銷售貨物，已知各城市之間的距離，要求售貨員選擇出發(fā)的城市及旅行路線，使每一個(gè)城市僅經(jīng)過一次，最后回

6、到原出發(fā)城市，而總路程最短。,用圖的頂點(diǎn)代表城市，邊的權(quán)重表示城市間的距離，這個(gè)問題可以轉(zhuǎn)化為求一個(gè)圖的最短哈密頓回路,哈密頓回路可以定義為n1個(gè)相鄰節(jié)點(diǎn)vi0,vin-1,vi0的一個(gè)序列 可以通過生成n1個(gè)中間城市的組合來得到所有的旅行路線，計(jì)算這些路線的長度，然后求得最短的線路,算法時(shí)間復(fù)雜度 O（n！）,對于所設(shè)計(jì)的算法，如何說明它是有效的？ 如果對于同一問題，有多個(gè)不同的解法，如何知道哪一個(gè)算法更有效？ 算法復(fù)雜性分析目的在于選擇合適的算法和改進(jìn)算法,實(shí)驗(yàn)測量法（實(shí)際執(zhí)行時(shí)間、執(zhí)行指令的條數(shù)） 把算法用某種程序設(shè)計(jì)語言實(shí)現(xiàn)并在計(jì)算機(jī)上運(yùn)行，計(jì)算實(shí)際運(yùn)行時(shí)間,如何進(jìn)行算法時(shí)間效率分析,

7、例：讓一臺更快的、運(yùn)行插入排序的計(jì)算機(jī)（計(jì)算機(jī)A）與一臺較慢的、運(yùn)行合并排序的計(jì)算機(jī)（計(jì)算機(jī)B）進(jìn)行比較。兩者都要對一個(gè)大小為一百萬個(gè)數(shù)的數(shù)組進(jìn)行排序。假設(shè)計(jì)算機(jī)A每秒能執(zhí)行10億條指令，而計(jì)算機(jī)B每秒只能執(zhí)行一千萬條指令。,計(jì)算機(jī)A花費(fèi)的時(shí)間： 2*（106）2條指令/109條指令/秒2000秒 計(jì)算機(jī)B花費(fèi)的時(shí)間： 50*106lg106條指令/107條指令/秒100秒,影響實(shí)驗(yàn)測量時(shí)間的因素,程序的輸入長度 編譯程序生成目標(biāo)代碼的質(zhì)量 計(jì)算機(jī)指令的質(zhì)量和速度 算法本身的優(yōu)劣,實(shí)驗(yàn)測量法（實(shí)際執(zhí)行時(shí)間、執(zhí)行指令的條數(shù)） 缺點(diǎn)： 必須先運(yùn)行根據(jù)算法編制的的程序；所得的時(shí)間統(tǒng)計(jì)量依賴于計(jì)算機(jī)的

8、硬件、軟件等環(huán)境因素，容易掩蓋算法本身的優(yōu)劣。,事前分析(估計(jì))法 忽略機(jī)器性能對運(yùn)行時(shí)間的影響 使用問題輸入規(guī)模為參數(shù)的函數(shù)來衡量,算法執(zhí)行的時(shí)間是算法優(yōu)劣和問題規(guī)模的函數(shù)。評價(jià)一個(gè)算法的優(yōu)劣，可以在相同的規(guī)模下，考察算法執(zhí)行時(shí)間的長短來進(jìn)行判斷。,選定輸入規(guī)模,規(guī)模越大，需要的運(yùn)行時(shí)間越長 使用以算法輸入規(guī)模n為參數(shù)的函數(shù)T（n）研究算法效率,運(yùn)行時(shí)間的度量單位,找出算法中最重要的操作基本操作，計(jì)算它們的運(yùn)行次數(shù) 基本操作通常是算法最內(nèi)層循環(huán)中最費(fèi)時(shí)的操作,例：A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求其最大和最小元素的算法和時(shí)間復(fù)雜性 void MinMax(double A, int n

9、, double max, double min ) double max, min; max=min=A0; for ( k=1; kmax ) max=Ak; if ( Akmin ) min=Ak; ,T（n） 2（n1）,評價(jià)算法運(yùn)行時(shí)間的標(biāo)準(zhǔn),最好時(shí)間復(fù)雜度 算法對具有長度為n的任何輸入的最短運(yùn)行時(shí)間 最壞時(shí)間復(fù)雜度 算法對具有長度為n的任何輸入的最長運(yùn)行時(shí)間 平均時(shí)間復(fù)雜度 在平均輸入下，算法的運(yùn)行時(shí)間。通常假設(shè)給定長度的各種輸入概率相同。,例:A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出確定給定實(shí)數(shù)K是否在A中的算法及其時(shí)間復(fù)雜性,SequentialSearch(A0n-1,K) i

10、 = 0 while i n and Ai != K do i = i + 1 if i n return i else return -1 ,最好時(shí)間復(fù)雜度T（n）1 最壞時(shí)間復(fù)雜度 T（n） n 平均時(shí)間復(fù)雜度 T（n）p（n1）/2n（1p）,常用最壞運(yùn)行時(shí)間估計(jì),平均運(yùn)行時(shí)間難以計(jì)算 假設(shè)每一個(gè)輸入具有相同的概率有時(shí)沒有意義 平均運(yùn)行時(shí)間常常與最壞運(yùn)行時(shí)間有相同的數(shù)量級 實(shí)際問題中，算法的運(yùn)行時(shí)間常常達(dá)到這個(gè)上界,漸近時(shí)間復(fù)雜性,指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級,一般說來，當(dāng)n單調(diào)增加且趨于時(shí)，T（n）也將單調(diào)趨于 對于T（n），如果存在g（n），使得當(dāng)n 時(shí)，有 T

11、（n） g（n）/ T（n）0 那么，我們說g（n）是T（n）當(dāng)n趨于時(shí)的漸進(jìn)復(fù)雜性,T(n)= 3n2+4nlogn+7 g(n) = 3n2,當(dāng)n ，T（n) g（n） g（n）比T（n）簡單,幾個(gè)常見的漸進(jìn)符號,漸近上界符號O 漸近下界符號 緊漸近界記號符號,漸進(jìn)符號,漸近上界符號O f（n） O（g（n）的成立條件是： 對于所有足夠大的n，f（n）的上界由g（n）的常數(shù)倍所確定，即存在大于0的常數(shù)c和非負(fù)整數(shù)n0，使得： 對于所有n n0 ，有f（n） cg（n）,100n+5 O(n2),漸進(jìn)符號,漸近下界符號 f（n） （g（n）的成立條件是： 對于所有足夠大的n，f（n）的下界由

12、g（n）的常數(shù)倍所確定，即存在大于0的常數(shù)c和非負(fù)整數(shù)n0，使得： 對于所有n n0 ，有f（n） cg（n）,n3 (n2),漸進(jìn)符號,緊漸近界記號符號 f（n） （g（n）的成立條件是： 對于所有足夠大的n，f（n）的上界和下界都由g（n）的常數(shù)倍所確定，即存在大于0的常數(shù)c1、c2和非負(fù)整數(shù)n0，使得： 對于所有n n0 ，有c1g（n） f（n） c2g（n）,1/2n(n-1) (n2),根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則，如下這些規(guī)則也同樣適用和表示法 ： (1) O(f)+O(g)=O(max(f,g)； (2) O(f)+O(g)=O(f+g)； (3) O(f)O(g)=

13、O(fg)； (4) 如果g(N)=O(f(N)，則O(f)+O(g)=O(f)； (5) O(Cf(N)=O(f(N)，其中C是一個(gè)正的常數(shù)； (6) f=O(f)。,漸近分析記號的運(yùn)算性質(zhì),定理： 若 A（n）=amnm+a1n+a0 是關(guān)于n的m次多項(xiàng)式，則 A（n）=（nm） 此定理說明，當(dāng)要比較的兩個(gè)算法的漸進(jìn)復(fù)雜性的階不相同時(shí)，只要確定出各自的階 如f(n) = 20n2 + 5n + 10 g(n) = 3n5 + 2n3 + 100,算法的漸進(jìn)時(shí)間復(fù)雜性,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間度量記作T（n）= O（ f（n）。它表示隨問題規(guī)模n

14、的增大，算法執(zhí)行時(shí)間的增長率不會超過f（n），稱為算法的漸進(jìn)時(shí)間復(fù)雜性，簡稱時(shí)間復(fù)雜性。,算法效率分析,非遞歸算法 遞歸算法,例：找出n個(gè)元素的最大值,MaxElement(A0n-1) maxval = A0 For i = 1 to n-1 do if Ai maxval maxval = Ai return maxval ,n-1 T(n) = 1= n-1 i=1 = O(n),分析非遞歸算法效率的通用方案,決定用哪個(gè)（哪些）參數(shù)作為輸入規(guī)模的度量 找出算法的基本操作 檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模，如果還依賴其他特性則應(yīng)區(qū)分最差、平均及最優(yōu)效率 建立算法基本操作執(zhí)行次數(shù)的求

15、和公式 對求和公式求解，至少應(yīng)確定其增長次數(shù),遞歸算法的分析,一個(gè)過程在運(yùn)行時(shí)直接或間接地調(diào)用自己，則該過程稱為遞歸程序,例：計(jì)算階乘函數(shù)F（n）,F(n) if n = 0 return 1 else return F(n-1)*n ,時(shí)間復(fù)雜度遞歸公式(乘法步數(shù)) T(n) = T(n-1) + 1 (n0) T(0) = 0,T(n) = n= O(n),例：歸并排序,msort(int x,int aux,int s,int t) /*將xs.t歸并排序?yàn)閍uxs.t*/ if (s=t) auxs=xs; else m=(s+t)/2; msort(x,aux,s,m); msort

16、(x,aux,m+1,t); merge(aux,x,s,m,t); ,時(shí)間復(fù)雜度遞歸公式 T(n) = 2T(n/2) + n (n0) T(1) = 1,T(n) = O(nlogn),分析遞歸算法效率的通用方案,決定用哪個(gè)（哪些）參數(shù)作為輸入規(guī)模的度量 找出算法的基本操作 檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模，如果還依賴其他特性則應(yīng)區(qū)分最差、平均及最優(yōu)效率 對算法基本操作的執(zhí)行次數(shù)建立一個(gè)遞推關(guān)系式以及相應(yīng)的初始條件 求解遞歸關(guān)系式，至少確定其增長次數(shù),解遞歸方程,推測法 遞歸樹 主定理,推測法,T(n) = 4T(n/2) + n T(1) = O(1),推測T(n) = O(n3

17、) 推測T(n) = O(n2),遞歸樹,T(n) = aT(n/b) + f(n) T(1) = O(1),T(n) = f(n) + af(n/b) + a2f(n/b2) + + aLf(n/bL) n/bL = 1即L = logbn T(n) = 2T(n/2) + n,主定理,T(n) = 4T(n/2) + n a =4, b= 2 nlogba=n2; f(n) = n. CASE1: f(n) = O(n(logba)(= 1) T(n) = (n2).,T(n) = 4T(n/2) + n2 a =4, b= 2 n(logba)=n2; f(n) = n2. CASE2: f(n) = (n (logba) T(n) = (n2lgn).,T(n) = 4T(n/2) + n3 a =4, b= 2 n(logba)=n2; f(n) = n3 CASE3: f(n) = (n (logba + )(= 1),且af(n/b)=n3/2，取c1/2 T(n) = (n3).,基本的效率類型,常數(shù)、對數(shù)、線性、nlogn、平方、立方、指數(shù)、階乘 運(yùn)行時(shí)間為n的多項(xiàng)式的算法稱為好算法,算法設(shè)計(jì)的幾個(gè)原則,如果一個(gè)程序只用一、兩次，那么書寫和調(diào)試所用的時(shí)間比運(yùn)行程序時(shí)間大得多，因而算法應(yīng)易于理解和正確實(shí)現(xiàn) 如果一個(gè)算法只對小的輸入運(yùn)行，運(yùn)行時(shí)間增