算法設(shè)計(jì)與分析_10算法設(shè)計(jì)-分治法

1、2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析分治法分治法2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)2分治法（divide-and-conquer） 分治策略是一種用得最多的一種有效方法，它的基本思想將問題分解成若干子問題，然后求解子問題。子問題較原問題無疑是要容易些，由此得出原問題的解，就是所謂的“分而治之”的意思。分治策略還可以遞歸進(jìn)行，即子問題仍然可以用分治策略來處理，最后的問題是非?；径唵?。下面舉幾個(gè)例子。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)31.合并排序合并算法排序即屬于分治方法。合并（Merge）就是將兩

2、個(gè)或多個(gè)有序表合并成一個(gè)有序表，例如下圖所示的兩個(gè)有序表經(jīng)合并運(yùn)算后得到一個(gè)有序表。我們在此只用到兩個(gè)有序表的合并，稱為二路并Two-way merge）。A7101315 B481920C47810131519202022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)4合并排序（Merge sort）就是利用這種合并過程進(jìn)行排序，即先將n個(gè)數(shù)據(jù)看成n個(gè)長度為l的表，將相鄰的表成對合并，得到長度為2的n/2個(gè)有序表；進(jìn)一步再將相鄰表成對會并，得到長度為4的n/4個(gè)有序表；如此重復(fù)做下去，直至所有數(shù)據(jù)均合并到一個(gè)長度為n的有序表為止，即完成排序。上述每一次的合并過程稱為一趟Pass），整個(gè)排序

3、過程叫二路合并排序。下圖是二路合并排序過程的一個(gè)例子。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)57 15 13 10 4 20 19 87 15 10 13 4 20 8 19 7 10 13 15 4 8 19 20 4 7 8 10 13 15 19 202022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)6 對于二路合并，如果數(shù)據(jù)個(gè)數(shù)n是2的整數(shù)次方，則所需的趟數(shù)為logn，例如n=8，logn=3，故共需三趟合并過程。如果n不是2的整數(shù)次方，則在每趟合并時(shí)表的數(shù)目不一定總是偶數(shù)個(gè)。若表的數(shù)目為奇數(shù)，就剩下一個(gè)表要“輪空”，直接進(jìn)入下一趟。這樣，下一趟合并時(shí)此表的長度

4、與其它的表將不相同，因此我們設(shè)計(jì)的合并過程，并不要求待合并的兩個(gè)表長度必須相同。 二路合并排序的時(shí)間復(fù)雜性為O(nlogn），與堆排序及快速排序平均情況的時(shí)間復(fù)雜性同樣數(shù)量級。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)72在互不相同的n個(gè)數(shù)x1, x2, xn中，找出最大和最小的數(shù)。若用普通的算法為：begin xmaxx1;xminx1 for i=2 to n do begin if xmaxxi then xminxi endendend2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)8 此算法的比較次數(shù)為2(n-1)=2n-2，顯然不是最優(yōu)的。如果用分治法解決法，

5、寫出遞歸過程為：過程MAXMIN(x1, x2, xn) （1）如n=1,則xmaxx1, xminx1 （2）如n=2,則比較x1與x2，令大者為xmax，小者為xmin （3）如n2,則調(diào)用MAXMIN(x1, , xn/2)調(diào)用MAXMIN(xn/2+1, xn)比較兩個(gè)最大值，令大者為xmax比較兩個(gè)最小值，令小者為xmin。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)9下面分析用此算法的比較次數(shù)。設(shè)T（n）表示元素個(gè)數(shù)為n時(shí)的總比較次數(shù)，則 T（1）=0，T（2）=12)2/()2/()(nTnTnT（n2）為方便起見，設(shè)n=2r，問題的逐層劃分如下表所示：可以證明 T(

6、n)=3n/2-2此值恰好等于問題的下界，故這是最優(yōu)算法。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)10其實(shí)，此問題也不一定要用遞歸算法來解決，可將數(shù)據(jù)分成兩個(gè)一組的n/2組，第一組比較一數(shù)，令大的為xmax，小的為xmin，以后各組比較三次，先兩個(gè)數(shù)據(jù)比較，其中大者再與xmax比，小者再與xmin比，總比較次數(shù)也恰為 。)223(n2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)113. 兩數(shù)相乘 我們研究兩個(gè)n位二進(jìn)制數(shù)相乘的問題。假設(shè)兩個(gè)一位數(shù)相乘，兩個(gè)一位數(shù)相加和任何數(shù)移位一步所需運(yùn)算時(shí)間均為O(1)，即均為常數(shù)。用普通的方法運(yùn)算，將乘數(shù)的每一位（由低位至高位）逐

7、個(gè)去乘被乘數(shù)，每乘一次將成積與原來的積相加，然后乘數(shù)和乘積移位一步，如此下去直至乘數(shù)的最高位運(yùn)算完即得出結(jié)果，這樣運(yùn)算共需n2 次一位乘一位運(yùn)算，n(n-1)次一位加一位運(yùn)算和n次移位，總運(yùn)算復(fù)雜性為O（n2）。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)122022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)13現(xiàn)在用分治法來做。設(shè)n=2r,將兩個(gè)數(shù)都按位數(shù)劃分成兩段，如圖所示，2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)14因 dcybaxnn2222則 bdbcadcayxnn22)(2這需要三次n位的加法，一次n步移位，一次n/2步移位和四次n/2位的乘法。

8、2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)15設(shè)用分治法做兩個(gè)n位數(shù)乘法的復(fù)雜性為T（n），因加法和移位都是O（n），故 21) 1 ()2(4)(KTnKnTnT下面用試猜法求 T（n） 。假定 nnnT2)(其中,是待定常數(shù)?，F(xiàn)將次假定代入上式，得到 nKnnnn122)2()2(4 4)2(12nKn2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)16按等式兩邊對應(yīng)項(xiàng)相等可解出 0,1K，則 nKnnT12)(再代入2) 1 (KT中，得到21KK ，即)(21KK 故 )()()(21221nOnKnKKnT這樣并沒有顯出其優(yōu)越性，我們可以將其進(jìn)一步改進(jìn)，增加一些

9、加法運(yùn)算以減少乘法運(yùn)算。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)17由于 bdbcadcayxnn22)(2令 )(,dcbawbdvacu則 vuwbcad)(上式的4次乘法可以由3次完成。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)18增加的加減運(yùn)算只影響K1值，卻使乘法減為三次，為分析簡單可近似認(rèn)為K2和K1相等,令K= K1= K2，則 KTn KnnTnT) 1 () 1()2(3)(為解此遞歸方程，將問題的逐層劃分列表如下：問題的個(gè)數(shù)13323r-23r-12r問題的大小2r2r-12r-22221每個(gè)問題的運(yùn)算時(shí)間K2rK2r-1K2r-2K22K2K

10、2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)19故總的運(yùn)算時(shí)間ririiiriyiKKnT0023223)( riirK0)23(2 ) 1)23(21)2/3(1)2/3(2111rrrrKK rrrrKKKK22332311因59. 13log3log)2()2(32nnrrrr故)(23)(59. 159. 1nOKnKnnT2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)20 顯然較普通方法更有效。這種思想同樣可以用于十進(jìn)制數(shù)的乘法中。 類似于上述兩個(gè)例子，可以看出，一般情況下采用分治解決法劃分子問題時(shí)，使各子問題的規(guī)模盡量相等為好。此外，如果是逐層劃分，采用遞歸形

11、式可以使程序簡而明，分析起來也較為方便。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)21 4. 4.循環(huán)賽日程表循環(huán)賽日程表 分治法不僅可以用來設(shè)計(jì)算法,而且在其他方面也有廣泛應(yīng)用。例如可以用分治思想來設(shè)計(jì)電路、構(gòu)造數(shù)學(xué)證明等?，F(xiàn)舉一例加以說明。 設(shè)有n=2k個(gè)運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： （1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次； （2）每個(gè)選手一天只能賽一次； （3）循環(huán)賽一共進(jìn)行n-1天。 按此要求可將比賽日程表設(shè)計(jì)成有n行和n-l列的一個(gè)表。在表中第i行和第j列處填入第i個(gè)選手在第j無所遇到的選手。2022-2-20算法設(shè)計(jì)與分析演示稿

12、 紀(jì)玉波制作(C)22 按分治策略，我們可以將所有選手對分為兩組，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。 下圖所列出的正方形表是4個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手2和選手3至選手4第1天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對位置抄到右下角，將左下角小塊中的所有數(shù)字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手2和選手3至選手4在后2天的比賽日程。這種安排是符合要求的。2022-2

13、-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)2312213 44 334431 22 14個(gè)選手的比賽日程表2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)24 依此思想容易將這個(gè)比賽日程表推廣到具有任意多個(gè)選手的情形。下表是8個(gè)選手的日程安排表。12342 3 41 4 34 1 23 2 15 6 7 86 5 8 77 8 5 68 7 6 556786 7 85 8 78 5 67 6 51 2 3 42 1 4 33 4 1 24 3 2 12022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)25 5. 5. 矩陣乘積的矩陣乘積的StrassenStrassen算法算法

14、C=AB=(cij)nn。nkkjikijnjibac1, 2 , 1, 求C=AB即對n2個(gè)元素cij進(jìn)行計(jì)算，故要作n3次乘法。相當(dāng)時(shí)間內(nèi)沒有人懷疑過是否可以用少于n3次乘法來完成。其實(shí)不然，先以n=2的矩陣乘積為例。 對于矩陣2221121122211211,bbbbBaaaaA2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)26則有2221121122211211bbbbaaaaABC22221221212211212212121121121111babababababababa22211211cccc共需作8次乘法。2022-2-20算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)27Strassen提出的算法如下： 令 P=(a11+a22)(b11+b22) Q=(a21+a22)b11 R=a11(b12-b22) S=a22(b21-b11) T=(a11+a12)b22 U=(a21-a11)(b11+b12) V=(