算法設計第一章_第1頁
算法設計第一章_第2頁
算法設計第一章_第3頁
算法設計第一章_第4頁
算法設計第一章_第5頁
已閱讀5頁,還剩28頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

計算機算法設計與分析1algorithm@163.com123456網(wǎng)易網(wǎng)盤算法20132參考書目:王紅梅,算法設計與分析,清華大學出版社,2006。呂國英,算法設計與分析,清華大學出版社,2009。AlfredV.Aho等,(黃林鵬等譯)計算機算法的設計與分析,機械工業(yè)出版社,2007。R.C.T.Lee,(王衛(wèi)東譯)算法設計與分析導引,機械工業(yè)出版社,2007。3內容安排:一算法概述二遞歸與分治策略(I)三動態(tài)規(guī)劃(I,H)四貪心算法(I)五回溯法(H)六分支限界法(H)4第一章算法概述AlgorithmIntroduction5學習要求:理解算法的概念理解什么是程序,程序與算法的區(qū)別和內在聯(lián)系掌握算法計算復雜性的概念掌握算法漸進復雜性的數(shù)學表達掌握用C++語言描述算法的方法了解NP類問題的基本概念61.1算法與程序1、算法一系列將問題的輸入轉換為輸出的計算或操作步驟。72.算法的性質輸入:有外部提供的量作為算法的輸入。輸出:算法產(chǎn)生至少一個量作為輸出。確定性:組成算法的每條指令是清晰、無歧義的。有限性:算法中每條指令的執(zhí)行次數(shù)是有限的,執(zhí)行每條指令的時間也是有限的。83、程序與算法的區(qū)別與內在聯(lián)系程序是算法用某種程序設計語言的具體實現(xiàn)。程序可以不滿足算法的性質(4)。4、算法描述語言自然語言、流程圖、程序設計語言、偽代碼等。9理解問題算法分析設計程序5、問題求解(ProblemSolving)證明正確性數(shù)學模型設計算法101.2算法復雜性分析算法的復雜性(C):算法執(zhí)行所需的時間和空間的數(shù)量。1、復雜性的計量算法的復雜性(C)時間復雜性(T)空間復雜性(S)11問題的規(guī)模算法輸入1.2算法復雜性分析12時間復雜性:元運算時間元運算種類元運算次數(shù)?1.2算法復雜性分析13(P71-4)例題1-114最壞情況:最好情況:1.2算法復雜性分析15平均情況:輸入I的概率1.2算法復雜性分析16例題1-2nInt

Find(intA[],intn){i:=0;awhilei<nti:=i+1;(a+s)IfA[i]==ktBreakRetureia}分析:問題的規(guī)模為n,設元運算執(zhí)行時間為賦值:a,判斷:t,加法:s。172、復雜性的漸進性態(tài)1)漸進性態(tài)18*漸進分析適用于N充分大的情況,當問題的規(guī)模很小時,或比較的兩算法同階時,則不能做這種簡化.2、復雜性的漸進性態(tài)192)漸進性態(tài)的階(1)大O表示法(算法運行時間的上限)202)漸進性態(tài)的階212)漸進性態(tài)的階22??*上界的階越低,結果就越有價值。2)漸進性態(tài)的階232)漸進性態(tài)的階24(2)大表示法(算法運行時間的下限)2)漸進性態(tài)的階25(3)表示法2)漸進性態(tài)的階26指數(shù)級階乘級常數(shù)級對數(shù)級線性級多項式級2)漸進性態(tài)的階27a)對問題處理能力、運行時間有影響的因素有:硬件設備的性能系統(tǒng)軟件輸入數(shù)據(jù)b)起決定性作用的是算法漸近復雜度。c)在問題規(guī)模較小時,常數(shù)因子也不可忽視。d)實際工作中考慮的因素4算法復雜度的影響28練習:例1:解決某問題有三種算法,復雜性分別為1000N、10N2、2N,在一臺機器上可處理問題的規(guī)模分別為S1、S2、S3。若機器速度提高到原來的10倍,問在同樣時間內可處理問題的大小如何?解:復雜性原來處理問題規(guī)模速度提高以后

1000NS110S1S23.16S2S3S3+log10≈S3+3.3229例2:問題P的算法復雜度為T(n)=n3(毫秒),現(xiàn)改善為T(n)=n2(毫秒)。問原來運行一小時的問題實例,現(xiàn)在要運行多少時間?解:設實例大小為n,

則n3=3600*1000n=153.3∴現(xiàn)在需要時間t=153.32毫秒≈23.5秒練習:30指數(shù)級階乘級常數(shù)級對數(shù)級線性級多項式級1.3NP完全性理論易解問題311.3NP完全性理論P類問題NP類問題Nond

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論