算法設(shè)計(jì)第一章

計(jì)算機(jī)算法設(shè)計(jì)與分析1algorithm@163.com123456網(wǎng)易網(wǎng)盤(pán)算法20132參考書(shū)目：王紅梅，算法設(shè)計(jì)與分析，清華大學(xué)出版社，2006。呂國(guó)英，算法設(shè)計(jì)與分析，清華大學(xué)出版社，2009。AlfredV.Aho等，（黃林鵬等譯）計(jì)算機(jī)算法的設(shè)計(jì)與分析，機(jī)械工業(yè)出版社，2007。R.C.T.Lee，（王衛(wèi)東譯）算法設(shè)計(jì)與分析導(dǎo)引，機(jī)械工業(yè)出版社，2007。3內(nèi)容安排：一算法概述二遞歸與分治策略(I)三動(dòng)態(tài)規(guī)劃(I,H)四貪心算法(I)五回溯法(H)六分支限界法(H)4第一章算法概述AlgorithmIntroduction5學(xué)習(xí)要求：理解算法的概念理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系掌握算法計(jì)算復(fù)雜性的概念掌握算法漸進(jìn)復(fù)雜性的數(shù)學(xué)表達(dá)掌握用C++語(yǔ)言描述算法的方法了解NP類(lèi)問(wèn)題的基本概念61.1算法與程序1、算法一系列將問(wèn)題的輸入轉(zhuǎn)換為輸出的計(jì)算或操作步驟。72.算法的性質(zhì)輸入：有外部提供的量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令是清晰、無(wú)歧義的。有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。83、程序與算法的區(qū)別與內(nèi)在聯(lián)系程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿(mǎn)足算法的性質(zhì)(4)。4、算法描述語(yǔ)言自然語(yǔ)言、流程圖、程序設(shè)計(jì)語(yǔ)言、偽代碼等。9理解問(wèn)題算法分析設(shè)計(jì)程序5、問(wèn)題求解(ProblemSolving)證明正確性數(shù)學(xué)模型設(shè)計(jì)算法101.2算法復(fù)雜性分析算法的復(fù)雜性(C):算法執(zhí)行所需的時(shí)間和空間的數(shù)量。1、復(fù)雜性的計(jì)量算法的復(fù)雜性(C)時(shí)間復(fù)雜性(T)空間復(fù)雜性(S)11問(wèn)題的規(guī)模算法輸入1.2算法復(fù)雜性分析12時(shí)間復(fù)雜性：元運(yùn)算時(shí)間元運(yùn)算種類(lèi)元運(yùn)算次數(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}分析:問(wèn)題的規(guī)模為n,設(shè)元運(yùn)算執(zhí)行時(shí)間為賦值:a,判斷:t,加法:s。172、復(fù)雜性的漸進(jìn)性態(tài)1)漸進(jìn)性態(tài)18*漸進(jìn)分析適用于N充分大的情況,當(dāng)問(wèn)題的規(guī)模很小時(shí),或比較的兩算法同階時(shí),則不能做這種簡(jiǎn)化.2、復(fù)雜性的漸進(jìn)性態(tài)192）漸進(jìn)性態(tài)的階(1)大O表示法(算法運(yùn)行時(shí)間的上限)202）漸進(jìn)性態(tài)的階212）漸進(jìn)性態(tài)的階22??*上界的階越低，結(jié)果就越有價(jià)值。2）漸進(jìn)性態(tài)的階232）漸進(jìn)性態(tài)的階24(2)大表示法(算法運(yùn)行時(shí)間的下限）2）漸進(jìn)性態(tài)的階25(3)表示法2）漸進(jìn)性態(tài)的階26指數(shù)級(jí)階乘級(jí)常數(shù)級(jí)對(duì)數(shù)級(jí)線性級(jí)多項(xiàng)式級(jí)2）漸進(jìn)性態(tài)的階27a)對(duì)問(wèn)題處理能力、運(yùn)行時(shí)間有影響的因素有：硬件設(shè)備的性能系統(tǒng)軟件輸入數(shù)據(jù)b)起決定性作用的是算法漸近復(fù)雜度。c)在問(wèn)題規(guī)模較小時(shí)，常數(shù)因子也不可忽視。d)實(shí)際工作中考慮的因素4算法復(fù)雜度的影響28練習(xí)：例1：解決某問(wèn)題有三種算法，復(fù)雜性分別為1000N、10N2、2N，在一臺(tái)機(jī)器上可處理問(wèn)題的規(guī)模分別為S1、S2、S3。若機(jī)器速度提高到原來(lái)的10倍，問(wèn)在同樣時(shí)間內(nèi)可處理問(wèn)題的大小如何？解：復(fù)雜性原來(lái)處理問(wèn)題規(guī)模速度提高以后

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

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