【正文】 r (int i=1。i=n/r。i++){ InsertSort(left+(i1)*r,left+i*r1)。 Swap(left+i1, left+(i1)*r+Ceil(r,2)1)。 } int j=Select(Ceil(n/r,2),left,left+(n/r)1,r )。 Swap(left,j)。 j =Partition(left,right)。 if (k==jleft+1) return j。 else if (kjleft+1) return Select(k,left,j1,r)。 else return Select(k(jleft+1),j+1,right,r)。 } 時間分析 以二次取中的中間值 mm為主元，經(jīng)過一趟分劃，左、右兩個子表的大小均至多為： n???n/r?/2? ?r/2? 設(shè) T(n)為當(dāng)表長為 n時執(zhí)行程序 5－ 14所需的時間 。 T(n)由三部分時間組成： T(n)?T(?n/5?)+T(3n/4)+ 用歸納法容易證明 ， T(n)?20， n?1是線性時間的 。 允許重復(fù)元素的選擇算法 由于允許包含相同元素 ， 左子表中除了小于 mm的元素外 ， 還包含與 mm相同值的元素 。 因此 ， 左子表的大小至多可達(dá) n???n/r?/2? ?r/2?+1/2 ??n/r?/2? ?r/2? = n1/2 ??n/r?/2? ?r/2? 容易用歸納法證明對于所有 n?90， T(n)?T(n/9)+T(7n/8)+?72， n?90 斯特拉森矩陣乘法 問題 矩陣相乘 矩陣乘積的 Strassen算法 C=AB=(cij)n n。 求 C=AB即對 n2個元素 cij進(jìn)行計算 ， 故要作 n3次乘法 。相當(dāng)時間內(nèi)沒有人懷疑過是否可以用少于 n3次乘法來完成 。 其實(shí)不然 ， 先以 n=2的矩陣乘積為例 。 對于矩陣 則有： 共需作 8次乘法和 4次加法。 分治法求解大矩陣 C11＝ A11B11+A12B21 C12＝ A11B12+A12B22 C21＝ A21B11+A22B21 C22＝ A21B12+A22B22 ???????????????????222112112221121122211211CCCCBBBBAAAA一個四階方陣可以看作由 4個二階方陣組成 分治法求解大矩陣 C11＝ A11B11+A12B21 C12＝ A11B12+A12B22 C21＝ A21B11+A22B21 C22＝ A21B12+A22B22 一個 n階方陣可以看作由 4個 n/2階的方陣組成，二個 n階方陣的乘積，轉(zhuǎn)化為八個 n/2階方陣的乘積和 4個n/2階方陣的加法。 2n dn)2/n(T82n b)n(T2??????? T(n)=?(n3) 定理 51 設(shè) 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如果如果如果??? 斯特拉森分治法 P=(A11+A22)(B11+B22) Q=(A21+A22)B11 R=A11(B12B22) S=A21(B21B11) T=(A11+A12)B22 U=(A21A11)(B11+B12) V=(A12A22)(B21+B22) C11=P+ST+V C12=R+T C21=Q+S C22=P+RQ+U 2n dn)2/n(T72n b)n(T 2???????T(n)= ?(nlog 7)??(n2. 81) 2*2矩陣的最少乘法次數(shù)是 7。 目前最好的矩陣乘法的時間上界是： O()。 我們研究兩個 n位二進(jìn)制數(shù)相乘的問題。用普通的方法運(yùn)算，將乘數(shù)的每一位（由低位至高位）逐個去乘被乘數(shù)，每乘一次將乘積與原來的積相加，然后乘數(shù)和乘積移位一步，如此下去直至乘數(shù)的最高位運(yùn)算完即得出結(jié)果，這樣運(yùn)算共需 n2 次一位乘一位運(yùn)算，n(n1)次一位加一位運(yùn)算和 n次移位，假設(shè)兩個一位數(shù)相乘，兩個一位數(shù)相加和任何數(shù)移位一步所需運(yùn)算時間均為 O(1)，即均為常數(shù)?？傔\(yùn)算復(fù)雜性為 O（ n2）。 大整數(shù)相乘 現(xiàn)在用分治法來做。設(shè) n=2r,將兩個數(shù)都按位數(shù)劃分成兩段，如圖所示， 這需要三次 n位的加法，一次 n步移位，一次 n/2步移位和四次 n/2位的乘法。 設(shè)用分治法做兩個 n位數(shù)乘法的復(fù)雜性為 T（ n），因加法和移位都是 O（ n），故： 這樣并沒有顯出其優(yōu)越性，我們可以將其進(jìn)一步改進(jìn)，增加一些加法運(yùn)算以減少乘法運(yùn)算。 定理 51 設(shè) 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如果如果如果???減少了乘法運(yùn)算的次數(shù)。 顯然較普通方法更有效。這種思想同樣可以用于十進(jìn)制數(shù)的乘法中。 類似于上述例子，可以看出，一般情況下采用分治解決法劃分子問題時，使各子問題的規(guī)模盡量相等為好。此外，如果是逐層劃分，采用遞歸形式可以使程序簡而明，分析起來也較為方便。 計算： 2348 3825=？ 循環(huán)賽日程表 設(shè)有 n=2k個運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽 。 現(xiàn)要設(shè)計一個滿足以下要求的比賽日程表： （ 1） 每個選手必須與其他 n1個選手各賽一次； （ 2） 每個選手一天只能賽一次； （ 3） 循環(huán)賽一共進(jìn)行 n1天 。 按此要求可將比賽日程表設(shè)計－成有 n行和 n列的一個表 。 在表中第 i行和第 j列處填入第 i個選手在第 j天所遇到的選手 。 4個選手的比賽日程表 日程 選手 一 二 三 四 五 六 七 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 按分治策略 ， 我們可以將所有選手對分為兩組 ， n個選手的比賽日程表就可以通過為 n/2個選手設(shè)計的比賽日程表來決定 。 遞歸地用這種一分為二的策略對選手進(jìn)行分割 ， 直到只剩下 2個選手時 ， 比賽日程表的制定就變得很簡單 。 這時只要讓這 2個選手進(jìn)行比賽就可以了 。 下圖所列出的正方形表是 4個選手的比賽日程表 。 其中左上角與左下角的兩小塊分別為選手 1至選手 2和選手 3至選手 4第 1天的比賽日程 。 據(jù)此 ， 將左上角小塊中的所有數(shù)字按其相對位置抄到右下角 ， 將左下角小塊中的所有數(shù)字按其相對位置抄到右上角 ， 這樣我們就分別安排好了選手 1至選手 2和選手 3至選手 4在后 2天的比賽日程 。 這種安排是符合要求的。 4個選手的比賽日程表 依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。下表是 8個選手的日程安排表。