計算機算法基礎第一章

有兩種思想,像珠寶商放在天鵝絨上的寶石一樣熠熠生輝.一個是微積分，另一個就是算法.微積分以及在微積分基礎上建立起來的數(shù)學分析體系造就了現(xiàn)代科學,而算法造就了現(xiàn)代世界.——DavidBerlinski算法的探討內(nèi)容問題是否可解1930’s探討集中于推斷特定問題在計算機上是否可解，基本方法為：選定一個計算模型，視察是否能在該模型上創(chuàng)建能解決問題的算法。這些計算模型包括：Postmachines、Turingmachines等。這一階段的成果是：大部分問題為不行解。高效率的解決方法隨著計算機的發(fā)展和數(shù)據(jù)資源的增加，算法探討轉向針對可解的問題，找到高效率的解決方法。算法的應用數(shù)據(jù)庫中的檢索搜尋引擎中的檢索公共密鑰加密和數(shù)字簽名技術優(yōu)化問題最短路徑資源安排…章節(jié)支配《計算機算法基礎》，余祥宣、崔國華、鄒海明著，華中科技高校出版社第一章導引與基本數(shù)據(jù)結構 √其次章分治法 √第三章貪心方法 √第四章動態(tài)規(guī)劃 √第五章檢索與周游 √第六章回溯法 √第七章分枝-限界 √第八章NP-問題 ⊙

預備學問數(shù)學：集合、證明方法（干脆、間接、反證、反例、歸納假設）、對數(shù)基礎、FLOOR&CEILING函數(shù)、階乘、遞歸關系數(shù)據(jù)結構：鏈接表、圖、樹、二元樹第一章導引與基本數(shù)據(jù)結構1.1算法的定義及特性什么是算法？一系列將問題的輸入轉換為輸出的計算或操作步驟。

2.算法的五個重要特性確定性、能行性、輸入、輸出、有窮性1）確定性：算法的每種運算必須要有準確的定義，不能有二義性。例：不符合確定性的運算5/0將6或7與x相加未賦值變量參與運算2）能行性算法中有待實現(xiàn)的運算都是基本的運算，原理上每種運算都能由人用紙和筆在有限的時間內(nèi)完成。例：整數(shù)的算術運算是“能行”的實數(shù)的算術運算是“不能行”的3）輸入每個算法有0個或多個輸入。這些輸入是在算法起先之前給出的量，取自于特定的對象集合——定義域（或值域）4）輸出一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關系的量。5）有窮性一個算法總是在執(zhí)行了有窮步的運算之后終止。計算過程：只滿足確定性、能行性、輸入、輸出四個特性但不確定能終止的一組規(guī)則。

精確理解算法和計算過程的區(qū)分：不能終止的計算過程：操作系統(tǒng)算法是“可以終止的計算過程”算法的時效性：只能把在相當有窮步內(nèi)終止的算法投入到計算機上運行3.我們的主要任務算法學習將涉及5個方面的內(nèi)容：1）設計算法：創(chuàng)建性的活動2）表示算法：思想的表示形式3）確認算法：證明算法的正確性程序的證明4）分析算法：算法時空特性分析5）測試程序：調(diào)試和作出時空分布圖本課程集中于學習算法的設計與分析。通過學習，駕馭計算機算法設計和分析基本策略與方法，為設計更困難、更有效的算法奠定基礎4.算法描述語言自然語言,數(shù)學語言,流程圖,程序設計語言等等.5.問題的求解過程2)建立數(shù)學模型1)問題的陳述3)算法設計用科學規(guī)范的語言,對所求解的問題做精確的描述.通過對問題的分析,找出其中的全部操作對象及操作對象之間的關系并用數(shù)學語言加以描述.依據(jù)數(shù)學模型設計問題的計算機求解算法.4)算法的正確性證明5)算法的程序實現(xiàn)6)算法分析證明算法對一切合法輸入均能在有限次計算后產(chǎn)生正確輸出.對執(zhí)行該算法所消耗的計算機資源進行估算.將算法正確地編寫成機器語言程序.1.2分析算法1.分析算法的目的在于：通過對算法的分析，在把算法變成程序實際運行前，就知道為完成一項任務所設計的算法的好壞，從而運行好的算法，改進差的算法，避開無益的人力和物力奢侈。算法分析是計算機領域的古老而前沿的課題。進行算法分析的基本技術：抽象2.重要的假設和約定1）計算機模型的假設

Turing機模型：計算機形式理論模型通用計算機模型：單處理器有足夠的“內(nèi)存”能在固定的時間內(nèi)存取數(shù)據(jù)單元2）計算的約定確定運用什么樣的運算及其執(zhí)行時間。從計算時間上，運算的分類：時間囿界于常數(shù)的運算：盡管每種運算的執(zhí)行時間不同，但一般只花一個固定量的時間（單位時間）就可完成?！せ舅阈g運算，如整數(shù)、浮點數(shù)的加、減、乘、除·字符運算·賦值運算·過程調(diào)用等2）計算的約定（續(xù)）其他運算：

·字符串操作：與字符串中字符的數(shù)量成正比

·記錄操作：與記錄的屬性數(shù)、屬性類型等有關

·

特點：運算時間無定量如何分析非時間囿界于常數(shù)的運算：分解成若干時間囿界于常數(shù)的運算。

如：Tstring=Length（String）*tchar算法的執(zhí)行時間=∑Fi*ti其中，F(xiàn)i是算法中用到的某種運算i的次數(shù)，ti是該運算執(zhí)行一次所用的時間。3）工作數(shù)據(jù)集的選擇編制能夠反映算法在最好、平均、最壞狀況下工作的數(shù)據(jù)配置。然后運用這些數(shù)據(jù)配置運行算法，以了解算法的性能。測試數(shù)據(jù)集的生成作為算法分析的數(shù)據(jù)集：典型特征作為程序性能測試的數(shù)據(jù)集：對執(zhí)行指標產(chǎn)生影響的性質(zhì)3.如何進行算法分析？對算法進行全面分析，可分兩個階段進行：事前分析：就算法本身，通過對其執(zhí)行性能的理論分析，得出關于算法特性——時間和空間的一個特征函數(shù)（Ο、Ω）——與計算機物理軟硬件沒有干脆關系。事后測試：將算法編制成程序后實際放到計算機上運行，收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行分析推斷——干脆與物理實現(xiàn)有關。1）事前分析目的：試圖得出關于算法執(zhí)行特性的一種形式描述，以“理論上”衡量算法的“好壞”。如何給出反映算法執(zhí)行特性的描述？最干脆方法：統(tǒng)計算法中各種運算的執(zhí)行狀況，包括：運用了哪些運算每種運算被執(zhí)行的次數(shù)該種運算執(zhí)行一次所花費的時間等。算法的執(zhí)行時間=∑Fi*ti頻率計數(shù)例：

x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)

分析：

(a)：x←x+y執(zhí)行了1次

(b)：x←x+y執(zhí)行了n次

(c)：x←x+y執(zhí)行了n2次定義：

頻率計數(shù)：一條語句或一種運算在算法（或程序）體中的執(zhí)行次數(shù)。

算法2.7插入分類

procedureINSERTIONSORT(A,n)//將A(1：n)中的元素按非降次序分類，n≥1//1A(0)←-∞//設置初始邊界值

2forj←2tondo//A(1:j-1)已分類//3item←A(j);i←j-14whileitem<A(i)do//0≤i<j//5A(i+1)←A(i);i←i-16repeat7A(i+1)←item;8repeatendINSERTIONSORT

(8,5,4,9)(8,5,4,9)

(5,8,4,9)(5,8,

4,9)(4,5,8,9)(4,5,8,9)一條語句在整個程序運行時實際執(zhí)行時間=頻率計數(shù)*每執(zhí)行一次該語句所需的時間如何刻畫算法執(zhí)行特性的形式描述實際執(zhí)行時間受約于諸多實際因素，如機器類型、編程與語言、操作系統(tǒng)等，沒有統(tǒng)一的描述模型。在事前分析中，只限于確定與所運用的機器及其他環(huán)境因素無關的頻率計數(shù)，依此建立理論分析模型。數(shù)量級語句的數(shù)量級：語句的執(zhí)行頻率例：1，n，n2算法的數(shù)量級：算法所包含的全部語句的執(zhí)行頻率之和。算法的數(shù)量級從本質(zhì)上反映了一個算法的執(zhí)行特性。例：假如求解同一個問題的三個算法分別具有n，n2，n3數(shù)量級。若n=10，則可能的執(zhí)行時間將分別是10，100，1000個單位時間——與環(huán)境因素無關。計算時間/頻率計數(shù)的表示函數(shù)通過事前分析給出算法計算時間（頻率計數(shù)）的一個函數(shù)表示形式，一般記為與輸入規(guī)模n有關的函數(shù)形式：f(n)注：最高次項與函數(shù)整體的關系空間特性分析（略）2）事后測試目的：運行程序，確定程序實際耗費的時間與空間，驗證從前的分析結論——包括正確性、執(zhí)行性能等，比較、優(yōu)化所設計的算法。分析手段：作時、空性能分布圖4.計算時間的漸近表示記：算法的計算時間為f(n)數(shù)量級限界函數(shù)為g(n)其中，n是輸入或輸出規(guī)模的某種測度。f(n)表示算法的“實際”執(zhí)行時間—與機器及語言有關。g(n)是形式簡潔的函數(shù)，如nm，logn，2n，n!等。是事前分析中通過對計算時間或頻率計數(shù)統(tǒng)計分析所得的、與機器及語言無關的函數(shù)。

以下給出算法執(zhí)行時間：上界（О）、下界（Ω）、“平均”（）的定義。1）上界函數(shù)定義1假如存在兩個正常數(shù)c和n0，對于全部的n≥n0，有|f(n)|≤c|g(n)|則記作f(n)=Ο(g(n))含義：假如算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個上界函數(shù)。f(n)的數(shù)量級就是g(n)。試圖求出最小的g(n)，使得f(n)=Ο(g(n))。多項式定理:定理1若A(n)=amnm+…+a1n+a0是一個m次多項式，則有A(n)=Ο(nm)即：變量n的固定階數(shù)為m的任一多項式，與此多項式的最高階nm同階。

證明：取n0=1,當n≥n0時，有|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm

≤(|am|+|am-1|+…+|a0|)nm

令c=|am|+|am-1|+…+|a0|則，定理得證。計算時間的數(shù)量級對算法有效性的影響數(shù)量級的大小對算法的有效性有確定性的影響。例：假設解決同一個問題的兩個算法，它們都有n個輸入，計算時間的數(shù)量級分別是n2和nlogn。則，n=1024：分別須要1048576和10240次運算。n=2048：分別須要4194304和22528次運算。分析：在n加倍的狀況下，一個Ο(n2)的算法計算時間增長4倍，而一個Ο(nlogn)算法則只用兩倍多一點的時間即可完成。算法2.8歸并分類

procedureMERGESORT(low,high)//A(low:high)是一個全程數(shù)組，它含有high-low+1≥0個待分類的元素//integerlow,highiflow<highthenmid←//計算中分點//callMERGESORT(low,mid)//在第一個子集合上分類(遞歸)//callMERGESORT(mid+1,high)//在其次個子集合上分類(遞歸)//callMERGE(low,mid,high)//歸并已分類的兩子集合//endifendMERGESORTMerge算法示例(4,5,8,9)|(1,2,6,7)(1,2,4,5,6,7,8,9)參數(shù)：low=1;high=8;mid=4(4,5,8,9)|(1,2,6,7)hjjjjhh(14256789)j算法分類（計算時間）多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。常見的多項式限界函數(shù)有：Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法常見的指數(shù)時間限界函數(shù)：Ο(2n)<Ο(n！)<Ο(nn)說明：當n取值較大時，指數(shù)時間算法和多項式時間算法在計算時間上特別懸殊。典型的計算時間函數(shù)曲線當數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)有的計算機系統(tǒng)上運行具有比Ο(nlogn)困難度還高的算法是比較困難的。指數(shù)時間算法只有在n取值特別小時才好用。要想在依次處理機上擴大所處理問題的規(guī)模，有效的途徑是降低算法的計算困難度，而不是（僅僅依靠）提高計算機的速度。計算時間函數(shù)值比較定義1.2假如存在兩個正常數(shù)c和n0，對于全部的n≥n0，有|f(n)|≥c|g(n)|則記作f(n)=Ω(g(n))含義：假如算法用n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是不小于|g(n)|的一個常數(shù)倍。所以g(n)是計算時間f(n)的一個下界函數(shù)。試圖求出“最大”的g(n)，使得f(n)=Ω(g(n))。2）下界函數(shù)定義1.3假如存在正常數(shù)c1，c2和n0，對于全部的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|則記作含義：算法在最好和最壞狀況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔衒(n)=Ω(g(n))，又有f(n)=Ο(g(n))3）“平均狀況”限界函數(shù)4）限界函數(shù)的性質(zhì)1）若且，則。即О具有傳遞性。（同）2）當且僅當3）若，則。即，定義了一個等價關系（等價類）5.常用的整數(shù)求和公式在算法分析中，在統(tǒng)計語句的頻率時，求和公式的一般表示形式為：如：1+1+…+1（有n項1）=n1+2+…+n=n212+22+…+n2=n320+21+…+2n=2n+11.3關于SPARKS語言本書為描述算法選用的一種類計算機語言類PASCAL語言結構化程序描述1.基本語法成分1）數(shù)據(jù)類型：整型、實型、布爾型、字符型2）變量聲明：integeri,j;booleanb;charc3）賦值運算：（變量）←（表達式）4）邏輯運算：andornot5）關系運算：＜≤＝≠≥＞6）變量聲明：類型說明符變量；7）數(shù)組聲明：integerA（1：5，7：20）8）限制結構：依次:分支:·ifconditionthenS1elseS2endif·case:cond1:S1;:cond2:S2;…:condn:Sn:else:Sn+1endcase循環(huán):

·whileconddoSrepeat

·loopSuntilcondrepeat

·forvble←starttofinishbyincrementdoSrepeat

2.同質(zhì)異項3.其它

函數(shù)的定義與調(diào)用、函數(shù)和過程、變量與形式參數(shù)1.4基本數(shù)據(jù)結構1.棧和隊列棧和隊列：n個元素的線性表利用動態(tài)數(shù)據(jù)結構——鏈表實現(xiàn)?；蜿犃欣渺o態(tài)數(shù)據(jù)結構——數(shù)組實現(xiàn)?；蜿犃谢谝陨蟽煞N表示形式的棧和隊列上的基本運算隊列的數(shù)組表示棧的數(shù)組表示用一維數(shù)組STACKS（1:n）表示棧底：STACKS（1）第i個元素STACKS(i)棧頂指針：topprocedureADD(item,STACAK,n,top)iftop≥nthencallSTACKFULLendiftop←top+1STACK(top)←itemendaddprocedureDELETE(item,STACK,top)iftop≤0thencallSTACKEMPTYendifitem←STACK(top)top←top-1endDELETE棧的數(shù)組表示——增加、刪除棧的鏈接表表示一種單向鏈接表兩個信息段：DATA存放數(shù)據(jù)，LINK指向前一節(jié)點節(jié)點插入

callGETNODE(T)DATA(T)←itemLINK(T)←STACKSTACK←T節(jié)點刪除

item←DATA(STACK)T←STACKSTACK←LINK(SATCK)callRETNODE(T)ASTACK0棧的鏈接表表示——增加、刪除2.樹1）樹的一般定義定義1.4樹（tree）是一個或多個結點的有限集合，它使得：有一個指定為根（root）的結點剩余結點被劃分成m≥0個不相交的集合：

T1，…，Tm

這些集合的每一個又都是一棵樹，并稱T1，…，Tm為根的子樹。關于樹的重要概念結點的度（degree）：一個結點的子樹數(shù)樹的度：樹中結點度的最大值結點的級（level）（又叫層）：設根是1級，若某結點在p級，則它的兒子在p+1級樹的高度（或深度）：樹中結點的最大級數(shù)葉子（終端結點）：度為0的結點內(nèi)結點（非終端結點）：度不為0的結點森林：m≥0個不相交樹的集合。樹的表示方法用鏈接表表示

每個結點三個信息段：TAG,DATA,LINK

TAG＝0，DATA存數(shù)據(jù)；TAG=1,DATA存鏈接信息，指向一棵子樹2）二元樹定義1.5二元樹（binarytree）是結點的有限集合，它或者為空，或者由一個根和兩棵稱為左子樹和右子樹的不相交二元樹所組成。二元樹與度為2的樹的區(qū)分二元樹性質(zhì)1：引理1.1一棵二元樹第i級的最大結點數(shù)是2i-1。深度為k的二元樹的最大結點數(shù)為2k-1,k>0。特殊形態(tài)的二元樹

滿二元樹：深度為k且有2k-1個結點的二元樹

完全二元樹：一棵有n個結點深度為k的二元樹，當它的結點相當于深度為k的滿二元樹中編號為1到n的結點時，稱該二元樹是完全的。完全二元樹的葉子結點至多出現(xiàn)在相鄰的兩級上。完全二元樹的結點可以緊湊地存放在一個一維數(shù)組中（性質(zhì)見引理1.2）。二元樹的表示方法1.數(shù)組表示法：對于完全二元樹，空間效率好；其他二元樹，要奢侈大量空間2.鏈表法：結構簡潔，有效。鏈表中每個結點有三個信息段，LCHILD,DATA和RCHILD③堆：堆是一棵完全二元樹，它的每個結點的值至少和該結點的兒子們（假如存在的話）的值一樣大（max-堆）（或小，min-堆）。

④二分檢索樹：二分檢索樹Ｔ是一棵二元樹，它或者為空，或者其每個結點含有一個可以比較大小的數(shù)據(jù)元素，且有：·Ｔ的左子樹的全部元素比根結點中的元素小；·Ｔ的右子樹的全部元素比根結點中的元素大；·Ｔ的左子樹和右子樹也是二分檢索樹。

注：二分檢索樹要求樹中全部結點的元素值互異3.樹的應用——不相交集合的合并及搜尋問題問題描述：給定一個全集U，該集合包含n個元素很明顯該集合包含多個不相交的子集某些應用須要實現(xiàn)這些不相交子集的合并、查找操作，并且這些操作最終可形成序列如何高效率實現(xiàn)這些操作序列就是我們要解決的問題集合操作舉例n=10，U={1,2,3,4,5,6,7,8,9,10}s1={1,7,8,9};s2={2,5,10};s3={3,4,6}合并運算：s1∪s2={1,7,8,9,2,5,10}查找運算：元素4包含在s1,s2,s3的哪個集合中？方法一——位向量方法一：位向量s1={1,0,0,0,0,0,1,1,1,0}；s2={0,1,0,0,1,0,0,0,0,1}；利用位運算可得出s1∪s2={1,1,0,0,1,0,1,1,1,1}缺點：n很大，超過一個機器字長，而參與運算的集合的勢很小時，運算與n成正比。方法二——集合元素表s1={1,7,8,9};s2={2,5,10}合并操作：|s1|+|s2|查找操作：最壞為|n|方法三——樹數(shù)據(jù)結構字符數(shù)組U={1,2,3,4,5,6,7,8,9,10}子集s1={1,7,8,9};s2={2,5,10}則用數(shù)組Parent表示集合s1和s2：數(shù)組中記錄的是節(jié)點U[i]的父節(jié)點在Parent中的位置（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）00……2…1112合并操作U(1,2)后：（Parent[1]=2）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）20……2…1112查找元素F(9)U操作為常量時間，F(xiàn)操作則與查找元素在集合樹中的層數(shù)有關。U和F的性能問題——退化樹問題描述：有集合如下：（1）（2）…（n）000依次作下列操作：U(1,2),F(1),U(2,3),F(1),…,U(n-1,n)依據(jù)算法U和F，最終得到的樹剛好間耗費分析U：每次都是常量時間，因此總共是O(n-1)F(1)：2+3+…+(n-1)，因此是O(n^2)癥結？合并操作！加權規(guī)則節(jié)點數(shù)少的樹合并到節(jié)點數(shù)多的樹中。字符數(shù)組U={1,2,3,4,5,6,7,8,9,10}子集s1={1,7,8,9};s2={2,5,10}（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）-4-3……2…1112UnionF序列演示分析Union(1,2),F(1),Union(2,3),F(1),…,Union(n-1,n)Union合并的開銷較u要大，但仍舊是常量時間每次查找1耗費時間為2，常量時間，則執(zhí)行n-2次查找耗費時間為O(n)留意：本例的查找耗時不是最壞狀況最壞狀況由引理1.3給出引理1.3引理1.3設T是一棵由算法union所產(chǎn)生的有n個節(jié)點的樹。在T中沒有節(jié)點的級數(shù)會大于（logn的下界+1）證明：n=1，明顯引理為真；i為T的級數(shù)，假設當i<=n-1時，引理為真，現(xiàn)證對于i=n，引理也為真；令k和j是形成樹T的最終一次合并，即Union(k,j)；用count()表示數(shù)的節(jié)點數(shù)，假設count(j)=m，那么count(k)=n-m；不失一般性，可假設1<=m<n/2，則有m<=n-m；那么經(jīng)Union合并后，j的父親為k；如右圖：則T的級數(shù)：1）等于k的級數(shù)：log(n-m)的下界+1<=（logn的下界+1）2）或者等于（j的級數(shù)+1）：（logm的下界+2）<=（log(n/2)的下界+2）<=（logn的下界+1）得證壓縮規(guī)則更快的平均查找時間，適用于頻繁查找操作例1.2在下圖示例中實現(xiàn)8次對元素8的查找，用Find(8)算法實現(xiàn)總共20次，優(yōu)于運用F的8*3=24次結論：對于m次Find和n次Union的混合序列（m>=n），處理時間接近O(m)，但稍差。具體描述見引理1.4。例1.24.圖圖Ｇ由稱之為結點Ｖ和邊Ｅ的兩個集合組成，記為G=（V，E）。其中，Ｖ是一個有限非空的結點集合；Ｅ是結點對偶的集合，Ｅ的每一對偶表示Ｇ的一條邊。有關圖的的重要概念無向圖：邊的表示（ｉ，ｊ）有向圖：邊的表示〈ｉ，ｊ〉成本：帶有成本的圖稱為網(wǎng)絡鄰接：結點的度（出度／入度）路徑：由結點vp到vq的一條路（path）是結點

vp，

vi1，

vi2，

…，

vim，

vq的一個序列，它使得(vp，

vi1)

，(vi1

，vi2)

，

…，

(

vim，

vq)是E（G）的邊。路的長度：組成路的邊數(shù)。簡潔路徑：除了第一和最終一個結點可以相同以外，其它全部結點都不同。環(huán)：第一個和最終一個結點相同的簡潔路。連通圖：在無向圖中，假如每對結點之間都存在一條路，則稱該圖是連通的。子圖：是由G的結點集V的子集（記為VB）和邊集E中連接VB中結點的邊的子集所組成的圖。連通分圖：一個圖的最大連通子圖。有向圖的強連通性：在有向圖中，假如對于每一對結點i和j，既存在一條從i到j的路，又存在一條從j到i的路，則稱該有向圖是強連通的。圖的表示方法鄰接矩陣鄰接表1.5遞歸和消去遞歸1.遞歸干脆調(diào)用自己或間接通過一些語句調(diào)用自己遞歸是一種強有力的設計方法描述某些數(shù)學問題特別自然，易于證明算法遞歸的效率問題執(zhí)行時間、空間消耗多例1.3斐波那契(Fibonacci)序列：

F0=F1=1Fi=Fi-1+Fi-2

（i>1)

算法1.7求斐波那契數(shù)

procedureF(n)//返回第n個斐波那契數(shù)//integernifn<=1thenreturn(1)elsereturn(F(n-1)+F(n-2))endifendF算法效率：對F(n-1)、F(n-2)存在大量的重復計算改進：保存中間結果例1.4歐幾里得算法已知兩個非負整數(shù)a和b，且a＞b≥0，求這兩個數(shù)的最大公因數(shù)。輾轉相除法：若b=0，則a和b的最大公因數(shù)等于a；若b＞0，則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。算法1.8求最大公因數(shù)

procedureGCD(a,b)//約定a>b//ifb=0thenreturn(a)elsereturn(GCD(b,amodb))endifendGCD

例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2遞推遞推遞推遞推回來回來回來回來結果為GCD(22,8)=2例1.5遞歸在非數(shù)值算法設計中的應用已知元素x，推斷x是否在A（1：n）中。算法1.9在A（1：n）中檢索xprocedureSEARCH(i)//假如在A（1：n）中有一元素A（k）=x，則將其第一次出現(xiàn)的下標k返回，否則返回0//globaln,x,A(1:n)case:i>n:return(0):A(i)=x;return(i):else:return(SEARCH(i+1))endcaseendSEARCH2.消去遞歸干脆遞歸的消去規(guī)則：基本思路：將遞歸過程中出現(xiàn)遞歸調(diào)用的地方，用等價的非遞歸代碼來代替，并對return語句做適當處理。13條規(guī)則：處理干脆遞歸調(diào)用中的遞歸代碼和return語句，將之轉換成等價的迭代代碼。初始化⑴在過程的起先部分，插入說明為棧的代碼并將其初始化為空。在一般狀況下，這個棧用來存放參數(shù)、局部變量和函數(shù)的值、每次遞歸調(diào)用的返回地址。⑵將標號L1附于第一條可執(zhí)行語句。然后對于每一處遞歸調(diào)用都用一組執(zhí)行下列規(guī)則的指令來代替。處理遞歸調(diào)用語句⑶將全部參數(shù)和局部變量的值存入棧。棧頂指針可作為一個全程變量來看待。⑷建立第i個新標號Li，并將i存入棧。這個標號的i值將用來計算返回地址。此標號放在規(guī)則⑺所描述的程序段中。⑸計算這次調(diào)用的各實在參數(shù)（可能是表達式）的值，并把這些值賦給相應的形式參數(shù)。⑹插入一條無條件轉向語句轉向過程的起先部分：GotoL1對遞歸嵌套調(diào)用的處理⑺假如這過程是函數(shù)，則對遞歸過程中含有此次函數(shù)調(diào)用的那條語句做如下處理：將該語句的此次函數(shù)調(diào)用部分用從棧頂取回該函數(shù)值的代碼來代替，其余部分的代碼按原描述方式照抄，并將⑷中建立的標號附于這條語句上。假如此過程不是函數(shù)，則將⑷中建立的標號附于⑹所產(chǎn)生的轉移語句后面的那條語句。以上步驟實現(xiàn)消去過程中的遞歸調(diào)用。下面對過程中出現(xiàn)return語句進行處理（純過程結束處的end可看成是一條沒有值與之聯(lián)系的return語句）。對每個有return語句的地方，執(zhí)行下述規(guī)則：⑻假如棧為空，則執(zhí)行正常返回。⑼否則，將全部輸出參數(shù)（帶有返回值的出口參數(shù)，out/inout型）的當前值賦給棧頂上的那些對應的變量。⑽假如棧中有返回地址標號的下標，就插入一條此下標從棧中退出的代碼，并把這個下標賦給一個未運用的變量。⑾從棧中退出全部局部變量和參數(shù)的值并吧它們賦給對應的變量。⑿假如這個過程是函數(shù)，則插入以下指令，這些指令用來計算緊接在return后面的表達式并將結果值存入棧頂。⒀用返回地址標號的下標實現(xiàn)對該標號的轉向。例1.6遞歸調(diào)用示例求數(shù)組元素中的最大值算法1.10遞歸求取數(shù)組元素的最大值

procedureMAX1(i)//查找數(shù)組A中最大值元素，并返回該元素的最大下標。//globalintegern,A(1:n),j,kintegeriifi<nthenj←MAX1(i+1)//遞歸調(diào)用Max1.doc//ifA(i)>A(j)thenk←ielsek←jendifelsek←nendif

return(k)//遞歸調(diào)用的返回//endMAX1``消去上例中的遞歸算法1.11運用上述的規(guī)則消去例1.10中的遞歸代碼procedureMAX2(i)localintegerj,k;globalintegern,A(1:n)integerIintegerSTACK(1:2*n)top←0//規(guī)則1，聲明棧的代碼，并初始化為空//L1:ifi<n//規(guī)則2，將標號L1賦于第一條可執(zhí)行語句前//thentop←top+1;STACK(top)←i;//規(guī)則3，參數(shù)或局部變量的值入棧//top←top+1;STACK(top)←2;//規(guī)則4，建立新的標號2，并入棧//

i←i+1//規(guī)則5，計算參數(shù)值//gotoL1//規(guī)則6，無條件轉向算法的起先部分//L2:j←STACK(top);top←top-1;//規(guī)則7，處理函數(shù)調(diào)用，并將標號2賦于該語句上//ifA(i)>A(j)thenk←Ielsek←jendifelsek←nendififtop=0thenreturn(k)//規(guī)則8，假如?？?，則正常返回//elseaddr←STACK(top);top←top-1;//規(guī)則10，從棧中退出返回標號//i←STACK(top);top←top-1;//規(guī)則11，從棧中退出局部變量和參數(shù)的值//top←top+1;STACK(top)←k;//規(guī)則12，計算返回值，并將之入棧//ifaddr=2thengotoL2endif//規(guī)則13，用返回地址標號的下標實現(xiàn)對該標號的轉向//endifendMAX2進一步優(yōu)化和簡化經(jīng)過消去遞歸產(chǎn)生的迭代程序。算法1.12算法1.11的改進模型procedureMAX3(A,n)integeri,k,n;i←k←nwhilei>1doi←i-1ifA(i)>A(k)thenk←iendifrepeatreturn(k)endMAX3不必死套13條規(guī)則，應具體狀況具體分析procedureGCD1(a,b)//約定a>b//L1:ifb=0thenreturn(a)elset←b;b←amodb;a←t;gotoL1endifendGCD1整理后得：procedureGCD2(a,b)whileb≠0dot←b;b←amodb;a←trepeatreturn(a)endGCD2漸進分析時間困難性漸進階分析的規(guī)則:(最壞狀況)1).賦值,比較,算術運算,邏輯運算,讀寫單個變量(常量)只需1單位時間2).執(zhí)行條件語句ifcthenS1elseS2的時間為TC+max(TS1,TS2).3).選擇語句caseAofa1:s1；a2:s2；...；am:sm須要的時間為max（TS1,TS2,...,TSm）.4).訪問數(shù)組的單個重量或紀錄的單個域須要一個單位時間.5).執(zhí)行for循環(huán)語句的時間=執(zhí)行循環(huán)體時間*循環(huán)次數(shù).6).whilecdos(repeatsuntilc)語句時間=(Tc+Ts)*循環(huán)次數(shù).7).用goto從循環(huán)體內(nèi)跳到循環(huán)體末或循環(huán)后面的語句時,不需額外時間8).過程或函數(shù)調(diào)用語句對非遞歸調(diào)用,依據(jù)調(diào)用層次由里向外用規(guī)則1-7進行分析；對遞歸調(diào)用,可建立關于T(n)的遞歸方程,求解該方程得到T(n).例題1-1

算法1-2:二分查找(假定c是A的最終一元)例題1-1分析:問題規(guī)模為n,元運算執(zhí)行時間設為賦值a,推斷t,加法s,除法d,減法b.最壞狀況Tmax(n)=6a+4t+2s+d+(2a+2s+3t+d)lognfunctionb-search(c){L:=1;U:=n; 2found:=false; 1whilenotfoundandU>=Ldo 3{i:=(L+U)div2; 3 ifc=A[i] 1 thenfound:=true 1 elseifc>A[i] 1 thenL:=i+1 1elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 1}Logn+1算法設計與分析已知不重復且從小到大排列的m個整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對于給定的整數(shù)c,要求找到一個下標i,使得A[i]=c.找不到返回0.例題1-1functionb-search(c,L,U){ifU<Lthen 1b-search:=0 1 else{index:=(L+U)div2; 3element:=A[index]; 2 ifelement=cthen 1