計(jì)算機(jī)算法設(shè)計(jì)與分析課件：第一章 概論與相關(guān)知識(shí)回顧

1、The design and analysis of computer algorithms計(jì)算機(jī)算法設(shè)計(jì)與分析 教學(xué)目的通過(guò)對(duì)計(jì)算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，掌握算法設(shè)計(jì)的主要策略和方法，培養(yǎng)學(xué)生對(duì)算法的正確性證明以及計(jì)算復(fù)雜性正確分析的能力，為獨(dú)立設(shè)計(jì)算法和對(duì)算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)。 主要教學(xué)參考書余祥宣，崔國(guó)華，鄒海明，計(jì)算機(jī)算法基礎(chǔ) （第三版），2006 ，華中科技大學(xué)出版社E.Horowitz and S. Sahni: Fundamentals of Computer Algorithms, Computer Science Press, Pitman, Inc. Cli

2、fford A. Shaffer, A Practical Introduction to Data Structures and Algorithm Analysis（Second Edition）, Prentice Hall,. 數(shù)據(jù)結(jié)構(gòu)與算法分析(C+版) (第二版 英文原版)，電子工業(yè)出版社，2002。Sara Baase，Allen Van Gelder，Computer AlgorithmsIntroduction to Design and Analysis （Third Edition）, Addison Wesley Longman，2000，高等教育出版社（影印版），20

3、01年Donald E. Knuth，The Art of Computer Programming（Vol. 1 Fundamental Algorithms， Third Edition），Addison-Wesley，1998，清華大學(xué)出版社（英文影印版），2002年Sartaj Sahni，Data Structures，Algorithms，and Applications in C+，McGraw-Hill，1998，機(jī)械工業(yè)出版社（影印版）1999年蘇德富，鐘誠(chéng)， 計(jì)算機(jī)算法設(shè)計(jì)與分析，電子工業(yè)出版社，2001盧開澄，計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析，清華大學(xué)出版社，2001王曉東，計(jì)算

4、機(jī)算法設(shè)計(jì)與分析，電子工業(yè)出版社2001第一章 概論與相關(guān)知識(shí)回顧 1.1 算法的概念 形式的定義： 任何一個(gè)對(duì)所有有效輸入總要停機(jī)的圖靈機(jī)是一個(gè)算法。 非形式的定義：一組有窮的規(guī)則，規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。/有限指令的集合，遵循它可以完成一個(gè)特定的任務(wù)。（p21）。 算法必須滿足以下五條特性：1.有限（窮）性：算法必須在有限步內(nèi)終止。 （過(guò)程與算法的區(qū)別，如os）2.確定性：指令必須清楚，無(wú)二義性。 (例：分支語(yǔ)句，表達(dá)式的副作用)3.能（可）行性：每條指令必須充分基本。4.輸入（=0）：輸入是算法開始之前從外部給出的量。（狹義概念）5.輸出（=1）：輸出是同輸入有特定關(guān)系的

5、信息。（廣義概念）1.2 算法學(xué)習(xí)的內(nèi)容 一、設(shè)計(jì) 二、表達(dá) 三、確認(rèn) 四、分析 五、測(cè)試一、設(shè)計(jì)：對(duì)一個(gè)給定的問(wèn)題，設(shè)計(jì)出解算該問(wèn)題的有效算法。設(shè)計(jì)一個(gè)算法的常用技術(shù)是什么？現(xiàn)實(shí)世界中的問(wèn)題是由無(wú)窮多實(shí)例組成，個(gè)別實(shí)例不能被認(rèn)為是問(wèn)題。組成問(wèn)題的無(wú)窮多實(shí)例當(dāng)中的每個(gè)實(shí)例，均可由問(wèn)題定義域的某個(gè)實(shí)體及對(duì)實(shí)體的提問(wèn)構(gòu)成。如：整數(shù)加法問(wèn)題 實(shí)例 x+y a+b 實(shí)體 a，b 問(wèn)題定義域 全體整數(shù)偶對(duì) 指派 a:=2 ，b:=3 提問(wèn) 2+3=？ 關(guān)于p的 問(wèn)題p=算法A 解算p 如果把p的任一實(shí)例的實(shí)體作為算法A的輸入，算法A在有限步內(nèi)總能輸出一個(gè)關(guān)于此實(shí)例的正確答案。 若：存在一個(gè)算法A可以解算

6、問(wèn)題P，則稱問(wèn)題P是算法可解的。（即：具備可行性，在有限步內(nèi)終止。不一定真的可解，受條件和時(shí)空限制） 能行性：倒底需要多少步，是否可以接受（由計(jì)算復(fù)雜性理論給出）二、表達(dá) 自然語(yǔ)言，計(jì)算機(jī)語(yǔ)言，類語(yǔ)言 三、確認(rèn) 算法正確性證明 四、分析 衡量一個(gè)算法的好壞 （絕對(duì)、相對(duì)、效率、效能、時(shí)機(jī)） 要完成的任務(wù)是建立評(píng)價(jià)標(biāo)準(zhǔn)和分析手段目前對(duì)算法評(píng)價(jià)的標(biāo)準(zhǔn)： 1、正確性 2、時(shí)間工作量 3、空間用量 4、簡(jiǎn)單性 5、最佳性1、正確性 算法正確性的評(píng)價(jià)包括兩個(gè)方面 （1）問(wèn)題的解法在數(shù)學(xué)上是正確的 （2）執(zhí)行算法的指令系列是正確的2、時(shí)間工作量 時(shí)間工作量的評(píng)價(jià)應(yīng)該 （1）給出度量的有效信息，恰當(dāng)?shù)胤从乘?/p>

7、法的實(shí)際執(zhí)行時(shí)間 （2）比較解算同一問(wèn)題的兩個(gè)算法之間的效率要求：應(yīng)與具體的計(jì)算機(jī)、程序語(yǔ)言、程序員、實(shí)現(xiàn)細(xì)節(jié)無(wú)關(guān)，足夠精確又足夠一般。 算法時(shí)間工作量的評(píng)價(jià)通?？蓮囊韵聨追N方式考慮： a.實(shí)際執(zhí)行時(shí)間與實(shí)際程序描述有關(guān)、與機(jī)器有關(guān)、與執(zhí)行時(shí)的數(shù)據(jù)輸入集有關(guān)。 b.執(zhí)行指令的條數(shù)依賴于程序設(shè)計(jì)語(yǔ)言和程序員風(fēng)格。 c.指定基本操作，度量基本操作執(zhí)行次數(shù)?；静僮鳎簽榉治鏊惴ǘ槿?lái)的特定操作對(duì)被研究問(wèn)題是基本的，是解算這一問(wèn)題的關(guān)鍵操作，具有隨著輸入規(guī)模增大而增加（次數(shù)）的特征。 度量信息的表達(dá)：（輸入規(guī)模，不同情況）設(shè)：輸入集為 ，I是 的任一元素， 是I出現(xiàn)的概率, 是輸入為I時(shí)的基本操作（

8、執(zhí)行次數(shù)）計(jì)算：平均性態(tài)： 最壞形態(tài)： 例：線性表中查找問(wèn)題 設(shè)L是包含n個(gè)元素的一個(gè)線性表（n個(gè)元素互不相同），對(duì)某個(gè)指定值x，若x在表中找到它出現(xiàn)的下標(biāo)位置；如不在表中，返回0。3、空間用量 空間用量依賴于特定環(huán)境，也可以僅僅通過(guò)算法本身考察 空間用量=指令空間+輸入數(shù)據(jù)空間+執(zhí)行時(shí)數(shù)據(jù)空間 指令空間：與環(huán)境相關(guān)不可預(yù)測(cè)且與算法無(wú)關(guān)，不予考慮 輸入數(shù)據(jù)空間：分為輸入按自然形式存儲(chǔ)和采用特殊結(jié)構(gòu) 結(jié)論： 當(dāng)輸入按自然形式存儲(chǔ)時(shí)空間用量只計(jì)算執(zhí)行時(shí)數(shù)據(jù)空間 當(dāng)輸入采用特殊結(jié)構(gòu)時(shí)空間用量為輸入數(shù)據(jù)空間+執(zhí)行時(shí)數(shù)據(jù)空間4、簡(jiǎn)單性：清晰、易讀、易懂、易證明 5、最佳性：在同一算法類的算法中作評(píng)價(jià)，有

9、一個(gè)算法對(duì)解算問(wèn)題在這個(gè)算法類中是最好的嗎？ 同一算法類的算法指解算問(wèn)題使用同一種基本操作。 定義：為解決某問(wèn)題P的一個(gè)特定算法類（最壞或平均）的計(jì)算復(fù)雜性為MinTA(n),其中TA(n）為該算法類中任一算法A的（最壞或平均）時(shí)間復(fù)雜度。 計(jì)算復(fù)雜性受限于算法類。稱對(duì)問(wèn)題P在算法類下的固有復(fù)雜度，用CP(n)表示。-很難計(jì)算。算法最佳性評(píng)判的通常作法：確定算法類 。解決“下界問(wèn)題” 構(gòu)造一個(gè)函數(shù) f(n)，使得可以證明對(duì)算法類中算法A，均有 TA（n）= f(n)成立。則可得f(n)是CP(n)的一個(gè)下界。解決“上界問(wèn)題” 設(shè)計(jì)出一個(gè)算法類中算法A，分析復(fù)雜度TA（n），則 CP(n)=n0

10、時(shí)有TA*（n）=1,n-1 0 如果g(n)= O( f(n) ) 則 O(f(n) + O(g(n) O(f(n) 書中定理2.1的證明 p25 常用的整數(shù)求和公式 p271.4 描述算法的語(yǔ)言SPARKS 語(yǔ)言：語(yǔ)法、語(yǔ)義、語(yǔ)用 SPARKS語(yǔ)法 1、基本字符集 （未定義） 2、詞法- 保留字、自定義字 數(shù) - 十進(jìn)制 量 - 常量- false、true |- 變量（屬性）-名 | |-類型-標(biāo)準(zhǔn) | | |-構(gòu)造 | |-運(yùn)算 | |-生存周期 | |-作用域全局、局部、形式 |-表達(dá)式-|-運(yùn)算符（算數(shù)、關(guān)系、邏輯） |-計(jì)算順序 |-類型轉(zhuǎn)化規(guī)則 3、語(yǔ)句-賦值 變量-表達(dá)式 |

11、-順序 ； |-分支 |-if-then-else-endif | |-case-endcase | |-goto labal （exit、cycle） |-循環(huán) |-while cond dorepeat | |-loopuntil cond repeat | |-for to by do -repeat | |-loop-repeat |-輸入、輸出-|-read（參數(shù)表） | |-print（參數(shù)表） |-注釋-/ 4、子結(jié)構(gòu)過(guò)程-|-procedure（參數(shù)表） |-調(diào)用（過(guò)程式、函數(shù)式） |-返回 return（參數(shù)表） |-參數(shù)傳遞方式、純過(guò)程 1.5 基本數(shù)據(jù)結(jié)構(gòu)回顧 一、線性表

12、 （順序表、棧、隊(duì)列、數(shù)組、集合） 二、樹 （定義、存儲(chǔ)、森林、集合的樹形表示） 三、二叉樹（定義、存儲(chǔ)、特殊二叉樹、性質(zhì)、堆、二叉檢索樹） 四、圖1.6 數(shù)學(xué)知識(shí)回顧 一、數(shù)學(xué)歸納法 數(shù)學(xué)歸納法基本步驟： 設(shè)P(n)是關(guān)于整數(shù)n的某個(gè)命題 給出P(1)為真的證明 給出若P(i) （in-1）為真，則P(n)也為真的證明 結(jié)論：命題P(n)對(duì)任何整數(shù)n都成立 二、雙重歸納法 設(shè)P(n,m)是與整數(shù)m、n有關(guān)的命題，證明P(n,m)對(duì)任意自然數(shù)n、m都成立，步驟如下： 證明命題P(1,m)對(duì)任意自然數(shù)m成立，命題P(n,1)對(duì)任意自然數(shù)n成立 假設(shè)命題P(n+1,m)和命題P(n,m+1)成立

13、在條件下證明P(n+1,m+1)成立 由，可知命題P(n,m)對(duì)任意自然數(shù)，n、m都成立 三、數(shù)學(xué)歸納法的推廣 定義：良序關(guān)系 設(shè) 是集合S上的一個(gè)關(guān)系，它滿足以下性質(zhì)： 給定S中的x，y，z。如果xy，yz，則xz 給定S中的x，y，z。以下三種可能恰有一種為真 xy x=y yx 如果A是S的任何非空子集，則A中必有一個(gè)元素x，使得對(duì)于A中的所有y，x=y， 則稱關(guān)系為S的一個(gè)良序關(guān)系。 例：對(duì)“小于”關(guān)系 正整數(shù) 良序 整數(shù) x 正實(shí)數(shù) x 定理1（良序關(guān)系的等價(jià)定義）： 是集合S的一個(gè)良序，當(dāng)且僅當(dāng)它滿足性質(zhì)和性質(zhì)，而且對(duì)于所有的j1，不存在具有Xj+1Xj的無(wú)限序列 X1,X2,X3

14、 。 證明：必要性： 設(shè)是S的良序，顯然滿足。對(duì)反證。 如果存在無(wú)限序列Xj+1Xj ，則不滿足，與定義矛盾。與假設(shè)也矛盾。 必要性得證。 充分性：（證在條件下滿足） 反證：如果滿足不滿足 設(shè)A是S的一個(gè)沒(méi)有最小元素的非空無(wú)限子集，由于A非空，所以在A中可以找到X1，由于A無(wú)最小元，故可以找到X2，使X2X1。同理可找到 X3X2 ，X4X3 這樣可以在A中找到具有Xj+1Xj (j1)的無(wú)限序列X1,X2,X3 與條件矛盾。 所以滿足，是S的一個(gè)良序。 意義：證明算法的終止性 如果能夠把計(jì)算的諸狀態(tài)映射到一個(gè)上的良序集S，使得計(jì)算的每一步總是從一個(gè)狀態(tài)x進(jìn)入另一個(gè)狀態(tài)y，并且有f(y)f(x

15、)，則此算法必然終止。 定理2（推廣的數(shù)學(xué)歸納法）： 設(shè)S對(duì)于為良序集，并且設(shè)P(x)是關(guān)于S中元素x的一個(gè)命題，如果P(x)能在P(y)對(duì)于所有的yx為真的假定下得證，則P(x)對(duì)S中所有的x為真。 證明： 反證 令A(yù)是使得P(x)為假的所有x的集合，若A非空， A對(duì)于是良序，于是A中有一個(gè)最小元素x0。 而P(y)對(duì)所有yx0為真，所以P(x0)為真. 即：不在A中。與假設(shè)矛盾。 所以A應(yīng)為空。 定理得證。 二、遞歸方程及求解 遞歸方程：對(duì)函數(shù)序列，其通項(xiàng)是遞歸定義的，即其通項(xiàng)h(n)是通過(guò)h(0)h(n-1)定義，稱為遞歸式（遞歸方程） 遞歸方程常見(jiàn)解法： 1、生成函數(shù)法： 對(duì)函數(shù)序列a

16、0,a1,a2， 函數(shù)G(x)=a0+a1x+. 稱為序列的生成函數(shù)。 生成函數(shù)法：首先設(shè)對(duì)x的某些值生成函數(shù)G(x)值收斂，并且能求得G(x)的表達(dá)式，然后將G(x)重新展開成x的冪級(jí)數(shù)，則此展開式中x的n次項(xiàng)的系數(shù)即為an的表達(dá)式。*對(duì)遞歸式a0,a1,a2，,只是想求an ，x是序列和構(gòu)造函數(shù)的關(guān)系橋梁，生成函數(shù)G(x)只是形式，G依賴于x，若可以求得G(x)，對(duì)參數(shù)x是否收斂，收斂域是什么，不必知道。只是想從函數(shù)特征中來(lái)得到 an 的有用信息。 例1、漢諾塔問(wèn)題解：構(gòu)造生成函數(shù) 求解H(x) _ 得 分解H(x)成冪級(jí)數(shù) 令 則 A=-1 B=1 例2（Fibonacci數(shù)列）有一對(duì)兔子，假設(shè)過(guò)兩個(gè)月便可以繁殖一對(duì)兔子，以后每月生一對(duì)，問(wèn)過(guò)n個(gè)月后共有多少對(duì)兔子？ 解：以為Fn系數(shù)，構(gòu)成生成函數(shù) 其中 2、特征方程及特征根法 若a1,a2,ak是常數(shù)，且ak0，nk,則遞歸關(guān)系稱為K階常系數(shù)線性齊次遞歸關(guān)系，它的特征方程是 可先求出特征方程的根，再由初始條件確定通解表示式中的待定系數(shù)，得到原遞歸關(guān)系式的解。如果特征方程有k個(gè)互不相同的根q1,qk， 則通解為 c1,ck為待定系數(shù) 。 例： 解：遞歸方程對(duì)應(yīng)的特征方程