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

1、1 在封建國(guó)家中，君主為了有效地統(tǒng)治國(guó)家，往往在封建國(guó)家中，君主為了有效地統(tǒng)治國(guó)家，往往使用分治的方法，使用分治的方法， 就是將國(guó)土分成幾個(gè)部分，對(duì)每一部分國(guó)土，君就是將國(guó)土分成幾個(gè)部分，對(duì)每一部分國(guó)土，君主派一個(gè)諸侯去管理，主派一個(gè)諸侯去管理， 國(guó)君自己就不直接過(guò)問(wèn)這部分國(guó)土的事情了。國(guó)君自己就不直接過(guò)問(wèn)這部分國(guó)土的事情了。 國(guó)君的工作就是將一個(gè)國(guó)家分成幾個(gè)部分，委派國(guó)君的工作就是將一個(gè)國(guó)家分成幾個(gè)部分，委派諸侯，過(guò)問(wèn)諸侯工作的結(jié)果。諸侯，過(guò)問(wèn)諸侯工作的結(jié)果。 在計(jì)算機(jī)科學(xué)中，這種思想得到借鑒。在計(jì)算機(jī)科學(xué)中，這種思想得到借鑒。2subproblem 2 of size n/2subprob

2、lem 1 of size n/2a solution to subproblem 2a problem of size na solution to subproblem 1a solution tothe original problem3 將規(guī)模為將規(guī)模為N的問(wèn)題分解為的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題個(gè)規(guī)模較小的子問(wèn)題,使這使這些子問(wèn)題相互獨(dú)立可分別求解些子問(wèn)題相互獨(dú)立可分別求解,再將再將k個(gè)子問(wèn)題的解合并個(gè)子問(wèn)題的解合并成原問(wèn)題的解成原問(wèn)題的解.如如子問(wèn)題子問(wèn)題的規(guī)模仍很大的規(guī)模仍很大,則則反復(fù)分解反復(fù)分解直到直到問(wèn)題小到可直接求解為止。問(wèn)題小到可直接求解為止。 在分治法中在分治法中,

3、子問(wèn)題的解法通常與原問(wèn)題相同子問(wèn)題的解法通常與原問(wèn)題相同,自然導(dǎo)自然導(dǎo)致致遞歸過(guò)程遞歸過(guò)程。4 一個(gè)簡(jiǎn)單的例子：一個(gè)簡(jiǎn)單的例子： N個(gè)數(shù)字求和，如何用分治法解決？個(gè)數(shù)字求和，如何用分治法解決？ 是不是分治法一定比蠻力法高效呢？是不是分治法一定比蠻力法高效呢？ 串行計(jì)算串行計(jì)算 并行計(jì)算并行計(jì)算 通過(guò)分治法解決大問(wèn)題的時(shí)間等于所有解決小問(wèn)通過(guò)分治法解決大問(wèn)題的時(shí)間等于所有解決小問(wèn)題的時(shí)間？題的時(shí)間？ T(n)=aT(n/b)+f(n)劃分為規(guī)模為劃分為規(guī)模為n/b的小問(wèn)題的小問(wèn)題a個(gè)小問(wèn)題個(gè)小問(wèn)題解決大問(wèn)題的解決大問(wèn)題的消耗的時(shí)間消耗的時(shí)間合并小問(wèn)題消合并小問(wèn)題消耗的時(shí)間耗的時(shí)間5 T(n)=a

4、T(n/b)+f(n)遞推式的解法遞推式的解法 直接使用公式直接使用公式 寫出分治法解決寫出分治法解決n個(gè)數(shù)字相加問(wèn)題的效率類型，設(shè)每次個(gè)數(shù)字相加問(wèn)題的效率類型，設(shè)每次分為分為2個(gè)子問(wèn)題個(gè)子問(wèn)題dadddddbanbannbannTdnnfifb )( )log( )()(0 )()( log6 本章解決的問(wèn)題：本章解決的問(wèn)題： 排序排序 查找查找 大整數(shù)乘法大整數(shù)乘法 矩陣乘法矩陣乘法 最近對(duì)最近對(duì) 凸包凸包 二叉樹(shù)遍歷二叉樹(shù)遍歷7問(wèn)題：?jiǎn)栴}： 將將n個(gè)元素排成非遞減順序。個(gè)元素排成非遞減順序。思考如何使用分治法將大問(wèn)題分成小問(wèn)題？思考如何使用分治法將大問(wèn)題分成小問(wèn)題？88329715412

5、3456788329238914577154832938291745832971547154分分合合9 算法思路：算法思路： 若若n為為1,算法終止算法終止;否則否則,將將n個(gè)待排元素分割成個(gè)待排元素分割成k(k=2)個(gè)大致相等子集合個(gè)大致相等子集合A、B,對(duì)每一個(gè)子集合對(duì)每一個(gè)子集合分別遞歸排序分別遞歸排序,再將排好序的子集歸并為一個(gè)集再將排好序的子集歸并為一個(gè)集合。合。10 算法算法 MergeSort(A0.n-1 ) / 輸入：未排序序列輸入：未排序序列A0.n-1 / 輸出：已排序序列輸出：已排序序列A0.n-1 if n 1 copy A0. n/2 -1 to B0. n/2 -

6、1 copy A n/2 .n-1 to C0. n/2 -1 MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 當(dāng)前當(dāng)前n規(guī)模規(guī)模的問(wèn)題，的問(wèn)題，分成分成2個(gè)子個(gè)子問(wèn)題問(wèn)題以同樣的方式解決子問(wèn)題以同樣的方式解決子問(wèn)題用歸并排序，形成最終的用歸并排序，形成最終的有序數(shù)組有序數(shù)組11Merge(B,C,A)是將是將有序數(shù)組有序數(shù)組B、C合并為合并為有序數(shù)有序數(shù)組組A的算法。的算法。 稱為歸并排序稱為歸并排序 歸并排序示例：歸并排序示例：1 3 4 9 13 34 672 5 61 2 3 4 5 69 13 34 67B數(shù)組數(shù)組C數(shù)組數(shù)組12前提前提：數(shù)組

7、數(shù)組B及數(shù)組及數(shù)組C已經(jīng)有序已經(jīng)有序。 比較數(shù)組比較數(shù)組B的第一個(gè)記錄與數(shù)組的第一個(gè)記錄與數(shù)組C的第一個(gè)記錄的第一個(gè)記錄將將KEY值小者輸出至數(shù)組值小者輸出至數(shù)組A，再?gòu)南鄳?yīng)數(shù)組讀進(jìn)，再?gòu)南鄳?yīng)數(shù)組讀進(jìn)一個(gè)記錄，替代已被輸出的記錄，再繼續(xù)比較。一個(gè)記錄，替代已被輸出的記錄，再繼續(xù)比較。結(jié)束結(jié)束：直至有一個(gè)數(shù)組的記錄已被窮盡，然后再直至有一個(gè)數(shù)組的記錄已被窮盡，然后再將未窮盡的數(shù)組上的所有記錄拷貝到輸出數(shù)組將未窮盡的數(shù)組上的所有記錄拷貝到輸出數(shù)組A上。上。13 Merge(B0.p-1,C0.q-1,A0.p+q-1) i=0,j=0,k=0; while ip and j 1 copy A0.

8、n/2 -1 to B0. n/2 -1 copy A n/2 .n-1 to C0. n/2 -1 MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 基本操作？基本操作？ 似乎較難判斷。似乎較難判斷。 寫出總體工作量表達(dá)式。寫出總體工作量表達(dá)式。設(shè)設(shè)n=2k, 總工作量表示為：總工作量表示為：C(n)=(1次除法次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)C(1)=015 簡(jiǎn)寫為簡(jiǎn)寫為 C(n)=2C(n/2)+Cmerge(n)+kn 基本操作基本操作 比較？拷貝？比較？拷貝？ (比較的次數(shù)不會(huì)大于拷貝的次數(shù)比較的次數(shù)不會(huì)大于

9、拷貝的次數(shù)) 是否和其他因素相關(guān)？是否和其他因素相關(guān)？ 最壞情況如何？最壞情況如何？ 歸并排序的效率歸并排序的效率Cmerge(n)=n,C (n)=2C(n/2)+sn解得解得 C(n)=nlog2n-n+1(nlog2n)C(n)=(1次除法次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)16 最壞情況最壞情況(nlog2n) 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 合并排序在最壞情況下的鍵值比較次數(shù)合并排序在最壞情況下的鍵值比較次數(shù)十分接近于十分接近于任何基于比較的排序算法在任何基于比較的排序算法在理論理論上能夠達(dá)到的最少上能夠達(dá)到的最少次數(shù)次數(shù) 合并排序精確解合并排序精確解Cworst(n)

10、=nlog2n-n+1 理論最小值理論最小值nlog2n-1.44n向上取整向上取整 缺點(diǎn)：缺點(diǎn)： 需要線性的額外空間，體現(xiàn)在何處？需要線性的額外空間，體現(xiàn)在何處？ 雖然合并也可做到雖然合并也可做到“在位在位”，但導(dǎo)致算法過(guò)于復(fù)雜。，但導(dǎo)致算法過(guò)于復(fù)雜。17 算法思路算法思路: 對(duì)于輸入對(duì)于輸入A0. n-1，按以下三個(gè)步驟進(jìn)行排序：，按以下三個(gè)步驟進(jìn)行排序： (1)分區(qū)分區(qū):取取A中的一個(gè)元素為中的一個(gè)元素為支點(diǎn)支點(diǎn)(pivot) 將將A0.n-1劃分成劃分成3段段: A0.s-1, As , As+1.n-1, 使得使得 A0.s-1中任一元素中任一元素 As, As+1.n-1中任一元素

11、中任一元素 As; 下標(biāo)下標(biāo)s 在劃分在劃分過(guò)程中確定。過(guò)程中確定。 (2)遞歸求解遞歸求解:遞歸調(diào)用快速排序法分別對(duì)遞歸調(diào)用快速排序法分別對(duì)A0.s-1和和As+1.n-1排序。排序。 (3)合并合并:合并合并A0.s-1, As, As+1.n-1為為A0.n-118 49 38 65 97 13 27 一趟排序后一趟排序后27 38 13 4976 97 65 分別快排分別快排132738 65769719 快速排序算法快速排序算法 QuickSort(Al.r) / 使用快速排序法對(duì)序列或者子序列排序使用快速排序法對(duì)序列或者子序列排序 / 輸入：子序列輸入：子序列Al.r或者序列本身或

12、者序列本身A0.n-1 / 輸出：非遞減序列輸出：非遞減序列A if l r s Partition( Al.r ) QuickSort( Al.s-1 ) QuickSort( As+1.r ) /s是中軸元素是中軸元素/基準(zhǔn)點(diǎn)，是數(shù)組分區(qū)位置的標(biāo)志基準(zhǔn)點(diǎn)，是數(shù)組分區(qū)位置的標(biāo)志中軸元素如何選？中軸元素如何選？選好中軸后如何掃描數(shù)組形成分區(qū)？選好中軸后如何掃描數(shù)組形成分區(qū)？找到分裂點(diǎn)找到分裂點(diǎn)s，分區(qū)，分區(qū)按同樣的方法處理子區(qū)間按同樣的方法處理子區(qū)間20初始數(shù)組初始數(shù)組 A0.n-1=5, 3, 1, 9, 8, 2, 4, 7, 取元素取元素A0=5作為分裂點(diǎn)作為分裂點(diǎn), 紅色表示紅色表示i

13、上的元素上的元素，藍(lán)色表示藍(lán)色表示j上的元素上的元素 位置位置i 0 1 2 3 4 5 6 7 5 3 1 9 8 2 4 7 i，j上的元素和分裂點(diǎn)比較并移動(dòng)上的元素和分裂點(diǎn)比較并移動(dòng) 對(duì)于對(duì)于i遇到比分裂點(diǎn)大或等于時(shí)停止遇到比分裂點(diǎn)大或等于時(shí)停止 對(duì)于對(duì)于j遇到比分裂點(diǎn)小或等于時(shí)停止遇到比分裂點(diǎn)小或等于時(shí)停止 5 3 1 9 8 2 4 7 停止后，停止后，ij 交換分裂點(diǎn)和交換分裂點(diǎn)和Aj i=j Ai= Aj=分裂點(diǎn)上的值分裂點(diǎn)上的值 5 3 1 4 8 2 9 7 交換后，交換后，i加加1，j減減1 5 3 1 4 8 2 9 7 繼續(xù)前面的比較和移動(dòng)繼續(xù)前面的比較和移動(dòng) 5 3

14、1 4 2 8 9 7 5 3 1 4 2 8 9 7 ij 交換分裂點(diǎn)和交換分裂點(diǎn)和Aj 2 3 1 4 5 8 9 7 一次分區(qū)完成一次分區(qū)完成 21 算法算法 Partition( Al.r ) / 輸入：子數(shù)組輸入：子數(shù)組Al.r / 輸出：分裂點(diǎn)輸出：分裂點(diǎn)/基準(zhǔn)點(diǎn)基準(zhǔn)點(diǎn)pivot的位置的位置 p Ali l; j r+1 repeat repeati i + 1until Ai p repeat j j 1 until Aj p swap( Ai, Aj ) until i j swap( Ai, Aj ) swap( Al, Aj ) return j22if l r s Par

15、tition( Al.r ) QuickSort( Al.s-1 ) QuickSort( As+1.r ) 基本操作？基本操作？ 似乎較難判斷。似乎較難判斷。 寫出總體工作量表達(dá)式。寫出總體工作量表達(dá)式。 C(n)=Cpartition(n)+CQuickSort(s前面前面)+ CQuickSort(s后面后面)23 C(n)=Cpartition(n)+CQuickSort(s前面前面)+ CQuickSort(s后面后面) 上式依賴于上式依賴于s的位置。的位置。 考慮考慮partition的的基本操作：基本操作： 比較比較 一次分區(qū)算法的比較次數(shù)是否和其他因素相關(guān)一次分區(qū)算法的比較次數(shù)

16、是否和其他因素相關(guān) 對(duì)于對(duì)于一次長(zhǎng)度為一次長(zhǎng)度為n的數(shù)組的的數(shù)組的分區(qū)算法分區(qū)算法，如果出現(xiàn)指針，如果出現(xiàn)指針交叉，所執(zhí)行的比較是交叉，所執(zhí)行的比較是n+1次，為什么？次，為什么？ 相等，比較次數(shù)為相等，比較次數(shù)為n次次24 整個(gè)算法的最壞情況下：整個(gè)算法的最壞情況下： 在進(jìn)行了在進(jìn)行了n+1次比較后建立了分區(qū)，還會(huì)對(duì)數(shù)次比較后建立了分區(qū)，還會(huì)對(duì)數(shù)組進(jìn)行排序，繼續(xù)到最后一個(gè)子數(shù)組組進(jìn)行排序，繼續(xù)到最后一個(gè)子數(shù)組An-2.n-1。總比較次數(shù)為：總比較次數(shù)為： Cworst(n) =(n+1)+n+3 =(n+2)(n+1)/2-3 (n2)25 最好情況最好情況 每次分區(qū)執(zhí)行每次分區(qū)執(zhí)行n次次

17、并且每次都是等分并且每次都是等分 Cbest(n)=2Cbest(n/2)+n (nlog2n)26 平均情況平均情況 分裂點(diǎn)有可能在一次分區(qū)后出現(xiàn)在每個(gè)位置分裂點(diǎn)有可能在一次分區(qū)后出現(xiàn)在每個(gè)位置 設(shè)概率是設(shè)概率是1/nnnnnnCCCsnCsCnnnCnavgavgavgnsavgavgavg210log38. 1ln2)(0) 1 (0)0()1()() 1(1)( 127 合并排序最差合并排序最差(nlog2n) 快速排序最優(yōu)快速排序最優(yōu)(nlog2n) 最差最差(n2) 平均平均(1.38nlog2n)選擇排序選擇排序 (n2)冒泡排序冒泡排序 (n2)28 位置：位置：0 1 2 3

18、 4 5 6 7 8 9 10 11 12 值：值： 3,14,27,31,39,42,55,70,74,81,85,93,98 K=70 迭代迭代1 l=0 m=6 r=12 迭代迭代2 l m=9 r 迭代迭代3 l r 結(jié)果結(jié)果 m= (7+8)/2 =729 BinarySearch( A0.n-1, k ) / 輸入：已排序大小為輸入：已排序大小為n的序列的序列A，待搜索對(duì)象，待搜索對(duì)象k / 輸出：如果搜索成功，則返回輸出：如果搜索成功，則返回k的位置，否則返的位置，否則返回回-1 l=0,r=n-1; While lr mid= (l+r)/2 if k = Amid retur

19、n mid else if k Amid r=m-1 else l=m+1 return -1 30 折半查找效率分析： 基本操作：比較基本操作：比較 最壞情況下，比較次數(shù)最壞情況下，比較次數(shù) C(n)=C( n/2 )+1 C(1)=1 設(shè)設(shè)n=2k，可解得，可解得 C(n)=k+1=log2n+1 于是于是 C(n)(log2n)31 折半查找折半查找 最差最差(log2n) 順序查找順序查找 (n) 是一種退化了的分治法是一種退化了的分治法32 所謂二叉樹(shù)的遍歷指的是遵循某一種次序來(lái)訪問(wèn)二所謂二叉樹(shù)的遍歷指的是遵循某一種次序來(lái)訪問(wèn)二叉樹(shù)上的所有結(jié)點(diǎn)，使得樹(shù)中每一個(gè)結(jié)點(diǎn)被訪問(wèn)了一次叉樹(shù)上的

20、所有結(jié)點(diǎn)，使得樹(shù)中每一個(gè)結(jié)點(diǎn)被訪問(wèn)了一次且只訪問(wèn)一次。且只訪問(wèn)一次。 由于二叉樹(shù)是一種非線性結(jié)構(gòu)，樹(shù)中的結(jié)點(diǎn)可能有由于二叉樹(shù)是一種非線性結(jié)構(gòu)，樹(shù)中的結(jié)點(diǎn)可能有不止一個(gè)的直接后繼結(jié)點(diǎn)，所以遍歷以前必須先規(guī)定訪不止一個(gè)的直接后繼結(jié)點(diǎn)，所以遍歷以前必須先規(guī)定訪問(wèn)的次序。問(wèn)的次序。 33 二叉樹(shù)的中序遍歷算法比較簡(jiǎn)單，使用遞歸的策略。在二叉樹(shù)的中序遍歷算法比較簡(jiǎn)單，使用遞歸的策略。在遍歷以前首先確定遍歷的樹(shù)是否為空，如果為空，則直遍歷以前首先確定遍歷的樹(shù)是否為空，如果為空，則直接返回；否則中序遍歷的算法步驟如下：接返回；否則中序遍歷的算法步驟如下： （1）對(duì)左子樹(shù)）對(duì)左子樹(shù)L執(zhí)行中序遍歷算法執(zhí)行中序遍

21、歷算法 （2）訪問(wèn)輸出根結(jié)點(diǎn)）訪問(wèn)輸出根結(jié)點(diǎn)V的值。的值。 （3）對(duì)右子樹(shù)）對(duì)右子樹(shù)R執(zhí)行中序遍歷算法。執(zhí)行中序遍歷算法。 34 有了上面的中序遍歷的過(guò)程，前序遍歷也是類似的。在有了上面的中序遍歷的過(guò)程，前序遍歷也是類似的。在遍歷以前首先確定遍歷的樹(shù)是否為空，如果為空，則直遍歷以前首先確定遍歷的樹(shù)是否為空，如果為空，則直接返回；否則前序遍歷的算法步驟如下：接返回；否則前序遍歷的算法步驟如下： （1）訪問(wèn)輸出根結(jié)點(diǎn)）訪問(wèn)輸出根結(jié)點(diǎn)V的值；的值； （2）對(duì)左子樹(shù)）對(duì)左子樹(shù)L執(zhí)行前序遍歷算法。執(zhí)行前序遍歷算法。 （3）對(duì)右子樹(shù)）對(duì)右子樹(shù)R執(zhí)行前序遍歷算法。執(zhí)行前序遍歷算法。 35輸出 -遍歷 L-+

22、遍歷 R-/樹(shù)-輸出 -+遍歷 L-a遍歷 R-*樹(shù)-+輸出 -/遍歷 L-e遍歷 R-f樹(shù)-/輸出 -+遍歷 L-c遍歷 R-d樹(shù)-輸出 -a遍歷 L-遍歷 R-樹(shù)-a輸出 -*遍歷 L-b遍歷 R-樹(shù)-*輸出 -b遍歷 L-遍歷 R-樹(shù)-b輸出 -c遍歷 L-遍歷 R-樹(shù)-c輸出 -e遍歷 L-遍歷 R-樹(shù)-e輸出 -f遍歷 L-遍歷 R-樹(shù)-f輸出 -d遍歷 L-遍歷 R-樹(shù)-d3668793(2)541取 1687913254取 2(3)(8)998(5)8(7)95(4)687912取 334687912取 4354(6)87912取 53541112取 6635472取 76354

23、72取 8， 9637 算法算法 Height(T) /輸入一棵二叉樹(shù)輸入一棵二叉樹(shù)T /輸出二叉樹(shù)的高度輸出二叉樹(shù)的高度 /二叉樹(shù)高度定義：葉子到樹(shù)根的最長(zhǎng)路徑二叉樹(shù)高度定義：葉子到樹(shù)根的最長(zhǎng)路徑 if T= return -1 else return maxHeight(L), Height(R)+1 例：計(jì)算上例中二叉樹(shù)的高度例：計(jì)算上例中二叉樹(shù)的高度 H(T)=1+maxH(2),H(6)=2+maxH(3),H(4) =3+H(5)=538 整數(shù)乘法問(wèn)題整數(shù)乘法問(wèn)題: 設(shè)設(shè)A和和B為兩個(gè)為兩個(gè)N位的整數(shù)，位的整數(shù)，計(jì)算它們的乘積計(jì)算它們的乘積A B。 思考按照通常做法要執(zhí)行思考按照通

24、常做法要執(zhí)行一位一位乘法多少次？乘法多少次？ 如：234 125 1170 468 234 * * * * * N2次。次。39 分治法如何體現(xiàn)。分治法如何體現(xiàn)。 令令N為偶數(shù)，則為偶數(shù)，則A和和B可表示為可表示為 其中其中a1和和a2分別為分別為A的前半部和后半部。的前半部和后半部。 Aa110N/2+a2 (123456=123106/2+456) Bbl10N/2+b2 bl 和和b2則分別為則分別為B的前半部和后半部。如果的前半部和后半部。如果按下述方法得到積按下述方法得到積(多項(xiàng)式相乘多項(xiàng)式相乘) AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+

25、a2b1)10n/2+a2b240 AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+a2b1)10n/2+a2b2 估算時(shí)間效率是多少估算時(shí)間效率是多少(即需要多少次一位乘法即需要多少次一位乘法)？ 則要?jiǎng)t要4次次N/2位乘法，即位乘法，即N2次一位乘法。因此這次一位乘法。因此這種方法沒(méi)有改進(jìn)原來(lái)的方法。種方法沒(méi)有改進(jìn)原來(lái)的方法。41AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+a2b1)10n/2+a2b2 =a1b110n+(a1+a2)(b1+b2)-a1b1-a2b2)10n/2+a2b2此時(shí)需要乘法多少次？

26、此時(shí)需要乘法多少次？ 這種方法需要這種方法需要3次次n/2位位的乘法及的乘法及一些加減法一些加減法。 記記C(n)為計(jì)算兩個(gè)為計(jì)算兩個(gè)n位整數(shù)相乘所需的基本操位整數(shù)相乘所需的基本操作執(zhí)行次數(shù)，則作執(zhí)行次數(shù)，則42有有 C(n)=3C(n/2)+kn C(1)=1 其中，其中，k為常數(shù)為常數(shù)，KN表示加法、減法所需時(shí)間與表示加法、減法所需時(shí)間與N成成正比。正比。 解此遞歸方程，得解此遞歸方程，得 C(n)=nlog3+2knlog3-2kn O(nlog3) O(n1.58) 可見(jiàn)，乘法效率有改善。可見(jiàn)，乘法效率有改善。43 其原理在于乘法操作所需時(shí)間比加法多得多，因其原理在于乘法操作所需時(shí)間比

27、加法多得多，因此減少乘法次數(shù)，此減少乘法次數(shù)， 雖然代價(jià)為增加加法運(yùn)算，總的效果還是加速了雖然代價(jià)為增加加法運(yùn)算，總的效果還是加速了運(yùn)算運(yùn)算. 大整數(shù)大整數(shù)(500比特或比特或1024比特比特)的乘法用于加密和的乘法用于加密和認(rèn)證認(rèn)證.44 矩陣乘法是線性代數(shù)中最常見(jiàn)的運(yùn)算之一，它在數(shù)值矩陣乘法是線性代數(shù)中最常見(jiàn)的運(yùn)算之一，它在數(shù)值計(jì)算中有廣泛的應(yīng)用。計(jì)算中有廣泛的應(yīng)用。 若若A和和B是是2個(gè)個(gè)nn的矩陣，則它們的乘積的矩陣，則它們的乘積C=AB同同樣是一個(gè)樣是一個(gè)nn的矩陣。的矩陣。A和和B的乘積矩陣的乘積矩陣C中的元素中的元素Ci,j定義為定義為: 若依此定義來(lái)計(jì)算若依此定義來(lái)計(jì)算A和和B

28、的乘積矩陣的乘積矩陣C，則每計(jì)算，則每計(jì)算C的的一個(gè)元素一個(gè)元素Ci,j，加法和乘法的次數(shù)是多少？，加法和乘法的次數(shù)是多少？ 需要做需要做n個(gè)乘法和個(gè)乘法和n-1次加法。次加法。 因此，求出矩陣因此，求出矩陣C的的n2個(gè)元素所需的計(jì)算時(shí)間為個(gè)元素所需的計(jì)算時(shí)間為O(n3)。45 如何對(duì)矩陣乘法采用分治？如何對(duì)矩陣乘法采用分治？ 首先，假設(shè)首先，假設(shè)n=2k。 將矩陣將矩陣A，B和和C中每一矩陣都分塊成為中每一矩陣都分塊成為4個(gè)大小個(gè)大小相等相等的子矩陣，每個(gè)子矩陣都是的子矩陣，每個(gè)子矩陣都是n/2n/2的方陣。的方陣。由此可將方程由此可將方程C=AB重寫為重寫為:46其中：其中： C11 C1

29、2 C21 C22 是多少？是多少？ C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22 47 C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22 依此算法，計(jì)算依此算法，計(jì)算2個(gè)個(gè)n階方陣的乘積轉(zhuǎn)化階方陣的乘積轉(zhuǎn)化為計(jì)算為計(jì)算8個(gè)個(gè)n/2階方陣的乘積階方陣的乘積和和4個(gè)個(gè)n/2階方陣的加法階方陣的加法上述分治法的計(jì)算時(shí)間耗費(fèi)上述分治法的計(jì)算時(shí)間耗費(fèi)T(n)如何寫？如何寫？T(n)=8T(n/2)+cn2 T(1

30、)=1計(jì)算計(jì)算T(n)是多少？是多少？這個(gè)遞歸方程的解仍然屬于這個(gè)遞歸方程的解仍然屬于O(n3) 48Strassen方法方法 M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12)他的算法只用了他的算法只用了7次乘法運(yùn)算，但增加了加、減法的運(yùn)次乘法運(yùn)算，但增加了加、減法的運(yùn)算次數(shù)算次數(shù)10次。次。觀察使用了多少觀察使用了多少次乘法次乘法?加減法用了多少加減法用了多少次？次？49 于是可得到于

31、是可得到: C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7 引入引入8次加減法次加減法Strassen矩陣乘積分治算法中，用了矩陣乘積分治算法中，用了7次對(duì)于次對(duì)于n/2階矩陣乘積階矩陣乘積的遞歸調(diào)用和的遞歸調(diào)用和18次次n/2階矩陣的加減運(yùn)算。階矩陣的加減運(yùn)算。由此可知，該算法的所需的計(jì)算時(shí)間由此可知，該算法的所需的計(jì)算時(shí)間T(n)滿足如下的遞歸方滿足如下的遞歸方程程: 50其解為其解為T(n)O(nlog7)O(n2.81)。由此可見(jiàn)，由此可見(jiàn)，Strassen矩陣乘法的計(jì)算時(shí)間復(fù)雜性矩陣乘法的計(jì)算時(shí)間復(fù)雜性比普通矩陣乘法有階的改進(jìn)。

32、比普通矩陣乘法有階的改進(jìn)。 T(n)=7T(n/2)+kn2 T(1)=151 大整數(shù)乘法和矩陣乘法分別利用了將乘法轉(zhuǎn)換為大整數(shù)乘法和矩陣乘法分別利用了將乘法轉(zhuǎn)換為多個(gè)加法進(jìn)行替代。多個(gè)加法進(jìn)行替代。 對(duì)于矩陣乘法可以將矩陣作對(duì)于矩陣乘法可以將矩陣作3 3的劃分，即將的劃分，即將矩陣分成九個(gè)子矩陣，或作矩陣分成九個(gè)子矩陣，或作 4 4的劃分的劃分(即將矩即將矩陣分成十六個(gè)子矩陣陣分成十六個(gè)子矩陣)。 相應(yīng)地要求矩陣的階相應(yīng)地要求矩陣的階n是是3的整次冪的整次冪(或或4的整次的整次冪冪)。有人沿這個(gè)途徑改善了矩陣乘法的復(fù)雜度。有人沿這個(gè)途徑改善了矩陣乘法的復(fù)雜度。52問(wèn)題問(wèn)題: 給定平面給定平面

33、S上上n個(gè)點(diǎn)個(gè)點(diǎn),找其中的一對(duì)點(diǎn)找其中的一對(duì)點(diǎn),使得在使得在n(n-1)/2個(gè)點(diǎn)對(duì)中個(gè)點(diǎn)對(duì)中, 該點(diǎn)對(duì)的距離最小。該點(diǎn)對(duì)的距離最小。算法思路算法思路: 1) n較小時(shí)直接求較小時(shí)直接求(n=2). 2) 將將S上的上的n個(gè)點(diǎn)分成大致相等的個(gè)點(diǎn)分成大致相等的2個(gè)子集個(gè)子集S1和和S2 3) 分別求分別求S1和和S2中的最接近點(diǎn)對(duì)中的最接近點(diǎn)對(duì) 4) 求一點(diǎn)在求一點(diǎn)在S1、另一點(diǎn)在、另一點(diǎn)在S2中的最近點(diǎn)對(duì)中的最近點(diǎn)對(duì) 5) 從上述三對(duì)點(diǎn)中找距離最近的一對(duì)從上述三對(duì)點(diǎn)中找距離最近的一對(duì).53 2) 將將S上的上的n個(gè)點(diǎn)分成大致相等的個(gè)點(diǎn)分成大致相等的2個(gè)子集個(gè)子集S1和和S2如何分？如何分？將點(diǎn)按照將點(diǎn)按照x軸升序排序軸升序排序畫(huà)一條垂直線畫(huà)一條垂直線x=c543) 遞歸求遞歸求S1和和S2中的最接近點(diǎn)對(duì)中的最接近點(diǎn)對(duì)d1，d2d=mind1,d2是否這就是最小距離？是否這就是最小距離？不一定，距離最近的點(diǎn)可能位于分界線的兩側(cè)不一定，距離最近的點(diǎn)可能位于分界線的兩側(cè)55 4) 求一點(diǎn)在求一點(diǎn)在S1、另一點(diǎn)在、另一點(diǎn)在S2中的最近點(diǎn)對(duì)中的最近點(diǎn)對(duì)是否需要考察是否需要考察S1和和S2中的所有的點(diǎn)？中的所有的點(diǎn)？只需考察以只需考察以