分治法大整數(shù)乘法課件.ppt

1、第 3 章 分治法,概述：算法概要、算法效率 合并排序 快速排序 折半查找 大整數(shù)乘法 Strassen 矩陣乘法 分治法解凸包,概述,概述（算法概要、算法效率） 分治法是著名的通用算法設(shè)計技術(shù)，很多有效的算法是它的特殊實(shí)現(xiàn)。 算法思想：解決復(fù)雜問題時常從大到小逐步分解問題，求解子問題； 然后，合并子問題解，得原問題的解 分而治之 算法概要 1. 分解原問題為較小規(guī)模的子問題（規(guī)模最好相同） 2. 求解子問題 “分解求解”常是遞歸過程，直到子問題可簡單求解 3. 合并子問題的解，得原問題的解。不是所有算法都要“合并”,分治算法概要描述,分治算法的概要描述,集合的模 |s|：問題 s 的規(guī)模，即

2、 s 集合的元素個數(shù) 分解尺度 t ： 求解子問題的規(guī)模（不需繼續(xù)分解）,分治法應(yīng)用的一個簡例,分治法的應(yīng)用簡例 查找最大元素 已知：S 有 n 個元素，求 S 的最大元素。不妨設(shè) 本題有多種算法，現(xiàn)在用分治法解：每次將 S 一分為二，直到分解到 僅 2 個元素的子集為止。,分治法應(yīng)用簡例的過程圖解,分治法應(yīng)用簡例的過程圖解 已知：S = 30, 11, 42, 22, 1, 55, 21, 43 有 n = 23 個元素 求：S 的最大元素,分治法時間效率（例）,分治法的時間效率分析 上例的時間效率分析 輸入規(guī)模：元素個數(shù) n 基本操作：比較操作 效率類別：無最佳、最差、平均效率之分 增長函

3、數(shù)：比較次數(shù) T(n) 與 n 的關(guān)系 求解子集有 2 個元素，需比較 1 次。用數(shù)學(xué)歸納法分析 n = 2 = 21：T(21) = 1 比較 1 次 n = 4 = 22：T(22) = 2T(22/2) + 1 2T(4/2)：子集數(shù) = 2，規(guī)模 = 4/2 +1：兩個子集解需要合并 1 次（比較 1 次） n = 8 = 23：T(23) = 2T(23/2) + 1 = 2T(23-1) + 1 n = 2k： T(2k) = 2T(2k/2) + 1 = 2T(2k-1) + 1 歸納結(jié)果：,通用分治遞推式及其效率,分治法時間效率的 通用分治遞推式 規(guī)模 n 的問題，每次分為 a

4、 個子問題，求解子問題規(guī)模相等為 n / b （上例 a = 2 , b = 2）。為簡化分析，不妨設(shè) n = bk，k = 1, 2, 3, . 通用分治遞推式 c：求解子集的求解時間（基本操作執(zhí)行次數(shù)） f (n)：子集分解時間 + 子集解合并時間（本例比較1次 f (n) = 1） 解遞推式，得時間效率主定理：,合并排序,合并排序 待排序元素集合一分為二，每個子集繼續(xù)遞歸拆分，直到分解到僅一個 元素為止。然后，兩兩合并為一個有序集即完成了排序。過程如下：,合并排序算法,合并排序之分治算法 分解,合并排序算法（續(xù)）,合并,0 1 2 3 4 5 6 35407249398049,35,40

5、,72,49,39,80,3540,7249,3980,49,35407249,398049,49 72,35404972,394980,35394049497280,合并排序遞歸算法演示：,合并排序算法的時間效率分析,合并排序算法的時間效率分析 輸入規(guī)模：元素個數(shù) n 基本操作：比較操作 效率類別： while ( i p ) and ( j q ) 循環(huán)次數(shù)與 i 、j 有關(guān)。 最佳情況 每次循環(huán) i 或 j 之一增加，很快達(dá)到上限，結(jié)束循環(huán)。 待排序元素已排序，B、C 數(shù)組之一很快完成合并。 最壞情況 兩個循環(huán)變量交替增加，循環(huán)次數(shù)最多。 較小元素輪流來自于兩個數(shù)組。 時間效率遞推式 通

6、用分治遞推式 為簡化分析，假定 n = 2k, k = 1, 2, 3, .，即 B 和 C 數(shù)組元素數(shù)相同 每次拆分為兩個大小相同的子集，a = b = 2,合并排序算法的時間效率分析（續(xù)）,現(xiàn)在分析 合并子集解的比較次數(shù)，分解過程無基本操作。 最差情況 ： 兩個循環(huán)變量輪流增加，較小元素輪流來自于兩個數(shù)組 B 或 C。 每次合并時B、C 數(shù)組元素個數(shù)都是 n / 2 個，需比較 n1 次： 根據(jù)分治法效率主定理：,反向替換法可解遞推方程（略）,快速排序,快速排序 以非降序?yàn)槔?算法思想 對給定的待排序數(shù)組不斷進(jìn)行拆分，這與合并排序?qū)?shù)組的拆分不同。 合并排序按元素位置拆分（數(shù)組中間），快速

7、排序按元素值大小拆分， 得到 分區(qū) ( Partition )，拆分處稱為 分裂點(diǎn) ( Split position ) . 遞歸拆分下去，直到分區(qū)僅有一個元素為止。 建立分區(qū)時完成了元素的重排，拆分結(jié)束即排序結(jié)束。 分區(qū)特點(diǎn)：,快速排序算法,分區(qū)的確定,兩次掃描法確定分區(qū)（Partition） AL.R 中軸：初選一個元素為中軸 分裂點(diǎn)初值，其他元素與中軸比較 以確定分裂點(diǎn)。選擇中軸有多種方法，這里采用簡單策略即： 選數(shù)組第一個元素為中軸：p = AL 兩次掃描法 從左向右掃描一次，從右向左掃描一次 左右：從第 2 個元素開始，逐個與中軸比較，直到遇到大于或等于 中軸的元素為止。（ i ）

8、左右：從最后一個元素開始，逐個與中軸比較，直到遇到小于或等于 中軸的元素為止。（ j ） 根據(jù)兩次掃描 i、j 指針是否相交，分三種情況：,未相交（ij）,兩次掃描法確定分區(qū)(續(xù)),AL.R,相交（ij）,AL.R,相交（i=j）,將 i j 和 i = j 兩種情況相結(jié)合即 i j ，就交換 swap AL and Aj 得到分裂點(diǎn) S = j ，生成了分區(qū)。（生成兩個或一個分區(qū)）,分劃操作Partition演示：,i向右掃描，尋找 lilleft的元素,j向左掃描，尋找 ljlleft的元素,48,68,72,36,48,12,02,0 1 2 3 4 5 6 7,36不大于等于主元,所以

9、繼續(xù)掃描,找到大于主元的元素68,掃描暫停;準(zhǔn)備和lj交換;,left和right是待排序元素序列的下、上界；,left和right是待排序元素序列的下、上界；,(,),(,),此時,ij,掃描結(jié)束;把lleft和lj交換,實(shí)現(xiàn)了各元素按“左邊小右邊大”的原則分布在主元兩側(cè)。,如果ij,則交換li和lj,繼續(xù)各自的掃描。其目的是把較主元小的元素放到左邊,較主元大的元素放到右邊;,找到小于主元的元素02, 準(zhǔn)備和li交換;,接下來會分別把主元兩側(cè)的兩個子序列作為排序?qū)ο筮f歸執(zhí)行快速排序算法(過程略),兩次掃描法確定分區(qū)的算法偽碼,兩次掃描法確定分區(qū)的算法 Partition(AL . R) pA

10、L /選擇中軸 iL+1, jR /左右掃描位置指針。左掃描沒找到時，i 停在L+1位置 while (true) while (A i p) and ( j L ) do jj-1 /右掃描 if ( ij ) then break /左右掃描已交叉，退出循環(huán) swap(A i , A j ) /左右掃描未交叉 swap(A L, A j ) return ( j ) /返回分裂點(diǎn) j ,例 15, 18, 33, 10, 27, 11, 13, 42, 20， 請寫出快速排序的過程及結(jié)果。,結(jié)果： 10 11 13 1518 20 27 33 42,快速排序算法的時間效率分析,快速排序算法

11、的時間效率分析 輸入規(guī)模：元素個數(shù) n 基本操作 比較操作：A i p 效率類別 每次分裂點(diǎn)位置不同，所得兩個子分區(qū)大?。ㄔ貍€數(shù)）就不同，即子排序問題規(guī)模不同，導(dǎo)致子分區(qū)排序的基本操作次數(shù)不同。因此，快速排序有最佳、最差、平均效率。 最佳時間效率 每次分裂都在區(qū)域中點(diǎn)，將區(qū)域一分為二，得大小相同的兩子區(qū)域。左右掃描指針交叉時滿足 i = j. 比較總次數(shù) n 由通用分治遞推式和主定理得 ( a = b = 2，n = 2k , k 0 )： T(1) = 0 ; n 1：T(n) = 2T(n/2) + f (n) = nlog2n 建立分區(qū)需作 n 次比較， f (n) = n,最差時間效

12、率,最差時間效率 每次分裂都在區(qū)域兩端，兩子區(qū)域其一為空，另一個只比原區(qū)域少 一個元素 輸入序列已排序。例如 A0.n-1 為嚴(yán)格遞增： 中軸選p = A0，左掃描 i 停在 A1，右掃描 j 停在 A0，左右掃描 交叉，分裂點(diǎn)在 A0，左子區(qū)為空，右子區(qū)為A1.n-1，共 n+1 次 比較。繼續(xù)對右子區(qū) A1.n-1 排序，共作 n 次比較；如此繼續(xù)， 直到右子區(qū)僅有一個元素為止。 T(n) = (n+1) + n + . + 3 = (n+1) + n + . + 3 + 2 +1-2-1 = (n+1)(n+2) / 2 - 3 (n2) 平均時間效率 大小為 n 的隨機(jī)排列數(shù)組，平均比

13、較次數(shù)記為 Tavg(n) . 設(shè)分裂點(diǎn) s (0sn-1) 位于每個位置的概率相同為 1/ n . 兩子區(qū)的平均比較次數(shù)之和為 Tavg(s) + Tavg(n-1-s) .,快速排序平均時間效率（續(xù)）,平均時間效率遞推式：,分裂點(diǎn) s (0sn-1) 在每個位置的概率相等,統(tǒng)計平均,第一趟排序時元素間的比較次數(shù),因此，快速排序的平均情況僅比最佳情況多執(zhí)行38的比較操作。 此外，它的最內(nèi)層循環(huán)效率非常高，因此，比合并排序速度快些。,推導(dǎo)過程如下：,兩邊同乘以n,用n-1代替式(5-8),用式(5-8)減去式(5-9),兩邊同除以n(n+1),折半查找,折半查找 以非降序?yàn)槔?算法思想：比較查

14、找鍵 K 和有序數(shù)組中間元素Am K Am 在數(shù)組后半部分內(nèi)查找 算法描述,折半查找算法效率,折半查找的算法效率 輸入規(guī)模：元素個數(shù) n 基本操作：比較操作 效率類別：比較次數(shù)與輸入元素的分布有關(guān)。因此，有最佳、最差、 平均效率。最佳效率 Tbest (n) = 1 最差效率 直接寫出比較次數(shù)遞推式： 通過 1次 比較 K = Am ，化為一半規(guī)模的 1 個子問題 另據(jù)通用分治遞推式也可得上式： a = 1, b = 2, f (n) = 1 分解問題需作 1 次比較 解遞推式（要求自己推導(dǎo)）,折半查找算法簡評,折半查找算法簡評 就鍵值比較的查找算法而言，折半查找是一種最優(yōu)的查找算法； 折半查

15、找是分治法的一個非常不典型的應(yīng)用 分治技術(shù)是把一個問題分為若干子問題，每個子問題都需分別求解 。折半查找只有一個需要求解的子問題，所以，只是退化了的分治法。折半查找法歸入減半算法更合適，傳統(tǒng)上把它歸入分治法。,Strassen 矩陣乘法,Strassen 矩陣乘法 概述 改進(jìn)：計算兩個 2 階方陣的積只需 7 次乘法，蠻力法需 8 次乘法。 公式：(1969 年 V.Strassen 發(fā)表),簡單討論： 經(jīng)典蠻力法需 8次乘法和 4次加減法， 本算法需要 7次乘法和 18次加減法。 該算法吸引我們的不是這個原因，而 在于當(dāng) n 很大時所表現(xiàn)的卓越效率。,Strassen 矩陣乘法時間效率,當(dāng)

16、n = 2 k，計算兩個 n 階方陣的積 C=AB（若n 不是2 的乘方，矩陣 用全 0 行列填充）。A、B、C 分別劃分為 4 個 n / 2 階子矩陣： 子矩陣計算式與單個元素一樣（替換元素為子矩陣）。例如： C00 = M1+ M4 - M5 + M7, 其中 M1 = (A00+ A11)(B00+ B11), . n 階方陣遞歸分解，直到 n = 2 停止分解，計算兩個 22 矩陣的積。這就是計算大矩陣乘積的 Strassen 分治法。 算法效率 輸入規(guī)模：方陣的階 n 基本操作：乘法運(yùn)算 效率類別：乘法次數(shù)只與方陣的階 n 有關(guān)，無最佳、最差、平均效率,Strassen 矩陣乘法時

17、間效率（續(xù)1）,增長函數(shù) n 階方陣相乘問題，分解為 7個子問題，每個子問題是規(guī)模為 n/2 的 子矩陣乘法（ M1 M7）。乘法次數(shù)遞推式： 設(shè) n = 2k,Strassen 矩陣乘法時間效率（續(xù)2）,Strassen 算法的加法效率 減少乘法次數(shù)是以增加加法次數(shù)為代價。所以，檢查 Strassen 算法的 加法次數(shù)增長類型（加法的時間效率）。 輸入規(guī)模：方陣的階 n 基本操作：加法操作（包括減法：帶負(fù)號的加法） 效率類別：與乘法一樣，沒有最佳、最差、平均效率 增長函數(shù)遞推式 n 階方陣乘法分解為 7 個n / 2 階矩陣相乘的子問題，作 18 次 n / 2 階 子矩陣加法 (n/2)2

18、 次元素加法 (子方陣有 (n/2)2 個元素)。因此， 加法次數(shù)的遞推式： 依據(jù)主定理：,實(shí)驗(yàn)二 大整數(shù)乘法 概述 某些應(yīng)用尤其是當(dāng)代密碼技術(shù)，需要對超過100位的十進(jìn)制整數(shù)進(jìn)行 乘法運(yùn)算。整數(shù)過大超過計算機(jī)字長，也需特別處理。 經(jīng)典算法 兩個 n 位整數(shù)相乘，需 n2 次乘法。將乘法作基本操作，位數(shù) n 作為 輸入規(guī)模，該蠻力算法具有平方增長率。 算法改進(jìn) 提高效率 策略：減少乘法次數(shù)，可適當(dāng)增加加法次數(shù)。 舉例：計算 2314，要求只作 3 次位乘 23 = 2101 + 3100， 14 = 1101 + 4100， 2314 = (2101 + 3100)(1101 + 4100) = (21)102 + (31 + 24)101 + (34)100 4 次乘法 存儲 21 、34（2 次乘法）的結(jié)果： 共 3 次乘法 31 + 24 = (2 + 3)(1 + 4) - (21) - (34) 增加1 次乘法,大整數(shù)乘法: 算法,兩個 2 位數(shù)相乘（