算法設(shè)計與分析-10算法設(shè)計-分治法

算法設(shè)計與分析——分治法2023/2/41算法設(shè)計與分析演示稿紀(jì)玉波制作(C)分治法（divide-and-conquer）

分治策略是一種用得最多的一種有效方法，它的基本思想將問題分解成若干子問題，然后求解子問題。子問題較原問題無疑是要容易些，由此得出原問題的解，就是所謂的“分而治之”的意思。分治策略還可以遞歸進(jìn)行，即子問題仍然可以用分治策略來處理，最后的問題是非常基本而簡單。下面舉幾個例子。2023/2/42算法設(shè)計與分析演示稿紀(jì)玉波制作(C)1.合并排序合并算法排序即屬于分治方法。合并（Merge）就是將兩個或多個有序表合并成一個有序表，例如下圖所示的兩個有序表經(jīng)合并運(yùn)算后得到一個有序表。我們在此只用到兩個有序表的合并，稱為二路并〔Two-waymerge）。2023/2/43算法設(shè)計與分析演示稿紀(jì)玉波制作(C)合并排序（Mergesort）就是利用這種合并過程進(jìn)行排序，即先將n個數(shù)據(jù)看成n個長度為l的表，將相鄰的表成對合并，得到長度為2的n/2個有序表；進(jìn)一步再將相鄰表成對會并，得到長度為4的n/4個有序表；……；如此重復(fù)做下去，直至所有數(shù)據(jù)均合并到一個長度為n的有序表為止，即完成排序。上述每一次的合并過程稱為一趟〔Pass），整個排序過程叫二路合并排序。下圖是二路合并排序過程的一個例子。2023/2/44算法設(shè)計與分析演示稿紀(jì)玉波制作(C)[7][15][13][10][4][20][19][8][7][15][10][13][4][20][8][19][7][10][13][15][4][8][19][20][4][7][8][10][13][15][19][20]2023/2/45算法設(shè)計與分析演示稿紀(jì)玉波制作(C)對于二路合并，如果數(shù)據(jù)個數(shù)n是2的整數(shù)次方，則所需的趟數(shù)為logn，例如n=8，logn=3，故共需三趟合并過程。如果n不是2的整數(shù)次方，則在每趟合并時表的數(shù)目不一定總是偶數(shù)個。若表的數(shù)目為奇數(shù)，就剩下一個表要“輪空”，直接進(jìn)入下一趟。這樣，下一趟合并時此表的長度與其它的表將不相同，因此我們設(shè)計的合并過程，并不要求待合并的兩個表長度必須相同。二路合并排序的時間復(fù)雜性為O(nlogn），與堆排序及快速排序平均情況的時間復(fù)雜性同樣數(shù)量級。2023/2/46算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2．在互不相同的n個數(shù){x1,x2,…,xn}中，找出最大和最小的數(shù)。若用普通的算法為：begin

xmax←x1;xmin←x1fori=2tondobeginifxmax<xithenxmax←xi

ifxmin>xithenxmin←xi

endend2023/2/47算法設(shè)計與分析演示稿紀(jì)玉波制作(C)此算法的比較次數(shù)為2(n-1)=2n-2，顯然不是最優(yōu)的。如果用分治法解決法，寫出遞歸過程為：過程MAXMIN(x1,x2,…,xn)（1）如n=1,則xmax←x1,xmin←x1（2）如n=2,則比較x1與x2，令大者為xmax，小者為xmin（3）如n>2,則調(diào)用MAXMIN(x1,…,x[n/2])調(diào)用MAXMIN(x[n/2]+1,…,xn)比較兩個最大值，令大者為xmax比較兩個最小值，令小者為xmin。2023/2/48算法設(shè)計與分析演示稿紀(jì)玉波制作(C)下面分析用此算法的比較次數(shù)。設(shè)T（n）表示元素個數(shù)為n時的總比較次數(shù)，則T（1）=0，T（2）=1（n>2）為方便起見，設(shè)n=2r，問題的逐層劃分如下表所示：可以證明

T(n)=3n/2-2此值恰好等于問題的下界，故這是最優(yōu)算法。2023/2/49算法設(shè)計與分析演示稿紀(jì)玉波制作(C)其實，此問題也不一定要用遞歸算法來解決，可將數(shù)據(jù)分成兩個一組的n/2組，第一組比較一數(shù)，令大的為xmax，小的為xmin，以后各組比較三次，先兩個數(shù)據(jù)比較，其中大者再與xmax比，小者再與xmin比，總比較次數(shù)也恰為。2023/2/410算法設(shè)計與分析演示稿紀(jì)玉波制作(C)3.兩數(shù)相乘我們研究兩個n位二進(jìn)制數(shù)相乘的問題。假設(shè)兩個一位數(shù)相乘，兩個一位數(shù)相加和任何數(shù)移位一步所需運(yùn)算時間均為O(1)，即均為常數(shù)。用普通的方法運(yùn)算，將乘數(shù)的每一位（由低位至高位）逐個去乘被乘數(shù)，每乘一次將成積與原來的積相加，然后乘數(shù)和乘積移位一步，如此下去直至乘數(shù)的最高位運(yùn)算完即得出結(jié)果，這樣運(yùn)算共需n2次一位乘一位運(yùn)算，n(n-1)次一位加一位運(yùn)算和n次移位，總運(yùn)算復(fù)雜性為O（n2）。2023/2/411算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/412算法設(shè)計與分析演示稿紀(jì)玉波制作(C)現(xiàn)在用分治法來做。設(shè)n=2r,將兩個數(shù)都按位數(shù)劃分成兩段，如圖所示，2023/2/413算法設(shè)計與分析演示稿紀(jì)玉波制作(C)這需要三次n位的加法，一次n步移位，一次n/2步移位和四次n/2位的乘法。2023/2/414算法設(shè)計與分析演示稿紀(jì)玉波制作(C)設(shè)用分治法做兩個n位數(shù)乘法的復(fù)雜性為T（n），因加法和移位都是O（n），故2023/2/415算法設(shè)計與分析演示稿紀(jì)玉波制作(C)這樣并沒有顯出其優(yōu)越性，我們可以將其進(jìn)一步改進(jìn)，增加一些加法運(yùn)算以減少乘法運(yùn)算。2023/2/416算法設(shè)計與分析演示稿紀(jì)玉波制作(C)上式的4次乘法可以由3次完成。2023/2/417算法設(shè)計與分析演示稿紀(jì)玉波制作(C)增加的加減運(yùn)算只影響K1值，卻使乘法減為三次，為分析簡單可近似認(rèn)為K2和K1相等,令K=K1=K2，則2023/2/418算法設(shè)計與分析演示稿紀(jì)玉波制作(C)2023/2/419算法設(shè)計與分析演示稿紀(jì)玉波制作(C)顯然較普通方法更有效。這種思想同樣可以用于十進(jìn)制數(shù)的乘法中。類似于上述兩個例子，可以看出，一般情況下采用分治解決法劃分子問題時，使各子問題的規(guī)模盡量相等為好。此外，如果是逐層劃分，采用遞歸形式可以使程序簡而明，分析起來也較為方便。2023/2/420算法設(shè)計與分析演示稿紀(jì)玉波制作(C)4.循環(huán)賽日程表分治法不僅可以用來設(shè)計算法,而且在其他方面也有廣泛應(yīng)用。例如可以用分治思想來設(shè)計電路、構(gòu)造數(shù)學(xué)證明等?，F(xiàn)舉一例加以說明。設(shè)有n=2k個運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽。現(xiàn)要設(shè)計一個滿足以下要求的比賽日程表：（1）每個選手必須與其他n-1個選手各賽一次；（2）每個選手一天只能賽一次；（3）循環(huán)賽一共進(jìn)行n-1天。按此要求可將比賽日程表設(shè)計－成有n行和n-l列的一個表。在表中第i行和第j列處填入第i個選手在第j無所遇到的選手。2023/2/421算法設(shè)計與分析演示稿紀(jì)玉波制作(C)按分治策略，我們可以將所有選手對分為兩組，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進(jìn)行比賽就可以了。下圖所列出的正方形表是4個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手2和選手3至選手4第1天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對位置抄到右下角，將左下角小塊中的所有數(shù)字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手2和選手3至選手4在后2天的比賽日程。這種安排是符合要求的。2023/2/422算法設(shè)計與分析演示稿紀(jì)玉波制作(C)4個選手的比賽日程表2023/2/423算法設(shè)計與分析演示稿紀(jì)玉波制作(C)依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。下表是8個選手的日程安排表。2023/2/424算法設(shè)計與分析演示稿紀(jì)玉波制作(C)5.矩陣乘積的Strassen算法

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

c11=P+S-T+Vc12=R+Tc21=Q+Sc22=P+R-Q+U乘法次數(shù)