第1章算法引論剖析

1

算法分析與設(shè)計劉偉(Sunny)E-mail:weiliu_china@163Tel:135748184482主要內(nèi)容介紹第1章 算法引論第2章 遞歸與分治策略第3章 動態(tài)規(guī)劃第4章 貪心算法第5章 回溯法第6章 分支限界法3參考教材4算法無處不在(1)從學校去火車站走哪條線路所需時間最少？(2)如何推斷兩個人是父子關(guān)系（DNA測序）？(3)如何讓一個體積有限的背包中物品的價值最大？(4)如何規(guī)劃可以讓一個省的每個城市之間都有高速馬路連通但總長度最??？(5)一張中國地圖，對每個省進行著色，最少要幾種顏色才能保證相鄰的兩個省顏色不同？……5第1章算法引論1.1 算法與程序1.2 表達算法的抽象機制1.3 描述算法1.4 算法困難性分析本章主要學問點：61.1 算法與程序輸入：有零個或多個外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。是算法用某種程序設(shè)計語言的具體實現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。是滿足下述性質(zhì)的指令序列。算法：程序：71.從機器語言到高級語言的抽象1.2 表達算法的抽象機制高級程序設(shè)計語言的主要好處是：（4）把繁雜瑣碎的事務(wù)交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)建性勞動，提高程序質(zhì)量。（1）高級語言更接近算法語言，易學、易駕馭，一般工程技術(shù)人員只需要幾周時間的培訓就可以勝任程序員的工作；（2）高級語言為程序員供應(yīng)了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工具，使得設(shè)計出來的程序可讀性好，可維護性強，牢靠性高；（3）高級語言不依靠于機器語言，與具體的計算機硬件關(guān)系不大，因而所寫出來的程序可植性好、重用率高；82.抽象數(shù)據(jù)類型1.2 表達算法的抽象機制

抽象數(shù)據(jù)類型(ADT)是算法的一個數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運算。

抽象數(shù)據(jù)類型帶給算法設(shè)計的好處有：

（1）算法頂層設(shè)計與底層實現(xiàn)分別；（2）算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)設(shè)計隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；（3）數(shù)據(jù)模型和該模型上的運算統(tǒng)一在ADT中，便于空間和時間耗費的折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化供應(yīng)有效途徑和工具；（7）算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和困難性的分析。92.抽象數(shù)據(jù)類型1.2 表達算法的抽象機制抽象數(shù)據(jù)類型描述：

ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名實例：線性表ADTList{數(shù)據(jù)對象:D={ai|ai(-ElemSet,i=1,2,...,n,n>=0}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}基本操作：InitList(&L)

DestroyList(&L)

ListInsert(&L,i,e)

ListDelete(&L,i,&e)}ADTList103.偽代碼1.2 表達算法的抽象機制輸入3個數(shù)，打印輸出其中最大的數(shù)。Begin（算法起先）輸入A，B，CIFA>B則A→Max否則B→MaxIFC>Max則C→MaxPrintMaxEnd（算法結(jié)束）114.程序流程圖1.2 表達算法的抽象機制12在本課程中，接受Java語言描述算法。1.Java程序結(jié)構(gòu)1.3 描述算法（1）Java程序的兩種類型：應(yīng)用程序和applet 區(qū)分：應(yīng)用程序的主方法為main，其可在吩咐行中用吩咐 語句java應(yīng)用程序名來執(zhí)行（2）包：Java程序和類可以包(packages)的形式組織管理。（3）import語句：在Java程序中可用import語句加載所需的包。 例如，importjava.io.*;語句加載java.io包。131.3 描述算法2.Java數(shù)據(jù)類型數(shù)據(jù)類型

基本數(shù)據(jù)類型：詳見下頁表1-1

非基本數(shù)據(jù)類型：如

Byte,Integer,Boolean,String等。

Java對兩種數(shù)據(jù)類型的不同處理方式：

對基本數(shù)據(jù)類型：在聲明一個具有基本數(shù)據(jù)類型的變量時，自 動建立該數(shù)據(jù)類型的對象（或稱實例）。如:intk;對非基本數(shù)據(jù)類型：語句Strings;并不建立具有數(shù)據(jù)類型 String的對象，而是建立一個類型String的引用對象， 數(shù)據(jù)類型為String的對象可用下面的new語句建立。s=newString(“Welcome”);Strings=newString(“Welcome”);141.3 描述算法表1-1Java基本數(shù)據(jù)類型類型缺省值分配空間（bits）取值范圍booleanfalse1[true,false]byte08[-128,127]char\u000016[\u0000,\uFFFF]double0.064±4.9*10-324~±1.8*10308float0.032±1.4*10-45~±3.4*1038int032[-2147483648,2147483647]long064±9.2*1017short016[-32768,32767]151.3 描述算法3.方法在Java中，執(zhí)行特定任務(wù)的函數(shù)或過程統(tǒng)稱為方法(methods)

。例如，Java的Math類給出的常見數(shù)學計算的方法如下表所示：方法功能方法功能abs(x)x的絕對值max(x,y)x和y中較大者ceil(x)不小于x的最小整數(shù)min(x,y)x和y中較小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整數(shù)sqrt(x)x的平方根log(x)x的自然對數(shù)tan(x)x的正切161.3 描述算法3.方法

計算表達式 值的自定義方法ab描述如下：

publicstaticintab(inta,intb){return(a+b+Math.abs(a-b))/2;}

（1）方法參數(shù)：Java中全部方法的參數(shù)均為值參數(shù)。上述方法ab中，a和b 是形式參數(shù)（形參），在調(diào)用方法時通過實際參數(shù)（實參）賦值。（2）方法重載：Java允許方法重載，即允許定義有不同簽名的同名方法。 上述方法ab可重載為：

publicstaticdoubleab(doublea,doubleb){return(a+b+Math.abs(a-b))/2.0;}

171.3 描述算法4.異樣Java的異樣供應(yīng)了一種處理錯誤的方法。當程序發(fā)覺一個錯誤，就引發(fā)一個異樣，以便在合適地方捕獲異樣并進行處理。通常用try塊來定義異樣處理。每個異樣處理由一個catch語句組成。publicstaticvoidmain(String[]args){try{f();}catch(exception1){異樣處理;}catch(exception2){異樣處理;}…finally{finally塊;}}181.3 描述算法5.Java的類(4)訪問修飾公有(public)私有(private)保護(protected)Java的類一般由4個部分組成：(1)類名(2)數(shù)據(jù)成員(3)方法191.3 描述算法6.通用方法

下面的方法swap用于交換一維整型數(shù)組a的位置i和位置j處的值。

publicstaticvoidswap(int[]a,inti,intj){inttemp=a[i];a[i]=a[j];a[j]=temp;}

publicstaticvoidswap(Object[]a,inti,intj){objecttemp=a[i];a[i]=a[j];a[j]=temp;}

該方法只適用于整型數(shù)組該方法具有通用性，適用于Object類型及其全部子類以上方法修改如下：201.3 描述算法6.通用方法

（1）Computable接口

publicstaticComputablesum(Computable[]a,intn){if(a.length==0)returnnull;Computablesum=(Computable)a[0].zero();for(inti=0;i<n;i++)sum.increment(a[i]);returnsum;}利用此接口使方法sum()通用化

211.3 描述算法6.通用方法

（2）java.lang.Comparable接口Java的Comparable接口中惟一的方法頭compareTo()用于比較2個元素的大小。例如java.lang.Comparable.xpareTo(y)返回x-y的符號，當x<y時返回負數(shù)，當x=y時返回0，當x>y時返回正數(shù)。（3）Operable接口有些通用方法同時須要Computable接口和Comparable接口的支持。為此可定義Operable接口如下:publicinterfaceOperableextendsComputable,Comparable{}

（4）自定義包裝類由于Java的包裝類如Integer等已定義為final型，因此無法定義其子類，作進一步擴充。為了須要可自定義包裝類。221.3 描述算法7.垃圾收集8.遞歸Java的new運算用于安排所需的內(nèi)存空間。例如，int[]a=newint[500000];安排2000000字節(jié)空間給整型數(shù)組a。頻繁運用new安排空間可能會耗盡內(nèi)存。Java的垃圾收集器會適時掃描內(nèi)存，回收不用的空間（垃圾）給new重新安排。Java允許方法調(diào)用其自身，這類方法稱為遞歸方法。publicstaticintsum(int[]a,intn){if(n==0)return0;elsereturna[n-1]+sum(a,n-1);}

計算一維整型數(shù)組前n個元素之和的遞歸方法

231.4 算法困難性分析算法困難性是算法運行所須要的計算機資源的量，須要時間資源的量稱為時間困難性，須要的空間資源的量稱為空間困難性。這個量應(yīng)當只依靠于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。假如分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示困難性，那么，應(yīng)當有C=F(N,I,A)。一般把時間困難性和空間困難性分開，并分別用T和S來表示，則有：T=T(N,I)和S=S(N,I)。（通常，讓A隱含在困難性函數(shù)名當中）241.4 算法困難性分析最壞狀況下的時間困難性：最好狀況下的時間困難性：平均狀況下的時間困難性：其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達到Tmax(N)的合法輸入；是中使T(N,)達到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。251.4 算法困難性分析算法困難性在漸近意義下的階：漸近意義下的記號：O、Ω、θ、o

設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O的定義：假如存在正的常數(shù)C和自然數(shù)N0，使得當NN0時有f(N)Cg(N)，則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。依據(jù)O的定義，簡潔證明它有如下運算規(guī)則：