




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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í)間增
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 戒毒人員輔助管理辦法
- 唐山強(qiáng)化風(fēng)控管理辦法
- 瓦斯隧道施工培訓(xùn)課件
- 肥胖課件介紹
- 肢體殘疾人職業(yè)培訓(xùn)課件
- 腸癌手術(shù)護(hù)理課件
- 福建龍巖中考數(shù)學(xué)試卷
- 肝病心理護(hù)理課件
- 監(jiān)理鐵路隧道培訓(xùn)課件
- 肌肉能量技術(shù)課件原理
- 2024年江蘇省徐州市保安員證考試題庫及答案()
- 2025年江西省中考數(shù)學(xué)試卷真題(含標(biāo)準(zhǔn)答案)
- 2025年物聯(lián)網(wǎng)技術(shù)在智能養(yǎng)老中的老人健康監(jiān)測與生活服務(wù)保障報(bào)告
- 天臺保安考試題及答案
- 2025年高考全國二卷英語高考真題含解析
- 2024年民族出版社招聘事業(yè)編制專業(yè)技術(shù)人員真題
- 2025年食品安全管理員考試試題及答案
- 2025-2030骨科植入器材產(chǎn)業(yè)市場深度分析及發(fā)展趨勢與投資戰(zhàn)略研究報(bào)告
- 陜西省西工大附中第二次2025屆數(shù)學(xué)八下期末考試試題含解析
- 2025年中央八項(xiàng)規(guī)定精神學(xué)習(xí)教育應(yīng)知應(yīng)會考試題庫(含答案)
- 建立有效的風(fēng)險(xiǎn)管理體系試題及答案
評論
0/150
提交評論