【正文】 bnaTabnaTnT00112233232222)/( )/()/()1( )/()/()/( )/()/()/(( )/()/( ))/()/(( )/()(??設 r= bk /a ， 下面分三種情況計算 。 } } 【 程序 52】 一分為二的分治法 SolutionType DandC(int left， int right) { if (Small(left, right)) return S(left,right)。 【 程序 51】 分治法 SolutionType DandC(ProblemType P) { ProblemType P1， P2， ?， Pk。算法設計與分析 DeSign and Analysis of Algorithms In C++ “十一五”國家級規(guī)劃教材 陳慧南 編著 電子工業(yè)出版社 第 2部分 算法設計策略 第 5章 分治法 分治法的基本思想 求最大最小元 二分搜索 排序問題 選擇問題 斯特拉森矩陣乘法 一般方法 分治法的基本思想 分治法 顧名思義就是分而治之 。 if (Small(P)) return S(P)。 else { int m=Divide(left， right)。 （ 1） 若 r1， 則 所以 （ 2） 若 r=1， 則 所以 （ 3） 若 r1， 則 所以 )r1/(1rm0ii ????)(nT (n ) al o g b??nl o g1m1r bm0ii ??????)nl o gn()nl o g (nT (n ) kal o g b ?? ??)r(1r 1rr m1mm0ii ????? ???)n()b()r(aT ( n ) kmkmm ??? ??? ?例如： (1) T(n)=2T(n/2)+n a=2,b=2,k=1,a=bk 所以 T(n)= ?(nlog(n)) (2) T(n)=4T(n/4)+n2 a=4,b=4,k=2,abk 所以 T(n)= ?(n2) (3) T(n)=16T(n/2)+ n2 a=16,b=2,k=2,abk 所以 T(n)= ?(n4) ???????????kkkkkal o gba )n(ba )nl o gn(ba )n()n(Tb如果如果如果??? 數(shù)據(jù)結構 【 程序 5－ 3】 可排序表類 template class K, class D struct E { //可排序表中元素的類型 operator K( ) const { return key。 template class T class SortableList //可排序表類 { public: SortableList(int mSize) //構造函數(shù) { maxSize=mSize。} //析構函數(shù) ? private: ? T *l 。 } 求最大最小元 問題 在一個元素集合中尋找最大元素和最小元素的問題。 max=min=l[0]。 if(l[i]min) min=l[i]。 max=min=l[0]。 else if(l[i]min) min=l[i]。 if (i==j) max=min=l[i]。 min=l[j]。 if (maxmax1) max=max1。 分治法求解 int SortableListT::BSearch(const Tamp。 從上述查找思想可知，每進行一次關鍵字比較，都將原區(qū)間一分為二，故稱為二分搜索。 if (xl[m]) return BSearch(x,left,m1)。 } 對半搜索 對半搜索 對半搜索是一種二分搜索 。 if (xl[m]) return BSearch(x,left,m1)。 } 二分查找的性能分析 為了分析二分查找的性能 ， 可以用二叉樹來描述二分查找過程 。 于是 ， 可以得到結論：二叉樹第 K層結點的查找次數(shù)各為 k次(根結點為第 1層 )， 而第 k層結點數(shù)最多為 2k1個 。2h2+h2h1+h 合并兩個有序表： 合并算法排序也屬于分治方法。上述每一次的合并過程稱為一趟 〔 Pass），整個排序過程叫二路合并排序。 while (( i=mid )amp。 while (i=mid) temp[k++]=l[i++]。) l[k++] = temp[i++]。若表的數(shù)目為奇數(shù)，就剩下一個表要 “ 輪空 ” ，直接進入下一趟。 MergeSort(mid+1,right)。 ??? ?? ?? 1n )2/n(T2 1n d)n(T??????? 1n )2/(21n )(nTdnT定理 51 設 a,b,c和 k為常數(shù)， T(n)=aT(n/b)+k，T(1)=c，則， ???????????kkkkkal o gba )n(ba )nl o gn(ba )n()n(Tb如果如果如果???使用 遞歸樹 可以形象地看到遞推式的迭代過程。主元左測子序列中所有元素都不大于主元，主元右測子序列中所有元素都不小于主元。 do{ do i++。 if (ij) Swap(i,j)。 } 快速排序算法 【 程序 5－ 12】 快速排序 template class T void SortableListT::QuickSort() { QuickSort(0,n1)。 } } 若快速排序出現(xiàn)最壞的情形 （ 每次能劃分成兩個子區(qū)間 ，但其中一個是空 ） ， 因此 ， 快速排序的最壞時間復雜度為O(n2)。 平均情況時間 )k(An21n ))1kn(A)k(A(n11n)n(A1n0k1n0k?????????????＝－ ))k(A2)1n(n)n(nA 1n0k?????? ))k(A2)1n(n)1n(A1n 2n0k????? －）－）－（ )1n(l o g2xdx2k12 321n2n21n221A 1n2n21n22n3nA n21n21n2nA 1n