計(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é)參考書(shū),余祥宣，崔國(guó)華，鄒海明，計(jì)算機(jī)算法基礎(chǔ) （第三版），2006 ，華中科技大學(xué)出版社 E.Horowitz and S. Sahni: Fundamentals of Computer Algorithms, Computer Science Press, Pitman, Inc.

2、Clifford 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，高等教育出版社（影印版

3、），2001年 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 盧開(kāi)澄，計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析，清華大學(xué)出版社，20

4、01 王曉東，計(jì)算機(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）：輸入是算法開(kāi)始之前從外部給出的量。（狹義概念） 5.輸出（=

5、1）：輸出是同輸入有特定關(guān)系的信息。（廣義概念）,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í)例的

6、正確答案。 若：存在一個(gè)算法A可以解算問(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)

7、價(jià)應(yīng)該 （1）給出度量的有效信息，恰當(dāng)?shù)胤从乘惴ǖ膶?shí)際執(zhí)行時(shí)間 （2）比較解算同一問(wèn)題的兩個(gè)算法之間的效率 要求：應(yīng)與具體的計(jì)算機(jī)、程序語(yǔ)言、程序員、實(shí)現(xiàn)細(xì)節(jié)無(wú)關(guān)，足夠精確又足夠一般。,算法時(shí)間工作量的評(píng)價(jià)通常可從以下幾種方式考慮： 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是 的任

8、一元素， 是I出現(xiàn)的概率, 是輸入為I時(shí)的基本操作（執(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)單性：清晰、

9、易讀、易懂、易證明 5、最佳性：在同一算法類的算法中作評(píng)價(jià)，有一個(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è)下界。 解決“上界

10、問(wèn)題” 設(shè)計(jì)出一個(gè)算法類中算法A，分析復(fù)雜度TA（n），則 CP(n)=n0時(shí)有TA*（n）= f(n) ，則A*是該算法類的最佳算法。,例：在n個(gè)元素線性表中查找最小元的順序查找法。 算法類：比較、復(fù)制 “下界分析”：令f（n）=n-1, 由淘汰法知f（n）是復(fù)雜度下界 “上界分析”：算法與輸入數(shù)據(jù)無(wú)關(guān)，對(duì)任何輸入|I|=n， w(n)=n-1 , A(n)=n-1,所以n-1是問(wèn)題復(fù)雜度上界。 因?yàn)椋簩?duì)n=1,n-1= f（n） 所以：算法是解算該問(wèn)題的比較類算法中的一個(gè)最佳算法。 *對(duì)最佳算法的分析要注意問(wèn)題的變化和算法類的確定（求最大元和次 大元；比較類排序和基數(shù)排序）,五、測(cè)試 算法

11、分析的兩個(gè)階段：事前分析，事后測(cè)試 事前分析：時(shí)間工作量分析 事后測(cè)試：由調(diào)試和作時(shí)空分布圖兩部分組成。 調(diào)試：在抽象數(shù)據(jù)集上執(zhí)行程序，以確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果，若有，則修改程序。 作時(shí)空分布圖：用各種給定的數(shù)據(jù)執(zhí)行調(diào)試認(rèn)為是正確的程序，并測(cè)定為計(jì)算出結(jié)果所花去的時(shí)間和空間。,時(shí)空性能分布圖 算法時(shí)間的準(zhǔn)確測(cè)量 時(shí)鐘不準(zhǔn)確造成的噪聲 解決方法 增大規(guī)模 重復(fù)執(zhí)行 分布圖的做法,1.3 復(fù)雜度的漸進(jìn)表示 目的和方法,一些性質(zhì)： O(f(n) + O(g(n) = O(maxf(n),g(n) O(f(n) + O(g(n) = O( f(n)+g(n) ) O( f(n) ) * O( g(n

12、) )= O( f(n)*g(n) ) O( Cf(n) = O( f(n) ) C 0 如果g(n)= O( f(n) ) 則 O(f(n) + O(g(n) O(f(n),書(shū)中定理2.1的證明 p25 常用的整數(shù)求和公式 p27,1.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ì)

13、算順序 |-類型轉(zhuǎn)化規(guī)則,3、語(yǔ)句-賦值 變量-表達(dá)式 |-順序 ； |-分支 |-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ù)表） |-

14、參數(shù)傳遞方式、純過(guò)程,1.5 基本數(shù)據(jù)結(jié)構(gòu)回顧 一、線性表 （順序表、棧、隊(duì)列、數(shù)組、集合） 二、樹(shù) （定義、存儲(chǔ)、森林、集合的樹(shù)形表示） 三、二叉樹(shù)（定義、存儲(chǔ)、特殊二叉樹(shù)、性質(zhì)、堆、二叉檢索樹(shù)） 四、圖,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ù)

15、n成立 假設(shè)命題P(n+1,m)和命題P(n,m+1)成立 在條件下證明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ì)于

16、所有的j1，不存在具有Xj+1Xj的無(wú)限 序列 X1,X2,X3 。 證明：必要性： 設(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ì)

17、算的每一步總是從一個(gè)狀態(tài)x進(jìn)入另一個(gè)狀態(tài)y，并且有f(y)f(x)，則此算法必然終止。,定理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)定義，稱為遞歸

18、式（遞歸方程） 遞歸方程常見(jiàn)解法： 1、生成函數(shù)法： 對(duì)函數(shù)序列a0,a1,a2， 函數(shù)G(x)=a0+a1x+. 稱為序列的生成函數(shù)。 生成函數(shù)法：首先設(shè)對(duì)x的某些值生成函數(shù)G(x)值收斂，并且能求得G(x)的表達(dá)式，然后將G(x)重新展開(kāi)成x的冪級(jí)數(shù)，則此展開(kāi)式中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， 則通解