離散數(shù)學(xué)算法基礎(chǔ).ppt

《離散數(shù)學(xué)算法基礎(chǔ).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第1章算法基礎(chǔ)11.1算法簡(jiǎn)介一、算法的概念算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。也可以說，在有限的時(shí)間內(nèi)，解決某一問題的一系列邏輯步驟就是算法。2二、算法的特征所有的算法都必須滿足下列幾個(gè)條件：1.有限性：必須保證執(zhí)行有限步之后結(jié)束；也叫可終止性。2.確切性：算法的每一步驟必須有確切的含義，并且在任何情況下，對(duì)于相同的輸入只能得出相同的輸出。3.輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定義了初始條件。4.輸出：至少產(chǎn)生一個(gè)結(jié)果，此結(jié)果與輸入的數(shù)據(jù)構(gòu)成某種

2、特定的關(guān)系。5.可行性：對(duì)于指令的執(zhí)行，可用筆和紙來模擬。31.2算法表示一、自然語言【例】寫出“A、B為整數(shù)，求A除以B的余數(shù)”的算法。A/B算法：1）獲得A和B的值；2）判斷B是否為零；3）如果B為零，則輸出“除數(shù)為零”出錯(cuò)信息；4）如果B不為零，則通過除式計(jì)算求得余數(shù)，最后，輸出余數(shù)。4二、流程圖【例】“A、B為整數(shù)，求A除以B的余數(shù)”的流程圖算法。5三、偽代碼偽代碼（Pseudocode，擬代碼，偽語言）是一種使用程序語言的基本結(jié)構(gòu)來說明程序的運(yùn)行過程的算法描述語言----程序語言的簡(jiǎn)化。使用偽代碼的目的是為了使被描述的算法可以容易地以編程語言（Pascal，C，J

3、ava，etc）實(shí)現(xiàn)。偽代碼的種類很多，原則上要結(jié)構(gòu)化，盡量接近高級(jí)語言。本書以類C語言為算法描述語言。6【例】：偽代碼示例if九點(diǎn)以前thendo私人事務(wù)；elseif9點(diǎn)到18點(diǎn)then工作；else下班;優(yōu)點(diǎn)：結(jié)構(gòu)清晰----體現(xiàn)了編程語言的結(jié)構(gòu)表達(dá)精煉----忽略了編程語言繁瑣的語法規(guī)則思路突出----容易把握解決方法的關(guān)鍵7類C語言的整體規(guī)格：1）算法名稱（含參數(shù)）2）注釋3）指令步驟類C語言的指令基本沿用C語言的指令集，在不產(chǎn)生歧義的情況下可適當(dāng)簡(jiǎn)化。8【例1.2.1】算法:在整數(shù)iData1,iData2,iData3中尋找最大數(shù)。解：算法1//在整數(shù)iDat

4、a1,iData2,iData3中尋找最大數(shù)FindMaxData(intiData1,iData2,iData3){X=iData1;ifiData2>XX=iData2;ifiData3>XX=iData3；returnX；}9解：算法2//在整數(shù)iData1,iData2,iData3中尋找最大數(shù)FindMaxData(intiData1,iData2,iData3){if(iData1>iData2)and(iData1>iData3)returniData1;if(iData2>iData1)and(iData2>iData3)returniData2;if(iD

5、ata3>iData2)and(iData3>iData1)returniData3;}101.3算法分析完成一個(gè)任務(wù)，可以有多個(gè)算法。算法分析----對(duì)按照該算法編制的程序在計(jì)算機(jī)上的執(zhí)行效率進(jìn)行估算，目的在于評(píng)價(jià)算法的優(yōu)劣。怎樣評(píng)價(jià)算法的優(yōu)劣時(shí)間效率：時(shí)間復(fù)雜度空間效率：空間復(fù)雜度（一般考慮多些）11一、時(shí)間復(fù)雜度（Timecomplexity）算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。可以理解為程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。兩種方法：事后統(tǒng)計(jì)方法事前分析方法12二、空間復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的空間資源（內(nèi)存大?。?zhí)行程序需要使用的空間是下列組成

6、的總和：1）固定部分：指令空間、固定大小的變量及常數(shù)所用的空間等。2）可變部分：動(dòng)態(tài)變量和遞歸?？臻g等。在一般的算法分析中，多以時(shí)間復(fù)雜度為主。13影響運(yùn)行時(shí)間的因素：書寫算法的程序設(shè)計(jì)語言編譯產(chǎn)生的機(jī)器語言代碼質(zhì)量機(jī)器執(zhí)行指令的速度問題的規(guī)模（數(shù)據(jù)個(gè)數(shù)）*原始數(shù)據(jù)的值（最好、平均、最壞）14找出問題的規(guī)模與時(shí)間之間的關(guān)系函數(shù)：從算法中選取一種對(duì)于所研究的問題來說是基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)（稱為語句頻度或時(shí)間頻度）作為算法的時(shí)間度量。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模（Problem’sSize）n（元素個(gè)數(shù)）的某個(gè)函數(shù)T(n)－－作為算法的

7、時(shí)間復(fù)雜度的估算。15【例】語句頻度的計(jì)算：下面的三個(gè)程序段..for(i=0;i