計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)_第1頁(yè)
計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)_第2頁(yè)
計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)_第3頁(yè)
計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)_第4頁(yè)
計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)_第5頁(yè)
已閱讀5頁(yè),還剩28頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

計(jì)算機(jī)算法分析與設(shè)計(jì)計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第1頁(yè)。學(xué)習(xí)目標(biāo)掌握算法分析與設(shè)計(jì)的基本理論掌握進(jìn)行算法分析與設(shè)計(jì)的基本方法(時(shí)間、空間復(fù)雜度分析,算法正確性的證明)掌握計(jì)算機(jī)領(lǐng)域中常用的非數(shù)值計(jì)算方法,并學(xué)會(huì)用這些算法解決實(shí)際問(wèn)題計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第2頁(yè)。課程要求教學(xué)方式:理論(32學(xué)時(shí)),實(shí)踐(16學(xué)時(shí))考核方式:考試(80%)+實(shí)驗(yàn)作業(yè)(20%)課程學(xué)分:3先修課程:《離散數(shù)學(xué)》《數(shù)據(jù)結(jié)構(gòu)》《數(shù)值分析》《C語(yǔ)言程序設(shè)計(jì)》計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第3頁(yè)。授課教材選用教材:《計(jì)算機(jī)算法基礎(chǔ)》(第二版)余祥宣,崔國(guó)華,鄒海明華中科技大學(xué)出版社參考書目:《算法引論》張益新,沈雁國(guó)防科技大學(xué)出版社《算法設(shè)計(jì)與分析》周培德機(jī)械工業(yè)出版社計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第4頁(yè)。第一章導(dǎo)引

---計(jì)算機(jī)算法分析與設(shè)計(jì)是面向設(shè)計(jì)的、處于核心地位的教育課程

---計(jì)算機(jī)算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心。1.什么是算法?2.如何分析算法?3.如何表示算法?4.基本數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第5頁(yè)。1.什么是算法算法數(shù)值計(jì)算方法(求解數(shù)值問(wèn)題,插值計(jì)算、數(shù)值積分等)非數(shù)值計(jì)算方法(求解非數(shù)值問(wèn)題,主要進(jìn)行判斷比較)算法籠統(tǒng)的定義:求解一確定類問(wèn)題的任意一種特殊方法。非形式描述:算法就是一組有窮的規(guī)則,它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第6頁(yè)。例1求兩個(gè)正整數(shù)m,n的最大公因子算法1-1歐幾里得算法輸入:正整數(shù)m和n輸出:m和n的最大公因子第一步:求余數(shù)。rm%n第二步:判斷r=0?,若是,終止(n為答案),否則,轉(zhuǎn)第三步。第三步:互換,mn,nr,返回第一步。BeginRm%nr=0?Swap(m.n)EndNY計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第7頁(yè)。例1求兩個(gè)正整數(shù)最大公因子的一個(gè)實(shí)例假設(shè)m=21和n=45,求21和45的最大公因子第一步:r=m%n=21%45=21;第二步:r不等于0,轉(zhuǎn)入第三步;第三步:互換,m=n=45,n=r=21,返回第一步。第一步:r=m%n=45%21=3;第二步:r不等于0,轉(zhuǎn)入第三步;第三步:互換,m=n=21,n=r=3,返回第一步。第一步:r=m%n=21%3=0;第二步:r等于0,算法結(jié)束,3即為21和45的最大公因子。計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第8頁(yè)。算法的五個(gè)重要特性確定性每一種運(yùn)算必須要有確切的定義,無(wú)二義性可行性運(yùn)算都是基本運(yùn)算,原理上能在有限時(shí)間內(nèi)完成輸入有 1個(gè)或多個(gè)輸入輸出一個(gè)或多個(gè)輸出有窮性在執(zhí)行了有窮步運(yùn)算后終止計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第9頁(yè)。算法的特性凡是算法,都必須滿足以上五條特性。只滿足前四條特性的一組規(guī)則不能稱之為算法,只能叫做計(jì)算過(guò)程。操作系統(tǒng)就是計(jì)算過(guò)程的一個(gè)典型例子。設(shè)計(jì)操作系統(tǒng)的目的是為了控制作業(yè)的運(yùn)行,當(dāng)沒(méi)有作業(yè)時(shí),這一計(jì)算過(guò)程并不終止,而是處于等待狀態(tài),一直等到一個(gè)新的作業(yè)的進(jìn)入。計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第10頁(yè)。算法學(xué)習(xí)的五個(gè)內(nèi)容如何設(shè)計(jì)算法運(yùn)用一些基本設(shè)計(jì)策略規(guī)劃算法如何表示算法用恰當(dāng)?shù)姆绞奖硎舅惴ㄈ绾未_認(rèn)算法算法正確性的證明(算法確認(rèn)algorithmvalidation)如何分析算法通過(guò)時(shí)間和空間復(fù)雜度的分析,確定算法的優(yōu)劣如何測(cè)試程序測(cè)試程序是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第11頁(yè)。2.如何分析算法算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。算法分析步驟:首先確定使用那些運(yùn)算以及執(zhí)行這些運(yùn)算所用的時(shí)間。(運(yùn)算包括基本數(shù)值運(yùn)算和一些更基本的任意長(zhǎng)序列的運(yùn)算)其次是要確定出能反映算法在各種情況下工作的數(shù)據(jù)集。(即要求我們編造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置,通過(guò)使用這些數(shù)據(jù)來(lái)運(yùn)行算法,以更了解算法的性能)計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第12頁(yè)。全面分析一個(gè)算法的兩個(gè)階段事前分析(apriorianalysis)求出該算法的一個(gè)時(shí)間限界函數(shù)(一些關(guān)于參數(shù)的函數(shù))事前分析只限于每條語(yǔ)句的頻率計(jì)數(shù)(frequencycount,該語(yǔ)句的執(zhí)行次數(shù),與所用的機(jī)器無(wú)關(guān),且獨(dú)立于程序設(shè)計(jì)語(yǔ)言,可由算法直接確定)事后測(cè)試(aposterioritesting)收集此算法的實(shí)際執(zhí)行時(shí)間和占用空間的統(tǒng)計(jì)資料計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第13頁(yè)。例3:頻率計(jì)數(shù)例子考慮語(yǔ)句xx+y在下面三個(gè)程序段中的頻率計(jì)數(shù)beginxx+yendFC:1beginfori1tondo

xx+yrepeatEndFC:nbeginfori1tondoforj1tondo

xx+y

repeatRepeatEndFC:n2計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第14頁(yè)。算法分析是對(duì)一個(gè)算法需要多少時(shí)間很存儲(chǔ)空間作定量分析。布爾值:True False第一步:r=m%n=21%45=21;解決方法:先使用遞歸,然后證明所設(shè)計(jì)的遞歸算法正確并且確信是一個(gè)好算法,再把遞歸消去,翻譯成與之等價(jià)的只使用迭代的算法。例1求兩個(gè)正整數(shù)m,n的最大公因子則記作:f(n)=O(g(n))ProcedureName(<參數(shù)列表>)(即要求我們編造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置,通過(guò)使用這些數(shù)據(jù)來(lái)運(yùn)行算法,以更了解算法的性能)運(yùn)算都是基本運(yùn)算,原理上能在有限時(shí)間內(nèi)完成邏輯運(yùn)算符:and,or,not解決方法:先使用遞歸,然后證明所設(shè)計(jì)的遞歸算法正確并且確信是一個(gè)好算法,再把遞歸消去,翻譯成與之等價(jià)的只使用迭代的算法。關(guān)系運(yùn)算符:<,≤,=,≠,>,≥elsereturn(GCD(b,amodb))先修課程:《離散數(shù)學(xué)》《數(shù)據(jù)結(jié)構(gòu)》《數(shù)值分析》《C語(yǔ)言程序設(shè)計(jì)》余祥宣,崔國(guó)華,鄒海明華中科技大學(xué)出版社余祥宣,崔國(guó)華,鄒海明華中科技大學(xué)出版社計(jì)算時(shí)間的漸進(jìn)估計(jì)表示定義1.1如果存在兩個(gè)正常數(shù)c和n0,對(duì)于所有的n≥n0,有

|f(n)|≤c|g(n)|則記作:f(n)=O(g(n))因此,當(dāng)說(shuō)一個(gè)算法具有O(g(n))的計(jì)算時(shí)間時(shí),指的就是如果此算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí),所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù),f(n)的數(shù)量級(jí)就是g(n)計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第15頁(yè)。時(shí)間的漸進(jìn)估計(jì)表示定理

若A(n)=amnm+…+a1n+a0是一個(gè)m次多項(xiàng)式,則A(n)=O(nm)。證明:取n0=1,當(dāng)n≥n0時(shí)利用A(n)的定義和一個(gè)簡(jiǎn)單的不等式,有

|A(n)|≤|am|nm+…+|a1|

n+|a0| ≤(|am|+|am-1|/n…+|a0|/nm)

nm

≤(|am|+|am-1|…+|a0|)

nm取c=|am|+|am-1|…+|a0|,定理得證。計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第16頁(yè)。求出該算法的一個(gè)時(shí)間限界函數(shù)(一些關(guān)于參數(shù)的函數(shù))ProcedureName(<參數(shù)列表>)非形式描述:算法就是一組有窮的規(guī)則,它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。則記作:f(n)=Ω(g(n))例如,一個(gè)算法的數(shù)量級(jí)為c1nm1,c2nm2,…cknmk的k個(gè)語(yǔ)句,則算法的數(shù)量級(jí)及計(jì)算時(shí)間就是c1nm1+c2nm2+…+cknmk=O(nm)SPARKS語(yǔ)言的組成(3)解決方法:先使用遞歸,然后證明所設(shè)計(jì)的遞歸算法正確并且確信是一個(gè)好算法,再把遞歸消去,翻譯成與之等價(jià)的只使用迭代的算法。在當(dāng)前的過(guò)程中說(shuō)明的變量其中m=max{mi|1≤i≤k}結(jié)果為GCD(22,8)=2因此,一個(gè)計(jì)算時(shí)間為m階多項(xiàng)式的算法,其時(shí)間都可以用O(nm)來(lái)表示。例如:a=22,b=8求GCD(22,8)=?while條件do loop例1求兩個(gè)正整數(shù)m,n的最大公因子在已包含當(dāng)前過(guò)程的過(guò)程中說(shuō)明為局部變量的變量(即要求我們編造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置,通過(guò)使用這些數(shù)據(jù)來(lái)運(yùn)行算法,以更了解算法的性能)時(shí)間的漸進(jìn)估計(jì)表示定理表明,變量n的固定階數(shù)為m的任一多項(xiàng)式,與此多項(xiàng)式的最高階nm同階。因此,一個(gè)計(jì)算時(shí)間為m階多項(xiàng)式的算法,其時(shí)間都可以用O(nm)來(lái)表示。例如,一個(gè)算法的數(shù)量級(jí)為c1nm1,c2nm2,…cknmk的k個(gè)語(yǔ)句,則算法的數(shù)量級(jí)及計(jì)算時(shí)間就是c1nm1+c2nm2+…+cknmk=O(nm)其中m=max{mi|1≤i≤k}計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第17頁(yè)。算法的分類從計(jì)算時(shí)間上可把算法分為兩類多項(xiàng)式時(shí)間算法(polynomialtimealgorithm):可用多項(xiàng)式來(lái)對(duì)其計(jì)算時(shí)間限界的算法。以下六種計(jì)算時(shí)間的多項(xiàng)式時(shí)間算法是最為常見(jiàn)的O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時(shí)間算法(exponentialtimealgorithm):計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法O(2n)<O(n!)<O(nn)計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第18頁(yè)。nlognnlognn2n32n100112212484428166416832464512256164642564096655363251601024327684294967296對(duì)于問(wèn)題輸入長(zhǎng)度n取不同值,各種不同的時(shí)間復(fù)雜性函數(shù)的算法,在機(jī)器上的運(yùn)行所需時(shí)間如下所示:計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第19頁(yè)。時(shí)間的漸進(jìn)估計(jì)表示定義

如果存在兩個(gè)正常數(shù)c和n0,對(duì)于所有的n≥n0,有

|f(n)|≥c|g(n)|

則記作:f(n)=Ω(g(n))定義

如果存在兩個(gè)正常數(shù)c1,c2和n0,對(duì)于所有的n≥n0,有

c1|g(n)|≤|f(n)|≤c2|g(n)|

則記作:f(n)=Θ(g(n))計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第20頁(yè)。常用的整數(shù)求和公式計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第21頁(yè)。3.如何表示算法將算法的基本思想和基本步驟用語(yǔ)言表示出來(lái),便于閱讀并能很容易地用人工或機(jī)器翻譯成其他實(shí)際使用的程序設(shè)計(jì)語(yǔ)言。用SPARKS語(yǔ)言寫算法SPARKS語(yǔ)言的組成基本數(shù)據(jù)類型整型(integer),實(shí)型(float),布爾型(boolean),字符型(char)保留字具有特殊含義的標(biāo)識(shí)符,用黑體字表示計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第22頁(yè)。SPARKS語(yǔ)言的組成(1)變量命名規(guī)則以字母開頭,不允許使用特殊字符,不要太長(zhǎng),不允許與任何保留字重復(fù)。語(yǔ)句:以分號(hào)作為語(yǔ)句結(jié)束的標(biāo)志賦值語(yǔ)句:<變量><表達(dá)式>布爾值:True False邏輯運(yùn)算符:and,or,not關(guān)系運(yùn)算符:<,≤,=,≠,>,≥數(shù)組:任意整數(shù)下界和上界的多維數(shù)組計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第23頁(yè)。SPARKS語(yǔ)言的組成(2)條件語(yǔ)句

if條件thens1

或if條件then

elses2 s1

endif endifCase語(yǔ)句

case :

條件1:s1

… :

條件n:sn :else :sn+1 endcase計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第24頁(yè)。SPARKS語(yǔ)言的組成(3)循環(huán)語(yǔ)句while

條件

do loop

S S Repeat until

條件repeatFor

vblestart

tofinish

by

increment

do SRepeat

計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第25頁(yè)。SPARKS語(yǔ)言的組成(4)過(guò)程(函數(shù))ProcedureName(<參數(shù)列表>) <說(shuō)明部分> SReturn(<表達(dá)式>)EndName局部變量(localvariabl)在當(dāng)前的過(guò)程中說(shuō)明的變量全局變量(globalvariabl)在已包含當(dāng)前過(guò)程的過(guò)程中說(shuō)明為局部變量的變量形式參數(shù)(formalparameter)參數(shù)表中的一個(gè)標(biāo)識(shí)符計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第26頁(yè)。1.4基本數(shù)據(jù)結(jié)構(gòu)(略)棧和隊(duì)列棧的運(yùn)算隊(duì)列的運(yùn)算樹二元樹堆二分檢索樹圖計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第27頁(yè)。1.5遞歸和消去遞歸遞歸直接調(diào)用自己或間接通過(guò)一些語(yǔ)句調(diào)用自己優(yōu)點(diǎn):描述某些數(shù)學(xué)問(wèn)題非常自然,證明算法很容易。缺點(diǎn):執(zhí)行時(shí)間、空間消耗多一個(gè)遞歸問(wèn)題可分為“回推”和“遞推”兩個(gè)階段未知已知遞推回推計(jì)算機(jī)算法分析與設(shè)計(jì)(共33張PPT)全文共33頁(yè),當(dāng)前為第28頁(yè)。遞歸例子:Fibonacci數(shù)列定義F(n)=1, n=01, n=1F(n-1)+F(n-2), n>1非遞歸部分,終止條件遞歸部分,起始條件求Fibonacci數(shù)列算法ProcedureF(n) integern ifn≤1thenreturn(1) elsereturn(F(n-1)

溫馨提示

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

評(píng)論

0/150

提交評(píng)論