分治法：計算方向：自頂向下；分為3個步驟：divide:整個問題劃分為多個子問題；conquer求解每個子問題combine合并子問題的解，形成原問題的解設(shè)輸入大小為n，T(n)為時間復(fù)雜性，當(dāng)n<c,T(n)=(1);總之：(1) ifn<cT(n)=aT(n/b)+D(n)+C(n).1同階。定義：e(f(n))={g(n)|ЭC1,C2>0,n0;當(dāng)n>=n0,C1f(n)<=g(n)<=C2f(n)}稱為與f(n)同階。例題：證明,其中證:由于，，所以。2、高階。定義：Ω（f（n））={g(n)|ЭC1,C2>0,n0;當(dāng)n>=n0,0<=g(n)<=C2f(n)}稱為比f(n)高階。二分查找：BinarySearch(max,min,des)mid-<(max+min)/2while(min<=max)mid=(min+max)/2ifmid=desthenreturnmidelseifmid>desthenmax=mid-1elsemin=mid+1；returnmaxO(logn)歸并算法（mergesort）：輸入：Ap,r：欲排序數(shù)據(jù)在數(shù)組A中。輸出：Ap,r：排序后的數(shù)據(jù)。方法： Merge-Sort(A,p,r)ifp<rthenq(p+r)/2Merge-Sort(A,p,q)Merge-Sort(A,q+1,r)Merge(A,p,q,r)。*Merge算法十分簡單，需要O(n)次比較。*若要排序存儲在數(shù)組A的n個數(shù),只需調(diào)用Merge-Sort(A,1,n)。2.Merge-Sort的分析 ·Ifn=1,T(n)=(1) ·Divide階段的時間復(fù)雜性:D(n)=(1) ·Conquer階段的時間復(fù)雜性:2T() ·Combine階段的時間復(fù)雜性:C(n)=(n)(1) ifn=1·T(n)=2T(n/2)+(n)+(1) ifn>1 ·使用循環(huán)展開法求解T(n)=(n)。快速排序算法(Quick-Sort):描述：有數(shù)組A[p….r]q=(p+r)/2;1).divide:把數(shù)組A[p…r]劃分為兩個非空數(shù)組A1[p…q],A2[q+1,r];使得A1中的每個數(shù)都小于A2中的；2).conquer:遞歸調(diào)用排序算法排序A1，A2；3).combine:將兩個已經(jīng)排好序的算法合并算法詳細(xì):Quick_sort(A[],p,r)Ifp<rThenq=partition(A[],p,r)Quick_sort(A[],p,q)Quick_sort(a[],q+1,r);Partition算法:Partition(a[],p,r)X=a[p]i=p-1;j=r+1;repaeatj--untila[j]<=x;repeati++untila[i]>=x;ifi<jthenexchangea[i]a[j]elsereturnj;將數(shù)組A有序排序,小的數(shù)放在前面A[i]>=X>=A[j];最壞時間復(fù)雜性:(n2)劃分平衡時間復(fù)雜性:(nlgn)動態(tài)規(guī)劃技術(shù)(DynamicProgramming):適用：當(dāng)一個優(yōu)化問題可以分為多個子問題，子問題的解被重復(fù)使用。滿足條件：1.問題據(jù)有優(yōu)化子結(jié)構(gòu)(Optimalsubstructure)2.有重疊子問題(Overlappingsub-problems)優(yōu)化結(jié)構(gòu)：如果一個問題的優(yōu)化解包含了他的子問題的優(yōu)化解，則稱該問題據(jù)具有優(yōu)化子結(jié)構(gòu)；特點：求解每個子問題僅一次，并保存結(jié)果，以后用到時直接存取，不重復(fù)計算，節(jié)省時間。計算方向：自底向上步驟：分析優(yōu)化解的結(jié)構(gòu)遞歸定義最優(yōu)解的代價；自底向上的計算優(yōu)化解的代價保存，并獲取構(gòu)造最優(yōu)解的信息；根據(jù)構(gòu)造最優(yōu)解的信息構(gòu)造優(yōu)化解；矩陣鏈乘積(Matrix-chainMultiplication)(~)優(yōu)化解的代價方程：假設(shè)：m[I,j]=計算Ai-j的最小乘法數(shù)=0；m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj,m[i,j]=0ifi=jminik<j{m[i,k]+m[k+1,j]+pI-1pkpj}ifi<j時間復(fù)雜性T(n)=0(n3)空間復(fù)雜性S(n)=0(n2)最長公共子序列問題步驟：1.問題定義2.建立求解LCS長度的遞歸方程3.LSC長度的計算4.構(gòu)造最優(yōu)解0-1背包最優(yōu)子結(jié)構(gòu)：問題分析：令f(i,j)表示在前i(0≤i<n)個物品中能夠裝入容量為j(0≤j≤W)的背包中的物品的最大價值，則可以得到如下的動態(tài)規(guī)劃函數(shù): f[i,j]=0(i=0ORj=0)f[i,j]=f[i-1,j]j<wi① f[i,j]=max{f[i-1,j],f[i-1,j-wi]+vi}j>wi②偽代碼：f[0,j]=0Fori=1tonForj=0toWf[i,j]=max{f[i-1,j],f[i-1,j-wi]+vi}returnF[n,W]問題的解為f[n,W]Geedy算法基本思想：1.求解最優(yōu)化問題的算法包含一些列步驟2.每一步都有一組選擇3.做出在當(dāng)前看來最好的選擇；4.希望做出局部優(yōu)化選擇達(dá)到全局優(yōu)化選擇*Greedy算法不一定總產(chǎn)生優(yōu)化解Greedy算法產(chǎn)生優(yōu)化解的條件：1.問題具有優(yōu)化子結(jié)構(gòu)2.貪心選擇性貪心選擇性：若一個優(yōu)化問題的全局優(yōu)化解可以通過局部優(yōu)化解選擇得到。*Greedy算法與動態(tài)規(guī)劃方法的不同動態(tài)規(guī)劃：每一步作一個選擇—依賴于子問題的解。Greedy方法:每一步作一個選擇—不依賴于子問題的解。*一個問題是否具有Greedy選擇性需要證明。活動任務(wù)安排GreedyAction(s,f，n)//s[1..n]、f[1..n]分別代表n項活動的起始時間和結(jié)束時間,并且滿足f[1]≤f[2]≤…≤f[n]j:=1,solution:={1}//解向量初始化forifrom2tondoifsi≥fjthensolution:=solution∪{j};//將j加入解中j:=i;end{if}end{for}return(solution);end{GreedyAction}時間復(fù)雜度：T(n)=O(n)(排序時)T(n)=O(nlogn)(未排序時)3.優(yōu)化子結(jié)構(gòu)定義2若一個優(yōu)化問題的優(yōu)化解包括它的子問題的優(yōu)化解，則稱其具有優(yōu)化子結(jié)構(gòu)。4.與動態(tài)規(guī)劃方法的比較·動態(tài)規(guī)劃方法可用的條件優(yōu)化子結(jié)構(gòu)子問題相交性子問題空間小·Greedy方法可用的條件優(yōu)化子結(jié)構(gòu)Greedy選擇性*可用Greedy方法時，動態(tài)規(guī)劃方法可能不適用。*可用動態(tài)規(guī)劃方法時，Greedy方法可能不適用。哈夫曼算法：基本思想：循環(huán)的選擇具有最低頻率的兩個節(jié)點。生成一顆子樹。直至生成一棵樹；算法：Huffman(C，F(xiàn))nC;QC;FORi1Ton-1DozAllocate-Node();xleft[z]Extract-MIN(Q);yright[E]Extract-MIN(Q);f(z)f(x)+f(y);insert(Q,z);ReturnExtract-MIN(Q).時間復(fù)雜度：T(n)=O(n)+O(nlogn)擬陣(Matriod)；Matroid是一個序?qū)=(S,I)，滿足：S是一個有限非空集合;I是非空的S子集的集族，I中的子集合稱為S的獨立子集合;遺傳性:如果BI，AB，則AI；交換性：如果AI，BI，A<B，則xB-A使得A{x}I。Matroid的性質(zhì).1設(shè)M=(S，I)是一個Matroid，AI。xA稱為A的一個extension如果A{x}I。2設(shè)M=(S，I)是一個Matroid，AI（A稱為M的獨立子集合）。如果A沒有extension，則稱A為最大獨立子集合。3一個Matroid的所有最大獨立子集合都具有相同大小設(shè)M=(S，I)是一個Matroid。如果存在一個權(quán)函數(shù)W，使得xS,W(x)是一個正數(shù)，則稱M是加權(quán)Matroid平攤分析平攤分析的基本思想在平攤分析中執(zhí)行一系列數(shù)據(jù)結(jié)構(gòu)所需要的時間是通過對執(zhí)行的所有操作求平均值而得出的，即使單一操作具有較大的代價，通過對所有求平均后平均代價還是很小的；平攤分析的方法：聚集方法，勢能方法，會計方法；聚集方法：首先證明n個操作序列在最壞情況下的總時間T(n)在最壞情況下每個操作的平均代價就是T(n)/n*聚集方法為每個操作都賦予相同的平攤代價，即使序列中存在不同類型操作時也一樣。會計方法：·首先定義每個操作的平攤代價然后計算總的平攤代價·執(zhí)行不同的操作需要付出不同的費用·某些操作的費用可能比它們的實際代價多或少·一個操作的平攤代價可看作為兩部分：其實際代價與存款*會計方法不同于聚集方法，不同操作具有不同的平攤代價。勢能方法:勢能方法不是將已預(yù)付的費用作為存儲在數(shù)據(jù)結(jié)構(gòu)特定對象中的存款來表示，而是表示成一種“勢能”，或“勢”，它在需要時可釋放出來以支付后面操作的代價。·勢是與整個數(shù)據(jù)結(jié)構(gòu)而不是其中的個別對象發(fā)生聯(lián)系的。*每個操作的平攤代價為其實際代價加上由于該操作所增加的勢。第七章近似算法求解NP-完全問題的兩種方法：·如果問題的輸入很小，可以使用指數(shù)級算法圓滿地解決該問題·使用多項式算法求解問題的近似優(yōu)化解點覆蓋：輸入輸入：無向圖G=（V，E）輸出：，滿足(1).，、或{u,v}V’(2).是滿足條件(1)的最小集合APPROX-Vertex-Cover(G)1.2.3.whileDO4.任取5.E’←E’-{(u’,v’)|u’=u或v’=v}RoturnC時間復(fù)雜性T(G)=O(|E|).第八章用回溯法解題的三個步驟：針對所給的問題，定義問題的解空間確定易于搜索的解空間；以深度優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜