第1章 算法概述

1、第1章 算法概述 算法分析與設(shè)計 課件 算法分析與設(shè)計design and analysis of computer algorithm 教材：計算機算法設(shè)計與分析( 教材：計算機算法設(shè)計與分析(第3版) 算法設(shè)計與分析 王曉東 編著 算法分析與設(shè)計 課件 課程簡介算法分析與設(shè)計是計算機的核心課程之一， 算法分析與設(shè)計是計算機的核心課程之一，在眾多的計 算機系統(tǒng)軟件和應(yīng)用軟件中都要用到本課程的內(nèi)容。 算機系統(tǒng)軟件和應(yīng)用軟件中都要用到本課程的內(nèi)容。它是操 作系統(tǒng)、編譯原理等課程的先行課程， 作系統(tǒng)、編譯原理等課程的先行課程，在計算機的理論體系 中占有極其重要的位置。 中占有極其重要的位置。 通過

2、本課程的學(xué)習， 通過本課程的學(xué)習，使同學(xué)把握算法分析與設(shè)計的基本 理論，使同學(xué)學(xué)會算法分析與設(shè)計的基本方法,把握 把握計算機科 理論，使同學(xué)學(xué)會算法分析與設(shè)計的基本方法 把握計算機科 學(xué)及應(yīng)用領(lǐng)域常見的有代表性的非數(shù)值算法及算法設(shè)計的若 干重要方法，并學(xué)會用這些算法解決實際問題。 干重要方法，并學(xué)會用這些算法解決實際問題。 本課程以算法設(shè)計策略為學(xué)問單元， 本課程以算法設(shè)計策略為學(xué)問單元，介紹算法設(shè)計方法 和分析技巧，這些策略包括遞歸技術(shù)、分治、動態(tài)規(guī)劃、貪 和分析技巧，這些策略包括遞歸技術(shù)、分治、動態(tài)規(guī)劃、 心算法、回溯法、分支限界法等策略，它們的內(nèi)容相對獨立。 心算法、回溯法、分支限界法等

3、策略，它們的內(nèi)容相對獨立。 其先修課為高等數(shù)學(xué)、程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)。 其先修課為高等數(shù)學(xué)、程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)。 算法分析與設(shè)計 課件 本課程主要內(nèi)容第1章 算法概述 第 2章 第 3章 第 4章 第 5章 第 6章 遞歸與分治策略 動態(tài)規(guī)劃 貪心算法 回朔法 分支限界法 算法分析與設(shè)計 課件 第1章 算法概述學(xué)習要點: 學(xué)習要點: 理解算法的概念。 理解什么是程序，程序與算法的區(qū)分和內(nèi)在聯(lián)系。 把握算法的計算簡單性概念。 把握算法漸近簡單性的數(shù)學(xué)表述。 算法分析與設(shè)計 課件 軟件(software):程序及其各種文檔資料的總稱 程序(algorithm)=算法+數(shù)據(jù)結(jié)構(gòu) 算法(procedur

4、e):解的描述(程序的靈魂) 數(shù)據(jù)結(jié)構(gòu)(data structure):現(xiàn)實世界的數(shù)據(jù)模型 語言(language):實現(xiàn)的工具 算法分析與設(shè)計 課件 算法(algorithm) 算法(algorithm)算法是指解決問題的一種方法或一個過程。 算法是若干指令的有窮序列，滿意性質(zhì)： (1)輸入 輸入：有外部供應(yīng)的量作為算法的輸入。 輸入 (2)輸出 輸出：算法產(chǎn)生至少一個量作為輸出。 輸出 (3)確定性 確定性：組成算法的每條指令是清楚，無歧義的。 確定性 (4)有限性 有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí) 有限性 行每條指令的時間也是有限的。 算法分析與設(shè)計 課件 程序(progra

5、m) 程序(program) 程序是算法 用某種程序設(shè)計語言的詳細實現(xiàn)。 程序可以不滿意算法的性質(zhì)(4)有限性 有限性。 有限性 例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因 而不是一個算法。 操作系統(tǒng)的各種任務(wù)可看成是單獨的問題，每一個問 題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。 該子程序得到輸出結(jié)果后便終止。 算法分析與設(shè)計 課件 算法的描述方法 自然語言 優(yōu)點：簡單理解 缺點：冗長、二義性 使用方法：粗線條描述算法思想 留意事項：避開寫成自然段 歐幾里德算法：輸入m和n; 求m除以n的余數(shù)r; 若r等于0,則n為最大公約數(shù)，算法 結(jié)束；否則執(zhí)行第步； 將n的值放在m中，將r的值

6、放在n中； 重新執(zhí)行第步。 算法分析與設(shè)計 課件 流程圖 優(yōu)點：流程直觀 缺點：缺少嚴密性、敏捷性 使用方法：描述簡潔算法 留意事項：留意抽象層次開頭 輸入m和n r=m % n r=0 n m=n;n=r 輸出n 結(jié)束 y 歐幾里德算法： 算法分析與設(shè)計 課件 程序設(shè)計語言 優(yōu)點：能由計算機執(zhí)行 缺點：抽象性差，對語言要求高 使用方法：算法需要驗證 留意事項：將算法寫成子函數(shù)int commonfactor(int m, int n) int r = m % n; while (r!=0) m = n; n = r; r = m % n; return n; 歐幾里德算法：#includei

7、ostream.h 算法分析與設(shè)計 課件 偽代碼 介于自然語言和程序設(shè)計語言之間的方法， 它采納某一程序設(shè)計語言的基本語法，操 作指令可以結(jié)合自然語言來設(shè)計。 優(yōu)點：表達力量強、抽象性強、簡單理解 歐幾里德算法：1. r = m % n;2. 循環(huán)直到r = 0; 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 輸出n; 算法分析與設(shè)計 課件 問題的求解(problem solving): 問題的求解(problem solving):1)問題的陳述用科學(xué)規(guī)范的語言,對所求解的問題做精確的描述. 用科學(xué)規(guī)范的語言,對所求解的問題做精確的描述. 2)建立數(shù)學(xué)模型通

8、過對問題的分析, 通過對問題的分析,找出其中的全部操作對象及操作對象之間 的關(guān)系并用數(shù)學(xué)語言加以描述. 的關(guān)系并用數(shù)學(xué)語言加以描述. 3)算法設(shè)計依據(jù)數(shù)學(xué)模型設(shè)計問題的計算機求解算法. 依據(jù)數(shù)學(xué)模型設(shè)計問題的計算機求解算法. 4)算法的正確性證明證明算法對一切合法輸入均能在有限次計算后產(chǎn)生正確輸出. 證明算法對一切合法輸入均能在有限次計算后產(chǎn)生正確輸出. 5)算法的程序?qū)崿F(xiàn)將算法正確地編寫成機器語言程序. 將算法正確地編寫成機器語言程序. 6)算法分析對執(zhí)行該算法所消耗的計算機資源進行估算. 對執(zhí)行該算法所消耗的計算機資源進行估算. 算法分析與設(shè)計 課件 算法設(shè)計的要求通常設(shè)計一個“好”的算法

9、應(yīng)考慮達到以下目標： 正確性：4個層次 可讀性：有助于對算法的理解(結(jié)構(gòu)化、模塊化、加解釋等) 健壯性：輸入數(shù)據(jù)非法，作出適 當反應(yīng)或進行處理 高效率與低存儲要求：效率是指算法執(zhí)行的時間 算法分析與設(shè)計 課件 算法分析算法分析( analysis): ):對算法所需要的 算法分析(algorithm analysis):對算法所需要的 兩種計算機資源 時間和空間進行估算 兩種計算機資源時間和空間進行估算 時間簡單性(time complexity) 時間簡單性( complexity) 空間簡單性( complexity) 空間簡單性(space complexity) 算法分析的目的： 算法

10、分析的目的： 設(shè)計算法 設(shè)計出簡單性盡可能低的算法 設(shè)計算法設(shè)計出簡單性盡可能低的算法 選擇算法 在多種算法中選擇其中簡單性最低者 選擇算法在多種算法中選擇其中簡單性最低者 算法分析與設(shè)計 課件 算法簡單性分析 算法簡單性 = 算法所需要的計算機資源 算法的時間簡單性t(n); 算法的空間簡單性s(n)。 是問題的規(guī)模(輸入大小)。 其中n是問題的規(guī)模(輸入大小)。 算法分析與設(shè)計 課件 算法的時間簡單性 (1)最壞狀況(worst case)下的時間簡單性 最壞狀況( 最壞狀況 tmax(n) = max t(i) | size(i)=n 最好狀況( (2)最好狀況(best case)下的

11、時間簡單性 最好狀況 tmin(n) = min t(i) | size(i)=n (3)平均狀況(average case)下的時間簡單性 平均狀況( 平均狀況 tavg(n) = size ( i ) =n p( i )t ( i ) 其中i是問題的規(guī)模(input size)為n的實例，p(i)是實 例i消失的概率。 算法分析與設(shè)計 課件 例：挨次搜尋算法 在具有n個元素的數(shù)組a1.n中找出值等于 的元素的位置。 中找出值等于k的元素的位置 在具有 個元素的數(shù)組 的數(shù)組 中找出值等于 的元素的位置。 templateclass type int seqsearch(type *a, in

12、t n, type k) for(int i=0;in;i+) if (ai=k) return i; return -1; 算法分析與設(shè)計 課件 (1)tmax(n) = max t(i) | size(i)=n =n (2)tmin(n) = min t(i) | size(i)=n =1 (3)在平均狀況下，假設(shè)： (a) 搜尋勝利的概率為p ( 0 p 1 ); (b) 在數(shù)組的每個位置i ( 0 i n )搜尋勝利的概率相同，均為 p/n。 tavg (n) = size ( i ) = n p( i )t ( i ) p p p p = 1 + 2 + 3 + l + n + n

13、(1 p ) n n n n p n (1 p ) = p(n + 1) + n(1 p) = i + n n i =1 2 算法分析與設(shè)計 課件 算法漸近簡單性設(shè)t(n)為算法a的時間簡單性函數(shù),則它是n的單增函數(shù),假如存在 為算法a的時間簡單性函數(shù), 的單增函數(shù), 一個函數(shù) (n) 使得當n ,有 t(n)- (n) / t(n)0 時的漸進性態(tài)或 漸進簡單性 。 稱 (n) 是t(n)當 n 時的 或 在數(shù)學(xué)上, 有相同的最高階項. 為略去t( 在數(shù)學(xué)上,t(n)與 (n)有相同的最高階項.可取 (n)為略去t(n)的 低階項后剩余的主項. 代替t( 低階項后剩余的主項.當n充分大時我們

14、用 (n)代替t(n)作為算法復(fù) 雜性的度量,從而簡化分析. 雜性的度量,從而簡化分析 . 例如 t(n)=3n2+4nlogn+7, 則 (n)可以是3n2. 3n 若進一步假定算法中全部不同元運算的單位執(zhí)行時間相同,則可不 若進一步假定算法中全部不同元運算的單位執(zhí)行時間相同, 考慮 (n)所包含的系數(shù)或常數(shù)因子。 ( 所包含的系數(shù)或常數(shù)因子。 漸進分析適用于n充分大的狀況,當問題的規(guī)模很小時, 漸進分析適用于n充分大的狀況,當問題的規(guī)模很小時,或比較的兩 算法同階時,則不能做這種簡化. 算法同階時,則不能做這種簡化. 算法分析與設(shè)計 課件 meaning: for all data set

15、s big 漸近簡單性分析的記號 enough (i.e., nn0), the algorithm always executes in less than c|g(n)| 在下面的爭論中，對全部n,f(n) 0,g(n) 0。 (1)漸近上界記號o(big-o) 漸近上界記號o 漸近上界記號 )若存在正常數(shù)c和自然數(shù) 若存在正常數(shù) 和自然數(shù)n0 使得當 和自然數(shù) n n 0 時 ， 有 0 f ( n ) cg ( n ) 充分大時有上 則稱函數(shù) f(n )在n充分大時有上 在 充分大時有 界, 且g(n)是它的一個上界, 記為 f(n) =o(g (n) ) , 也稱 f(n) 的 階

16、不 高 于 g ( n ) 的 階 。c g(n)running time f (n) n0 input size 算法運行時間的上限 算法運行時間的上限 上界的階越低，則評估就越精確，結(jié)果就越有價 上界的階越低，則評估就越精確， 上界的階越低 t(n)= 值。例：t(n) =3n2 ,t(n)=o(n2),而n2= 取前者。 o(n3), 取前者。 算法分析與設(shè)計 課件 舉例：例1 :f(n) = 2n + 3 = o(n) 當n3時，2n+33n,所以，可選 = 3,n0 = 3。對于 時 ，所以，可選c , 。對于nn0,f(n) , = 2n + 33n,所以，f(n) = o(n),即2n + 3o(n)。這意味著， ,所以， , 。這意味著， 的程序步不會超過3n, 當n3時，程序 的程序步不會超過 ，2n + 3 = o(n)。 時 程序2-1的程序步不會超過 。 例2: f(n) = 10n2 + 4n + 2 = o(n2) 對于n2時， 有10n2 + 4n + 210n2 + 5n,