資源描述:
《《算法與算法分析》PPT課件》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第一章緒論1.1引言1.2算法及算法分析(算法評價(jià))1什么是算法?算法是對解決問題的方法的一種精確描述。并非所有問題都有算法,有些問題經(jīng)研究可行,則可能有相應(yīng)算法;而有些問題經(jīng)研究不可行,則沒有相應(yīng)算法。因此,算法研究在某種意義上就是可行性研究。2算法的性質(zhì)算法可以理解為動(dòng)作序列的有限集合僅有一個(gè)初始動(dòng)作每個(gè)動(dòng)作的后繼動(dòng)作是確定的算法的終止表示問題得到解答或問題沒有解答3算法是為了解決某類問題而規(guī)定的一個(gè)有限長的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性:1.有窮性2.確定性3.可行性4.有輸入5.有輸出算法的性質(zhì)41.有窮性對于任意一組合法輸入值,在執(zhí)行有窮步驟之后一定能結(jié)束,即:算法中的每
2、個(gè)步驟都能在有限時(shí)間內(nèi)完成。2.確定性對于每種情況下所應(yīng)執(zhí)行的操作,在算法中都有確切的規(guī)定,使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下,算法都只有一條執(zhí)行路徑。53.可行性算法中的所有操作都必須足夠基本,都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4.有輸入作為算法加工對象的量值,通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入,而有的算法表面上可以沒有輸入,實(shí)際上已被嵌入算法之中。65.有輸出它是一組與“輸入”有確定關(guān)系的量值,是算法進(jìn)行信息加工后得到的結(jié)果,這種確定關(guān)系即為算法的功能。7算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí),通常應(yīng)考慮達(dá)到以下目標(biāo):1.正確性2.可
3、讀性3.健壯性4.高效率與低存儲(chǔ)量需求81.正確性首先,算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。其次,對算法是否“正確”的理解可以有以下四個(gè)層次:a.程序中不含語法錯(cuò)誤;b.程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果;9c.程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果;通常以第c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。d.程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果;102.可讀性算法主要是為了人的閱讀與交流,其次才是為計(jì)算機(jī)執(zhí)行,因此算法應(yīng)該易于人的理解;另一方面,晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。113.健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí),
4、算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理,而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且,處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行,而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值,以便在更高的抽象層次上進(jìn)行處理。124.高效率與低存儲(chǔ)量需求通常,效率指的是算法執(zhí)行時(shí)間;存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間,兩者都與問題的規(guī)模有關(guān)。13第一章緒論1.1引言1.2算法及算法分析(算法評價(jià))14算法分析與算法復(fù)雜度算法分析的任務(wù)是對設(shè)計(jì)出的每一個(gè)具體的算法,利用數(shù)學(xué)工具,討論其復(fù)雜度,探討具體算法對問題的適應(yīng)性算法的復(fù)雜度分時(shí)間復(fù)雜度和空間復(fù)雜度。計(jì)算機(jī)理論科學(xué)中,按照計(jì)算復(fù)雜性研究問題求解的難易性,可把問題分為P類、NP
5、類和NP-完全類。15算法的效率對于一個(gè)問題通常有多種解法(算法),應(yīng)該選擇哪一種呢?計(jì)算機(jī)程序設(shè)計(jì)的核心有兩個(gè)目標(biāo)(有時(shí)它們互相沖突)設(shè)計(jì)一種容易理解、編碼和調(diào)試的算法設(shè)計(jì)一種能有效利用計(jì)算機(jī)資源的算法16算法的效率(cont)目標(biāo)1涉及到軟件工程原理目標(biāo)2涉及到數(shù)據(jù)結(jié)構(gòu)與算法分析本課程主要講的是與目標(biāo)2有關(guān)的問題怎樣度量算法的代價(jià)、效率呢?17如何度量效率?實(shí)驗(yàn)比較(運(yùn)行程序)漸近算法分析AsymptoticAlgorithmAnalysis關(guān)鍵資源:影響運(yùn)行時(shí)間的因素:對很多算法而言,運(yùn)行時(shí)間依賴與輸入的規(guī)模執(zhí)行算法所需要的時(shí)間T寫成輸入規(guī)模n的函數(shù),記為T(n)18怎樣比較兩種算法解決
6、問題的效率呢?實(shí)驗(yàn)比較用源程序分別實(shí)現(xiàn)這兩種算法,然后輸入適當(dāng)?shù)臄?shù)據(jù)運(yùn)行,測算兩個(gè)程序各自的開銷這是一種事后統(tǒng)計(jì)的方法漸近算法分析(asymptoticalgorithmanalysis),簡稱算法分析(algorithmanalysis)可以估算出當(dāng)問題規(guī)模變大時(shí),一種算法及實(shí)現(xiàn)它的程序的效率和開銷這是一種事前分析估算的方法19“規(guī)模”與“基本操作”判斷算法性能的一個(gè)基本考慮是處理一定“規(guī)?!?size)的輸入時(shí)該算法所需執(zhí)行的“基本操作”(basicoperation)數(shù)“規(guī)?!币话闶侵篙斎肓康臄?shù)目比如,在排序問題中,問題的規(guī)??梢杂帽慌判蛟氐膫€(gè)數(shù)來衡量20“規(guī)模”與“基本操作”(續(xù))一
7、個(gè)“基本操作”必須具有這樣的性質(zhì):完成該操作所需時(shí)間與操作數(shù)的具體取值無關(guān)在大多數(shù)高級語言中,下列操作是基本操作:賦值運(yùn)算簡單算術(shù)運(yùn)算簡單布爾運(yùn)算簡單I/O操作函數(shù)返回n個(gè)整數(shù)累加不是基本操作因?yàn)槠浯鷥r(jià)依賴于n的值(即大小)21運(yùn)行時(shí)間和增長率由于影響運(yùn)行時(shí)間的最主要因素一般是輸入的規(guī)模,所以經(jīng)常把執(zhí)行算法所需要的時(shí)間T寫成輸入規(guī)模n的函數(shù),記為T(n)我們總是假設(shè)T(n)為非負(fù)值算法的增長率(g