分治法：計算方向：自頂向下；分為3個步驟：divide:整個問題劃分為多個子問題；conquer求解每個子問題combine合并子問題的解，形成原問題的解設輸入大小為n，T(n)為時間復雜性，當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;當n>=n0,C1f(n)<=g(n)<=C2f(n)}稱為與f(n)同階。例題：證明,其中證:由于，，所以。2、高階。定義：Ω（f（n））={g(n)|ЭC1,C2>0,n0;當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：欲排序數據在數組A中。輸出：Ap,r：排序后的數據。方法： 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)次比較。*若要排序存儲在數組A的n個數,只需調用Merge-Sort(A,1,n)。2.Merge-Sort的分析 ·Ifn=1,T(n)=(1) ·Divide階段的時間復雜性:D(n)=(1) ·Conquer階段的時間復雜性:2T() ·Combine階段的時間復雜性:C(n)=(n)(1) ifn=1·T(n)=2T(n/2)+(n)+(1) ifn>1 ·使用循環展開法求解T(n)=(n)。快速排序算法(Quick-Sort):描述：有數組A[p….r]q=(p+r)/2;1).divide:把數組A[p…r]劃分為兩個非空數組A1[p…q],A2[q+1,r];使得A1中的每個數都小于A2中的；2).conquer:遞歸調用排序算法排序A1，A2；3).combine:將兩個已經排好序的算法合并算法詳細: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;將數組A有序排序,小的數放在前面A[i]>=X>=A[j];最壞時間復雜性:(n2)劃分平衡時間復雜性:(nlgn)動態規劃技術(DynamicProgramming):適用：當一個優化問題可以分為多個子問題，子問題的解被重復使用。滿足條件：1.問題據有優化子結構(Optimalsubstructure)2.有重疊子問題(Overlappingsub-problems)優化結構：如果一個問題的優化解包含了他的子問題的優化解，則稱該問題據具有優化子結構；特點：求解每個子問題僅一次，并保存結果，以后用到時直接存取，不重復計算，節省時間。計算方向：自底向上步驟：分析優化解的結構遞歸定義最優解的代價；自底向上的計算優化解的代價保存，并獲取構造最優解的信息；根據構造最優解的信息構造優化解；矩陣鏈乘積(Matrix-chainMultiplication)(~)優化解的代價方程：假設：m[I,j]=計算Ai-j的最小乘法數=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時間復雜性T(n)=0(n3)空間復雜性S(n)=0(n2)最長公共子序列問題步驟：1.問題定義2.建立求解LCS長度的遞歸方程3.LSC長度的計算4.構造最優解0-1背包最優子結構：問題分析：令f(i,j)表示在前i(0≤i<n)個物品中能夠裝入容量為j(0≤j≤W)的背包中的物品的最大價值，則可以得到如下的動態規劃函數: 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.求解最優化問題的算法包含一些列步驟2.每一步都有一組選擇3.做出在當前看來最好的選擇；4.希望做出局部優化選擇達到全局優化選擇*Greedy算法不一定總產生優化解Greedy算法產生優化解的條件：1.問題具有優化子結構2.貪心選擇性貪心選擇性：若一個優化問題的全局優化解可以通過局部優化解選擇得到。*Greedy算法與動態規劃方法的不同動態規劃：每一步作一個選擇—依賴于子問題的解。Greedy方法:每一步作一個選擇—不依賴于子問題的解。*一個問題是否具有Greedy選擇性需要證明。活動任務安排GreedyAction(s,f，n)//s[1..n]、f[1..n]分別代表n項活動的起始時間和結束時間,并且滿足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}時間復雜度：T(n)=O(n)(排序時)T(n)=O(nlogn)(未排序時)3.優化子結構定義2若一個優化問題的優化解包括它的子問題的優化解，則稱其具有優化子結構。4.與動態規劃方法的比較·動態規劃方法可用的條件優化子結構子問題相交性子問題空間小·Greedy方法可用的條件優化子結構Greedy選擇性*可用Greedy方法時，動態規劃方法可能不適用。*可用動態規劃方法時，Greedy方法可能不適用。哈夫曼算法：基本思想：循環的選擇具有最低頻率的兩個節點。生成一顆子樹。直至生成一棵樹；算法：Huffman(C，F)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).時間復雜度：T(n)=O(n)+O(nlogn)擬陣(Matriod)；Matroid是一個序對M=(S,I)，滿足：S是一個有限非空集合;I是非空的S子集的集族，I中的子集合稱為S的獨立子集合;遺傳性:如果BI，AB，則AI；交換性：如果AI，BI，A<B，則xB-A使得A{x}I。Matroid的性質.1設M=(S，I)是一個Matroid，AI。xA稱為A的一個extension如果A{x}I。2設M=(S，I)是一個Matroid，AI（A稱為M的獨立子集合）。如果A沒有extension，則稱A為最大獨立子集合。3一個Matroid的所有最大獨立子集合都具有相同大小設M=(S，I)是一個Matroid。如果存在一個權函數W，使得xS,W(x)是一個正數，則稱M是加權Matroid平攤分析平攤分析的基本思想在平攤分析中執行一系列數據結構所需要的時間是通過對執行的所有操作求平均值而得出的，即使單一操作具有較大的代價，通過對所有求平均后平均代價還是很小的；平攤分析的方法：聚集方法，勢能方法，會計方法；聚集方法：首先證明n個操作序列在最壞情況下的總時間T(n)在最壞情況下每個操作的平均代價就是T(n)/n*聚集方法為每個操作都賦予相同的平攤代價，即使序列中存在不同類型操作時也一樣。會計方法：·首先定義每個操作的平攤代價然后計算總的平攤代價·執行不同的操作需要付出不同的費用·某些操作的費用可能比它們的實際代價多或少·一個操作的平攤代價可看作為兩部分：其實際代價與存款*會計方法不同于聚集方法，不同操作具有不同的平攤代價。勢能方法:勢能方法不是將已預付的費用作為存儲在數據結構特定對象中的存款來表示，而是表示成一種“勢能”，或“勢”，它在需要時可釋放出來以支付后面操作的代價。·勢是與整個數據結構而不是其中的個別對象發生聯系的。*每個操作的平攤代價為其實際代價加上由于該操作所增加的勢。第七章近似算法求解NP-完全問題的兩種方法：·如果問題的輸入很小，可以使用指數級算法圓滿地解決該問題·使用多項式算法求解問題的近似優化解點覆蓋：輸入輸入：無向圖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時間復雜性T(G)=O(|E|).第八章用回溯法解題的三個步驟：針對所給的問題，定義問題的解空間確定易于搜索的解空間；以深度優先的方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜