算法設(shè)計第一章

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

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

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

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