第一章(算法和算法分析)

《第一章(算法和算法分析)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、什么是算法？&第一章緒論?算法是對解決問題的方法的一種精確描述。1.1引言1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念；?并非所有問題都有算法，有些問題經(jīng)研究可行，則可能有相應(yīng)算法；而有1.3算法及算法分析（算法評(píng)價(jià)）些問題經(jīng)研究不可行，則沒有相應(yīng)算法。?因此，算法研究在某種意義上就是可12行性研究。算法的性質(zhì)算法的性質(zhì)?算法可以理解為動(dòng)作序列的有限集合算法是為了解決某類問題而規(guī)定的一?僅有一個(gè)初始動(dòng)作個(gè)有限長的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：?每個(gè)動(dòng)作的后繼動(dòng)作是確定的1．有窮性2．確定性3．可行性?算法的終止表示問題得到解答或問題4．有輸入5．有輸出沒有

2、解答341．有窮性對于任意一組合法輸入值，3．可行性算法中的所有操作都必須足在執(zhí)行有窮步驟之后一定能結(jié)束，即：夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。運(yùn)算有限次實(shí)現(xiàn)之。2．確定性對于每種情況下所應(yīng)執(zhí)行的4．有輸入作為算法加工對象的量值，操作，在算法中都有確切的規(guī)定，使算法通常體現(xiàn)為算法中的一組變量。有些輸入的執(zhí)行者或閱讀者都能明確其含義及如何量需要在算法執(zhí)行過程中輸入，而有的算執(zhí)行。并且在任何條件下，算法都只有一法表面上可以沒有輸入，實(shí)際上已被嵌入條執(zhí)行路徑。算法之中。561算法設(shè)計(jì)的原則5．有輸出它是一組與“輸入”有確

3、設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：定關(guān)系的量值，是算法進(jìn)行信息加1．正確性工后得到的結(jié)果，這種確定關(guān)系即2.可讀性為算法的功能。3．健壯性4．高效率與低存儲(chǔ)量需求781．正確性c．程序?qū)τ诰倪x擇的、典型、苛刻且首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足說明”方式給出的需求。要求的結(jié)果；其次，對算法是否“正確”的理解可以d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得有以下四個(gè)層次：出滿足要求的結(jié)果；a．程序中不含語法錯(cuò)誤；通常以第c層意義的正確性作為衡b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；量一個(gè)算法是否合格的標(biāo)準(zhǔn)。9103．健

4、壯性2.可讀性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)算法主要是為了人的閱讀與交流，地作出反映或進(jìn)行相應(yīng)處理，而不是產(chǎn)其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易生莫名奇妙的輸出結(jié)果。并且，處理出于人的理解；另一方面，晦澀難讀的程序錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)易于隱藏較多錯(cuò)誤而難以調(diào)試。是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。111224．高效率與低存儲(chǔ)量需求&第一章緒論通常，效率指的是算法執(zhí)行時(shí)間；1.1引言存儲(chǔ)量指的是算法執(zhí)行過程中所需的1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念；1.3算法及算法分析（算法評(píng)價(jià)）最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)

5、。1314算法分析與算法復(fù)雜度算法的效率?算法分析的任務(wù)是對設(shè)計(jì)出的每一個(gè)具體的算法，利用數(shù)學(xué)工具，討論其對于一個(gè)問題通常有多種解法（算法），復(fù)雜度，探討具體算法對問題的適應(yīng)應(yīng)該選擇哪一種呢？性計(jì)算機(jī)程序設(shè)計(jì)的核心有兩個(gè)目標(biāo)（有時(shí)它們互相沖突）?算法的復(fù)雜度分時(shí)間復(fù)雜度和空間復(fù)1.設(shè)計(jì)一種容易理解、編碼和調(diào)試的算法雜度。2.設(shè)計(jì)一種能有效利用計(jì)算機(jī)資源的算法?計(jì)算機(jī)理論科學(xué)中，按照計(jì)算復(fù)雜性研究問題求解的難易性，可把問題分為P類、NP類和NP-完全類。1516如何度量效率?算法的效率(cont)1.實(shí)驗(yàn)比較（運(yùn)行程序）目標(biāo)1涉及到軟件工程原理2.漸近算法

6、分析AsymptoticAlgorithmAnalysis目標(biāo)2涉及到數(shù)據(jù)結(jié)構(gòu)與算法分析關(guān)鍵資源:本課程主要講的是與目標(biāo)2有關(guān)的問題影響運(yùn)行時(shí)間的因素:怎樣度量算法的代價(jià)、效率呢？對很多算法而言，運(yùn)行時(shí)間依賴與輸入的規(guī)模執(zhí)行算法所需要的時(shí)間T寫成輸入規(guī)模n的函數(shù)，記為T(n)17183怎樣比較兩種算法解決問題的效“規(guī)?！迸c“基本操作”率呢？?實(shí)驗(yàn)比較–用源程序分別實(shí)現(xiàn)這兩種算法，然后輸入適?判斷算法性能的一個(gè)基本考慮是處理一當(dāng)?shù)臄?shù)據(jù)運(yùn)行，測算兩個(gè)程序各自的開銷定“規(guī)?！?size)的輸入時(shí)該算法所需執(zhí)–這是一種事后統(tǒng)計(jì)的方法行的“基本操作”(basico

7、peration)數(shù)?漸近算法分析(asymptoticalgorithmanalysis)，簡稱算法分析(algorithm?“規(guī)?！币话闶侵篙斎肓康臄?shù)目analysis)–比如，在排序問題中，問題的規(guī)?？梢杂帽花C可以估算出當(dāng)問題規(guī)模變大時(shí)，一種算法及排序元素的個(gè)數(shù)來衡量實(shí)現(xiàn)它的程序的效率和開銷–這是一種事前分析估算的方法1920“規(guī)?！迸c“基本操作”（續(xù)）運(yùn)行時(shí)間和增長率?一個(gè)“基本操作”必須具有這樣的性質(zhì)：完?由于影響運(yùn)行時(shí)間的最主要因素一成該操作所需時(shí)間與操作數(shù)的具體取值般是輸入的規(guī)模，所以經(jīng)常把執(zhí)行無關(guān)算法所需要的時(shí)間T寫成輸入規(guī)模n–在大多數(shù)

8、高級(jí)語言中，下列操作是基本操作：的函數(shù)，記為T(n)?賦值運(yùn)算–我們總是假設(shè)T(