第3章分治法PPT課件

1、3.2 求解排序問題求解排序問題3.1 分治法概述分治法概述3.3 求解查找問題求解查找問題3.4 求解組合問題求解組合問題3.5 求解大整數(shù)乘法和矩陣乘法問題求解大整數(shù)乘法和矩陣乘法問題3.6 并行計(jì)算簡(jiǎn)介并行計(jì)算簡(jiǎn)介對(duì)于一個(gè)規(guī)模為對(duì)于一個(gè)規(guī)模為n的問的問題：題：若若該問題可以容易地解決該問題可以容易地解決（比如說規(guī)模（比如說規(guī)模n較?。﹦t直接解較?。﹦t直接解決，否決，否則將其分解為則將其分解為k個(gè)規(guī)個(gè)規(guī)模較小的子問模較小的子問題，這題，這些子問題互相獨(dú)立且與原問題形式相些子問題互相獨(dú)立且與原問題形式相同，遞同，遞歸地解這些子問歸地解這些子問題，然題，然后將各子問題的解合并得到后將各子問題的

2、解合并得到原問題的解原問題的解。這種算法設(shè)計(jì)策略叫做這種算法設(shè)計(jì)策略叫做分治法。3.1 分治法概述分治法概述分治法所能解決的問題一般具有以下幾個(gè)特征：分治法所能解決的問題一般具有以下幾個(gè)特征：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決。）該問題的規(guī)?？s小到一定的程度就可以容易地解決。（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題。）該問題可以分解為若干個(gè)規(guī)模較小的相同問題。（3）利用該問題分解出的子問題的解可以合并為該問題的）利用該問題分解出的子問題的解可以合并為該問題的解。解。（4）該問題所分解出的各個(gè)子問題是相互獨(dú)立）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即的，即子問子問題之間不

3、包含公共的子問題。題之間不包含公共的子問題。分分治法通常采用遞歸算法設(shè)計(jì)技治法通常采用遞歸算法設(shè)計(jì)技術(shù)，在術(shù)，在每一層遞歸上都有每一層遞歸上都有3個(gè)步驟：個(gè)步驟： 分解：分解：將原問題分解為若干個(gè)規(guī)模較將原問題分解為若干個(gè)規(guī)模較小，相小，相互獨(dú)互獨(dú)立，與立，與原問題形式相同的子問題。原問題形式相同的子問題。 求解子問題：求解子問題：若子問題規(guī)模較小而容易被解決則直若子問題規(guī)模較小而容易被解決則直接求接求解，否解，否則遞歸地求解各個(gè)子問題。則遞歸地求解各個(gè)子問題。 合并：合并：將各個(gè)子問題的解合并為原問題的解。將各個(gè)子問題的解合并為原問題的解。 分治法的一般的算法分治法的一般的算法設(shè)計(jì)框架如下設(shè)

4、計(jì)框架如下：divide-and-conquer(P) if |P|n0 return adhoc(P); 將將P分解為較小的子問題分解為較小的子問題 P1，P2，Pk; for(i=1;ii & aj=tmp) j-; /從右向左掃從右向左掃描，找描，找第第1個(gè)關(guān)鍵字小于個(gè)關(guān)鍵字小于tmp的的aj ai=aj;/將將aj前移到前移到ai的位置的位置 while (ij & ai=tmp) i+; /從左向右掃從左向右掃描，找描，找第第1個(gè)關(guān)鍵字大于個(gè)關(guān)鍵字大于tmp的的ai aj=ai;/將將ai后移到后移到aj的位置的位置ai=tmp;return i;測(cè)試用例：測(cè)試用例：

5、5，2，1，7，10，6，9，4，3，8快速排序算法：快速排序算法：void QuickSort(int a，int s，int t)/對(duì)對(duì)as.t元素序列進(jìn)行遞增排序元素序列進(jìn)行遞增排序 if (st) /序列內(nèi)至少存在序列內(nèi)至少存在2個(gè)元素的情況個(gè)元素的情況 int i=Partition(a，s，t); QuickSort(a，s，i-1);/對(duì)左子序列遞歸排序?qū)ψ笞有蛄羞f歸排序 QuickSort(a，i+1，t);/對(duì)右子序列遞歸排序?qū)τ易有蛄羞f歸排序 【算法分析】快速快速排序的時(shí)間主要耗費(fèi)在劃分操作排序的時(shí)間主要耗費(fèi)在劃分操作上，對(duì)上，對(duì)長(zhǎng)度為長(zhǎng)度為n的區(qū)間進(jìn)行劃的區(qū)間進(jìn)行劃分，共

6、分，共需需n-1次關(guān)鍵字的比次關(guān)鍵字的比較，時(shí)較，時(shí)間復(fù)雜間復(fù)雜度為度為O(n)。對(duì)對(duì)n個(gè)記錄進(jìn)行快速排序的過程構(gòu)成一棵遞歸個(gè)記錄進(jìn)行快速排序的過程構(gòu)成一棵遞歸樹，在樹，在這樣這樣的遞歸樹的遞歸樹中，每中，每一層至多對(duì)一層至多對(duì)n個(gè)記錄進(jìn)行劃個(gè)記錄進(jìn)行劃分，所分，所花時(shí)間為花時(shí)間為O(n)。當(dāng)初始排序數(shù)據(jù)正序或反序當(dāng)初始排序數(shù)據(jù)正序或反序時(shí)，此時(shí)，此時(shí)的遞歸樹高度為時(shí)的遞歸樹高度為n，快快速排序呈現(xiàn)最壞情速排序呈現(xiàn)最壞情況，即況，即最壞情況下最壞情況下的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為O(n2)；當(dāng)初始排序數(shù)據(jù)當(dāng)初始排序數(shù)據(jù)隨機(jī)分隨機(jī)分布布，使，使每次分成的兩個(gè)子區(qū)間中的每次分成的兩個(gè)子區(qū)間中的記錄

7、個(gè)數(shù)記錄個(gè)數(shù)大致相大致相等等，此，此時(shí)的時(shí)的遞歸樹高度為遞歸樹高度為log2n，快，快速排序呈速排序呈現(xiàn)最好情現(xiàn)最好情況，即況，即最好情況下最好情況下的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為O(nlog2n)。快速。快速排序算法的排序算法的平均時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度也是也是O(nlog2n)。 已知由已知由n（n2）個(gè)）個(gè)正整數(shù)正整數(shù)構(gòu)成的集合構(gòu)成的集合A=ak（0kn），將其劃分為兩個(gè)不相交的子集），將其劃分為兩個(gè)不相交的子集A1和和A2，元素，元素個(gè)數(shù)分別是個(gè)數(shù)分別是n1和和n2， A1和和A2中元素之和分別為中元素之和分別為S1和和S2。設(shè)。設(shè)計(jì)一個(gè)盡可能計(jì)一個(gè)盡可能高效高效的劃分算法，滿足的劃分

8、算法，滿足|n1-n2|最小且最小且|S1-S2|最大。要求：最大。要求：（1）給出算法的基本設(shè)計(jì)思想。）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用）根據(jù)設(shè)計(jì)思想，采用C、C+描述算法，關(guān)鍵之描述算法，關(guān)鍵之處給出注釋。處給出注釋。（3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2016年全國(guó)計(jì)算機(jī)學(xué)科專業(yè)考研題示例22/121查找第查找第n/2小的元素小的元素遞歸快速排序 思路：將：將A遞增排序，前遞增排序，前 n/2 個(gè)元素放在個(gè)元素放在A1中，其他放中，其他放在在A2中中將最小的將最小的 n/2 個(gè)元素放在個(gè)元素放在A1中，其他放在中，其

9、他放在A2中中23/121int Partition(int a,int low,int high) /以以alow為為基準(zhǔn)劃分基準(zhǔn)劃分 int i=low,j=high; int povit=alow; while (ij) while (i=povit) j-; ai=aj; while (ij & aii)/在右區(qū)間查找在右區(qū)間查找 low=i+1; else high=i-1;/在左區(qū)間查找在左區(qū)間查找 int s1=0,s2=0; for (int i=0;in/2;i+) s1+=ai; for (int j=n/2;j2，即，即歸并操作在相鄰的多個(gè)有序子表中進(jìn)歸并操作在相

10、鄰的多個(gè)有序子表中進(jìn)行，則行，則叫多路歸并排序。叫多路歸并排序。 1. 自底向上的二路歸并排序算法例例如，對(duì)如，對(duì)于于2，5，1，7，10，6，9，4，3，8序序列，列，其其排序過程排序過程如下圖所示，圖如下圖所示，圖中方括號(hào)內(nèi)是一個(gè)有序子序列。中方括號(hào)內(nèi)是一個(gè)有序子序列。底底頂頂2，5， 1，7，10，6， 9，4， 3，83，83，82，51，76，104，93，81，2，5，74，6，9，101，2，4，5，6，7，9，101，2，3，4，5，6，7,8，9，10二路歸并排序的二路歸并排序的分治策略分治策略如下：如下：循環(huán)循環(huán) log2n 次，次，length依次取依次取1、2、log2

11、n。每次。每次執(zhí)行以下步驟：執(zhí)行以下步驟： 分解：分解：將原序列分解成將原序列分解成length長(zhǎng)度的若干子序列。長(zhǎng)度的若干子序列。 求解子問題：求解子問題：將相鄰的兩個(gè)子序列調(diào)用將相鄰的兩個(gè)子序列調(diào)用Merge算法算法合并成一個(gè)有序子序列。合并成一個(gè)有序子序列。 合并：合并：由于整個(gè)序列存放在數(shù)組中由于整個(gè)序列存放在數(shù)組中a中，排中，排序過程序過程是就地進(jìn)行是就地進(jìn)行的，合的，合并步驟不需要執(zhí)行任何操作。并步驟不需要執(zhí)行任何操作。 void Merge(int a，int low，int mid，int high)/有序表合并算法有序表合并算法alow.mid和和amid+1.highalo

12、w.high int *tmpa; int i=low，j=mid+1，k=0; tmpa=(int *)malloc(high-low+1)*sizeof(int); while (i=mid & j=high) if (ai=aj)/將第將第1子表中的元素放入子表中的元素放入tmpa中中 tmpak=ai; i+; k+; else/將第將第2子表中的元素放入子表中的元素放入tmpa中中 tmpak=aj;j+; k+; while (i=mid)/將第將第1子表余下部分復(fù)制到子表余下部分復(fù)制到tmpa tmpak=ai; i+; k+; while (j=high)/將第將第2子

13、表余下部分復(fù)制到子表余下部分復(fù)制到tmpa tmpak=aj; j+; k+; for (k=0，i=low;i=high;k+，i+) /將將tmpa復(fù)制回復(fù)制回a中中 ai=tmpak; free(tmpa);/釋放釋放tmpa所占內(nèi)存空間所占內(nèi)存空間void MergePass(int a，int length，int n)/一趟二路歸并排序一趟二路歸并排序 int i; for (i=0;i+2*length-1n;i=i+2*length) /歸并歸并length長(zhǎng)的兩相鄰子表長(zhǎng)的兩相鄰子表Merge(a，i，i+length-1，i+2*length-1); if (i+lengt

14、h-1n) /余下兩個(gè)子余下兩個(gè)子表，后表，后者長(zhǎng)度小于者長(zhǎng)度小于length Merge(a，i，i+length-1，n-1); /歸并這兩個(gè)子表歸并這兩個(gè)子表剩余剩余2個(gè)子個(gè)子表表歸并歸并的測(cè)試用例的測(cè)試用例：49 38 65 97 76 13 27 剩余剩余1個(gè)子表歸并的測(cè)試用例個(gè)子表歸并的測(cè)試用例：18,2,20,34,12,32,6,16,1,52，5，1，7，10，6，9，4，3，8void MergeSort(int a，int n)/二路歸并算法二路歸并算法 int length; for (length=1;lengthn;length=2*length)MergePass

15、(a，length，n);【算法分析】對(duì)于對(duì)于上述二路歸并排序算上述二路歸并排序算法，當(dāng)法，當(dāng)有有n個(gè)元素個(gè)元素時(shí)，需時(shí)，需要要 log2n 趟歸趟歸并，每并，每一趟歸一趟歸并，其并，其元素比較次數(shù)不超元素比較次數(shù)不超過過n-1，元，元素移動(dòng)次數(shù)都是素移動(dòng)次數(shù)都是n，因，因此歸并排序的時(shí)間復(fù)雜度為此歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。2. 自頂向下的二路歸并排序算法例例如，對(duì)如，對(duì)于于2，5，1，7，10，6，9，4，3，8序序列，說明其自頂向下的二路歸并排序的過程。列，說明其自頂向下的二路歸并排序的過程。2，5，1，7，10， 6，9，4，3，82，51, 2，57，101，2，5,

16、7, 10252，512，5，17，102，5，1，7，106，9，4，3，83，86，94, 6，93，4，6, 8, 91，2，3, 4, 5, 6, 7, 8, 9, 106，9，43，86，946971038分解分解合并合并底底頂頂設(shè)設(shè)歸并排序的當(dāng)前區(qū)間是歸并排序的當(dāng)前區(qū)間是alow.high，則，則遞歸歸并的兩遞歸歸并的兩個(gè)步驟如下：個(gè)步驟如下： 分解：分解：將序列將序列alow.high一分為一分為二，即二，即求求mid=(low+high)/2；遞歸地對(duì)兩個(gè)子序列；遞歸地對(duì)兩個(gè)子序列alow.mid和和amid+1.high進(jìn)行繼續(xù)分解。其終結(jié)條件是子序列長(zhǎng)度為進(jìn)行繼續(xù)分解。其終

17、結(jié)條件是子序列長(zhǎng)度為1（因?yàn)橐粋€(gè)元素的子表一定是有序（因?yàn)橐粋€(gè)元素的子表一定是有序表）。表）。 求解子問題：求解子問題：排序兩個(gè)子序列排序兩個(gè)子序列alow.mid和和amid+1.high。 合合并：并：與分解過程相與分解過程相反，將反，將已排序的兩個(gè)子序列已排序的兩個(gè)子序列alow.mid和和amid+1.high歸并為一個(gè)有序序列歸并為一個(gè)有序序列alow.high。對(duì)應(yīng)的二路歸并排序算法如下：對(duì)應(yīng)的二路歸并排序算法如下：void MergeSort(int a，int low，int high)/二路歸并算法二路歸并算法 int mid;if (low1容易推容易推出，出，T(n)=O

18、(nlog2n)。 【ACM、面試題】求解按求解按“最多排序最多排序”到到“最小排序最小排序”的的順序排列問題。一個(gè)序列中的順序排列問題。一個(gè)序列中的“未排序未排序”的度量是相對(duì)于彼此順的度量是相對(duì)于彼此順序不一致的條目對(duì)的數(shù)量，例如，在字母序列序不一致的條目對(duì)的數(shù)量，例如，在字母序列“DAABEC”中，該中，該度量為度量為5，因?yàn)?，因?yàn)镈大于右邊是大于右邊是4個(gè)字母，個(gè)字母，E大于其右邊的大于其右邊的1個(gè)字母。個(gè)字母。該度量稱為該序列的該度量稱為該序列的逆序數(shù)逆序數(shù)。序列。序列“AACEDGG”只有一個(gè)逆序?qū)χ挥幸粋€(gè)逆序?qū)Γ‥和和D），它幾乎被排序好了，而序列），它幾乎被排序好了，而序列“Z

19、WQM”有有6個(gè)逆序?qū)?，個(gè)逆序?qū)Γ俏磁判虻?，恰好是反序。它是未排序的，恰好是反序?你需要對(duì)若干個(gè)你需要對(duì)若干個(gè)DNA序列（僅包含序列（僅包含4個(gè)字母?jìng)€(gè)字母A、C、G和和T的字的字符串）分類，注意是分類而不是按字母順序排序，而是按照符串）分類，注意是分類而不是按字母順序排序，而是按照“最最多排序多排序”到到“最小排序最小排序”的順序排列，所有的順序排列，所有DNA序列的長(zhǎng)度都相序列的長(zhǎng)度都相同。同。輸入：輸入：第一行包含兩個(gè)整數(shù)：第一行包含兩個(gè)整數(shù)：n（0n50）表示字符串長(zhǎng)度，）表示字符串長(zhǎng)度，m（0m100）表示字符串個(gè)數(shù)。后面是表示字符串個(gè)數(shù)。后面是m行，每行包含一個(gè)長(zhǎng)度為行，每行包

20、含一個(gè)長(zhǎng)度為n的字符串。的字符串。輸出：輸出：按按“最多排序最多排序”到到“最小排序最小排序”的順序輸出所有字符串。若兩個(gè)字的順序輸出所有字符串。若兩個(gè)字符串的逆序?qū)€(gè)數(shù)相同，按原始順序輸出它們。符串的逆序?qū)€(gè)數(shù)相同，按原始順序輸出它們。輸入樣例：輸入樣例：10 6 AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT樣例輸出：樣例輸出：CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAAAACATGAAGG AAAAACGGGT3 求求逆序數(shù)逆序數(shù)AACA例

21、：AACAA AC AAAAC1AAAC#define MAXN 55#define MAXM 105/*求字符串求字符串a(chǎn)的逆序數(shù)的逆序數(shù)ans*/int ans; /全局變量全局變量,累計(jì)逆序數(shù)累計(jì)逆序數(shù)void Merge(char a,int low,int mid,int high) /兩個(gè)相鄰有序段歸并兩個(gè)相鄰有序段歸并 int i=low; int j=mid+1; int k=0; char *tmp=(char *)malloc(high-low+1)*sizeof(int); while(i=mid & jaj) tmpk+=aj+; ans+=mid-i+1; e

22、lse tmpk+=ai+; while(i=mid) tmpk+=ai+; while(j=high) tmpk+=aj+; for(int k1=0;k1alow.high alow+k1=tmpk1; free(tmp);alow ai amid alow.midamid+1 aj ahigh amid+1.high若若aiaj ans+=mid-i+1ai.midaj逆序數(shù)逆序數(shù)ans=0void Merge_sort(char a,int low,int high) /遞歸二路歸并排序遞歸二路歸并排序 if(lowhigh) int mid=(low+high)/2;Merge_so

23、rt(a,low,mid);Merge_sort(a,mid+1,high);Merge(a,low,mid,high); int Inversion(char a,int n) /二路歸并法求字符串二路歸并法求字符串a(chǎn)的逆序數(shù)的逆序數(shù) ans=0; Merge_sort(a,0,n-1); return ans;/*/typedef struct int v;/存放存放stri的逆序數(shù)的逆序數(shù) int i;/存放字符串的下標(biāo)存放字符串的下標(biāo)i ElemType;/聲明數(shù)組聲明數(shù)組b的元素類型的元素類型struct Cmp/定義排序關(guān)系函數(shù)定義排序關(guān)系函數(shù) bool operator()(co

24、nst ElemType &s,const ElemType &t) const return s.vt.v; /指定按逆序數(shù)遞增排序指定按逆序數(shù)遞增排序;int main() int i,n,m; char strMAXMMAXN; ElemType bMAXM; memset(b,0,sizeof(b); char tmpMAXN; scanf(%d%d,&n,&m);/輸入輸入n和和m for (i=0;im;i+)/輸入輸入m個(gè)字符串個(gè)字符串 scanf(%s,stri); for (i=0;im;i+)/求所有字符串的逆序數(shù)求所有字符串的逆序數(shù) str

25、cpy(tmp,stri);/由于保存原序列不變由于保存原序列不變,臨時(shí)復(fù)制到臨時(shí)復(fù)制到tmp中中 bi.v=Inversion(tmp,n);/求求tmp的逆序?qū)€(gè)數(shù)的逆序?qū)€(gè)數(shù) bi.i=i;/記錄原來的下標(biāo)記錄原來的下標(biāo) stable_sort(b,b+m,Cmp();/采用穩(wěn)定的排序算法采用穩(wěn)定的排序算法 for (i=0;irmax1，則，則max1=lmax1，max2=MAXlmax2，rmax1；例如：例如：（ 4, 6, 3, 2, 5, 1 ）否則否則max1=rmax1，max2=MAXlmax1，rmax2。例如（例如（2, 5, 1, 4, 6, 3）void sol

26、ve(int a,int low,int high,int &max1,int &max2) if (low=high)/區(qū)間只有一個(gè)元素區(qū)間只有一個(gè)元素 max1=alow;max2=-INF; else if (low=high-1)/區(qū)間只有兩個(gè)元素區(qū)間只有兩個(gè)元素 max1=max(alow,ahigh); max2=min(alow,ahigh); else/區(qū)間有兩個(gè)以上元素區(qū)間有兩個(gè)以上元素 int mid=(low+high)/2;int lmax1,lmax2;solve(a,low,mid,lmax1,lmax2); /左區(qū)間求左區(qū)間求lmax1和和lmax

27、2int rmax1,rmax2;solve(a,mid+1,high,rmax1,rmax2); /右區(qū)間求右區(qū)間求lmax1和和lmax2if (lmax1rmax1) max1=lmax1; max2=max(lmax2,rmax1);/lmax2,rmax1中求次大元素中求次大元素else max1=rmax1; max2=max(lmax1,rmax2);/lmax1,rmax2中求次大元素中求次大元素 【算法分析】對(duì)于對(duì)于solve(a，0，n-1，max1，max2)調(diào)用，其比較次數(shù)的遞推式為：調(diào)用，其比較次數(shù)的遞推式為： T(1)=T(2)=1 T(n)=2T(n/2)+1 /

28、合并的時(shí)間為合并的時(shí)間為O(1)可以推導(dǎo)出可以推導(dǎo)出T(n)=O(n)?；舅悸罚涸O(shè)設(shè)alow.high是當(dāng)前的查找區(qū)是當(dāng)前的查找區(qū)間，首間，首先確定先確定該區(qū)間的中點(diǎn)位置該區(qū)間的中點(diǎn)位置mid= (low+high)/2 ；然后將待查的；然后將待查的k值與值與amid.key比較：比較： （1）若）若k=amid，則，則查找成功并返回該元素的物理下標(biāo)；查找成功并返回該元素的物理下標(biāo)； （2）若）若kamid，則，則要查找的要查找的k必在位于右子表必在位于右子表amid+1.high中，即中，即新的查找區(qū)間是右子表新的查找區(qū)間是右子表amid+1.high。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。

29、下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。int BinSearch(int a，int low，int high，int k) int mid; if (lowk)/當(dāng)當(dāng)amidk時(shí)時(shí)return BinSearch(a，low，mid-1，k);else/當(dāng)當(dāng)amidk時(shí)時(shí) return BinSearch(a，mid+1，high，k); else return -1;/若當(dāng)前查找區(qū)間沒有元素時(shí)返回若當(dāng)前查找區(qū)間沒有元素時(shí)返回-1拆半查找拆半查找算法算法實(shí)現(xiàn)實(shí)現(xiàn)：算法分析：折半查找算法的主要時(shí)間花費(fèi)在元素比較折半查找算法的主要時(shí)間花費(fèi)在元素比較上，上，對(duì)對(duì)于含有于含有n個(gè)元素的有序個(gè)元素的有序

30、表，采表，采用折半查找時(shí)最壞情況下的用折半查找時(shí)最壞情況下的元素比較次數(shù)為元素比較次數(shù)為C(n)，則，則有：有：C(n)=1當(dāng)當(dāng)n=1C(n)1+C( n/2 ) 當(dāng)當(dāng)n2由此得到由此得到：C(n) log2n +1折半查找的主要時(shí)間花在元素比較折半查找的主要時(shí)間花在元素比較上，所上，所以算法的時(shí)間以算法的時(shí)間復(fù)雜度為復(fù)雜度為O(log2n)。 時(shí)間復(fù)雜度推導(dǎo)及折半查找的時(shí)間復(fù)雜度推導(dǎo)及折半查找的非遞歸算法非遞歸算法見教材見教材P93-94折半查找你真的會(huì)了嗎？據(jù)說據(jù)說90%的程序員編寫的折半查找程序都有的程序員編寫的折半查找程序都有bug!當(dāng)有序數(shù)組中存在相同元素當(dāng)有序數(shù)組中存在相同元素x時(shí)

31、，如何查找最左邊的時(shí)，如何查找最左邊的x ？當(dāng)有序數(shù)組中存在相同元素當(dāng)有序數(shù)組中存在相同元素x時(shí)，如何查找最右邊的時(shí)，如何查找最右邊的x ？當(dāng)有序數(shù)組中存在相同元素當(dāng)有序數(shù)組中存在相同元素x時(shí)，如何求時(shí)，如何求x的個(gè)數(shù)的個(gè)數(shù) ？【問題描述】對(duì)于對(duì)于給定的含有給定的含有n元素的無序序元素的無序序列，求列，求這這個(gè)序列中第個(gè)序列中第k（1kn）小的元素。）小的元素。【問題求解】假設(shè)假設(shè)無序序列存放在無序序列存放在a0.n-1中，若中，若將將a遞增排遞增排序，則序，則第第k小的元素為小的元素為ak-1。采用類似于采用類似于快速排序快速排序的思想。的思想。對(duì)于序列對(duì)于序列as.t，在，在其中查找第其中

32、查找第k小元素小元素的過程如下：的過程如下：將將as作為基準(zhǔn)劃分，其對(duì)應(yīng)下標(biāo)為作為基準(zhǔn)劃分，其對(duì)應(yīng)下標(biāo)為i。3種情況種情況：該元素的下標(biāo)為k-1若若k-1=i，ai即為所求，返回即為所求，返回ai。若若k-1i，第，第k小的元素應(yīng)在小的元素應(yīng)在ai+1.t子序列中，子序列中，遞歸在該子序列中求解并返回其結(jié)果。遞歸在該子序列中求解并返回其結(jié)果。算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：int QuickSelect(int a，int s，int t，int k)/在在as.t序列中找第序列中找第k小的元素小的元素 int i=s，j=t,tmp; if (si & aj=tmp) j-;ai=aj; /將將

33、aj前移到前移到ai的位置的位置while (ij & ai=tmp) i+;aj=ai; /將將ai后移到后移到aj的位置的位置 ai=tmp; if (k-1=i) return ai; else if (k-1i) return QuickSelect(a，s，i-1，k); /在左區(qū)間中遞歸查找在左區(qū)間中遞歸查找 else return QuickSelect(a，i+1，t，k); /在右區(qū)間中遞歸查找在右區(qū)間中遞歸查找 else if (s=t & s=k-1)/區(qū)間內(nèi)只有一個(gè)元素且為區(qū)間內(nèi)只有一個(gè)元素且為ak-1 return ak-1;測(cè)試用例：測(cè)試用例： 2，

34、5，1，7，10，6，9，4，3，8【算法分析】對(duì)于對(duì)于QuickSelect(a，s，t，k)算算法法，設(shè)設(shè)序列序列a中含有中含有n個(gè)元個(gè)元素素，其其比較次數(shù)的遞推式為：比較次數(shù)的遞推式為：T(n)=T(n/2)+O(n)可以推導(dǎo)出可以推導(dǎo)出T(n)=O(n)，這，這是是最好的情最好的情況況，即，即每次劃分每次劃分的基準(zhǔn)恰好是中位的基準(zhǔn)恰好是中位數(shù)，將數(shù)，將一個(gè)序列劃分為長(zhǎng)度大致相等的兩一個(gè)序列劃分為長(zhǎng)度大致相等的兩個(gè)子序列。個(gè)子序列。在在最壞情況最壞情況下，每下，每次劃分的基準(zhǔn)恰好是序列中的最大值次劃分的基準(zhǔn)恰好是序列中的最大值或最小或最小值，則值，則處理區(qū)間只比上一次減少處理區(qū)間只比上一

35、次減少1個(gè)元個(gè)元素，此素，此時(shí)比較時(shí)比較次數(shù)為次數(shù)為O(n2)。在在平均情況平均情況下該算法的時(shí)間復(fù)雜度為下該算法的時(shí)間復(fù)雜度為O(n)?！締栴}描述】對(duì)于對(duì)于一個(gè)長(zhǎng)度為一個(gè)長(zhǎng)度為n的有序序列（假設(shè)均的有序序列（假設(shè)均為升序序列）為升序序列）a0.n-1，處，處于于中間位置的元素稱為中間位置的元素稱為a的的中位數(shù)中位數(shù)。 設(shè)計(jì)一個(gè)算法求給定的兩個(gè)有序序列的中位數(shù)。設(shè)計(jì)一個(gè)算法求給定的兩個(gè)有序序列的中位數(shù)。 例例如，若如，若序列序列a=(11，13，15，17，19)，其，其中位數(shù)中位數(shù)是是15，若，若b=(2，4，6，8，20)，其，其中位數(shù)為中位數(shù)為6。兩個(gè)等長(zhǎng)。兩個(gè)等長(zhǎng)有序序列的中位數(shù)是含它

36、們所有元素的有序序列的中位有序序列的中位數(shù)是含它們所有元素的有序序列的中位數(shù)，數(shù)，例例如如a、b兩個(gè)有序序列的中位數(shù)為兩個(gè)有序序列的中位數(shù)為11。a=(11，13，15，17，19) b=(2，4，6，8，20)c=(2，4，6，8，11，12，15，17，19，20)【問題求解】對(duì)于對(duì)于含有含有n個(gè)元素的有序序列個(gè)元素的有序序列as.t，當(dāng)，當(dāng)n為奇為奇數(shù)數(shù)時(shí)，中時(shí)，中位數(shù)是出現(xiàn)在位數(shù)是出現(xiàn)在m= (s+t)/2 處；當(dāng)處；當(dāng)n為偶為偶數(shù)數(shù)時(shí)，中時(shí)，中位數(shù)下標(biāo)有位數(shù)下標(biāo)有m= (s+t)/2 （下中位）和（下中位）和m= (s+t)/2 +1（上中位）兩個(gè)。為了（上中位）兩個(gè)。為了簡(jiǎn)簡(jiǎn)單，單

37、，僅僅考慮中位數(shù)為考慮中位數(shù)為m= (s+t)/2 處。處。a=(11，13，15，17，19)b=(2， 4， 6， 8，20)0 1 2 3 40 1 2 3 4c=(2， 4， 6， 8， 11，12，15，17，19，20)0 1 2 3 4 5 6 7 8 9m= (s+t)/2 =4m= (s+t)/2 =2m= (s+t)/2 =2采采用用二分法二分法求含有求含有n個(gè)有序元素的序列個(gè)有序元素的序列a、b的中位數(shù)的過程如下：的中位數(shù)的過程如下：855若若n=1，較小者為中位數(shù)。，較小者為中位數(shù)。其他又分為其他又分為3種情況。種情況。分別求出分別求出a、b的中位數(shù)的中位數(shù)am1和和b

38、m2： 若若am1=bm2，則，則am1或或bm2即為所求中即為所求中位位數(shù)，算數(shù)，算法結(jié)束法結(jié)束。 1，3，5，6，92，3，5，8，105 若若am1bm2，則，則舍棄序列舍棄序列a中后半部分（較大的中后半部分（較大的一一半半），同），同時(shí)舍棄序列時(shí)舍棄序列b中前半部分（較小的中前半部分（較小的一一半半），要），要求舍棄的長(zhǎng)度求舍棄的長(zhǎng)度相相等。舍棄一等。舍棄一半即半即 n/2 個(gè)元素。個(gè)元素。1，3，5，6，92，3，4，8，105，6，94，8，104繼續(xù)求int (int a，int s1，int t1，int b，int s2，int t2) /求兩個(gè)有序序列求兩個(gè)有序序列as1.

39、t1和和bs2.t2的中位數(shù)的中位數(shù)int m1，m2;if (s1=t1 & s2=t2) /兩序列只有一個(gè)元素時(shí)返回較小者兩序列只有一個(gè)元素時(shí)返回較小者return as1bs2?as1:bs2;else m1=(s1+t1)/2;/求求a的中位數(shù)的中位數(shù) m2=(s2+t2)/2;/求求b的中位數(shù)的中位數(shù) if (am1=bm2)/兩中位數(shù)相等時(shí)返回該中位數(shù)兩中位數(shù)相等時(shí)返回該中位數(shù)return am1; if (am1bm2)/當(dāng)當(dāng)am1bm2時(shí)時(shí) prepart(s1，t1);/a取前半部分取前半部分 postpart(s2，t2);/b取后半部分取后半部分 return (

40、a，s1，t1，b，s2，t2); 【算法分析】對(duì)于對(duì)于含有含有n個(gè)元素的有序序列個(gè)元素的有序序列a和和b，設(shè)，設(shè)調(diào)調(diào)用用midnum(a，0，n-1，b，0，n-1)求求中位數(shù)的執(zhí)行時(shí)間為中位數(shù)的執(zhí)行時(shí)間為T(n)，顯，顯然然有以下遞歸式：有以下遞歸式：T(n)=1當(dāng)當(dāng)n=1T(n)=T(n/2)+1當(dāng)當(dāng)n1容易推容易推出，出，T(n)=O(log2n)。3.4 求解組合問題求解組合問題 【問題描述】給定一個(gè)有給定一個(gè)有n（n1）個(gè)整數(shù)的序列，要求求出其中最）個(gè)整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。大連續(xù)子序列的和。 例如例如： 序列（序列（-2，11，-4，13，-5，-2）的最大子

41、序列和為）的最大子序列和為20 序列（序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子）的最大子序列和為序列和為16。 規(guī)定一個(gè)序列最大連續(xù)子序列和至少是規(guī)定一個(gè)序列最大連續(xù)子序列和至少是0（長(zhǎng)度為（長(zhǎng)度為0的子序列）的子序列），如果小于如果小于0，其結(jié)果為，其結(jié)果為0。 【問題求解】對(duì)于含有對(duì)于含有n個(gè)整數(shù)的序列個(gè)整數(shù)的序列a0.n-1，若，若n=1，表示該序，表示該序列僅含一個(gè)元素，如果該元素大于列僅含一個(gè)元素，如果該元素大于0，則返回該元素；否則返回，則返回該元素；否則返回0。 若若n1，采用分治法求解最大連續(xù)子序列時(shí)，取其中間位置，采用分治法求解最大連續(xù)子序列

42、時(shí)，取其中間位置mid= (n-1)/2 ，該子序列只可能出現(xiàn)，該子序列只可能出現(xiàn)3個(gè)地方。個(gè)地方。 （1）該子序列完全落在左半部即）該子序列完全落在左半部即a0.mid中。采用遞歸求出其最大中。采用遞歸求出其最大連續(xù)子序列和連續(xù)子序列和maxLeftSum。a0 a1 ai amidmaxLeftSum （2）該子序列完全落在右半部即）該子序列完全落在右半部即amid+1.n-1中。采用遞歸求出中。采用遞歸求出其最大連續(xù)子序列和其最大連續(xù)子序列和maxRightSum。amid+1 amid+2 aj an-1maxRightSum（3）該）該子序列跨越序列子序列跨越序列a的中部而占據(jù)左右兩

43、部的中部而占據(jù)左右兩部分分。1 -2 3 5 2 -1 5 -3n=8，mid=(0+7)/2=386 max(8,6)=8? 1 -2 3 5 2 -1 5 -386跨越序列跨越序列a的中部：的中部：amid左、右左、右最大連續(xù)子序列最大連續(xù)子序列和的和的+ 8+6=14max3(8,6,14)=14ai ai+1 amidamid+1 aj maxLeftSummaxRightSum結(jié)果：max3( maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum )maxLeftBorderSummaxRightBorderSum考慮

44、該子序列跨越序列考慮該子序列跨越序列amid元素的情況元素的情況long (int a，int left，int right)/求求aleft.high序列中最大連續(xù)子序列和序列中最大連續(xù)子序列和 int i，j; long maxLeftSum，maxRightSum; long maxLeftBorderSum，leftBorderSum; long maxRightBorderSum，rightBorderSum; if (left=right)/子序列只有一個(gè)元素時(shí)子序列只有一個(gè)元素時(shí) if (aleft0) /該元素大于該元素大于0時(shí)返回它時(shí)返回它return aleft;else/

45、該元素小于或等于該元素小于或等于0時(shí)返回時(shí)返回0return 0; int mid=(left+right)/2;/求中間位置求中間位置maxLeftSum=(a，left，mid);/求左邊求左邊maxRightSum=(a，mid+1，right); /求右邊求右邊maxLeftBorderSum=0，leftBorderSum=0;for (i=mid;i=left;i-)/求出以左邊加上求出以左邊加上amid元素元素 leftBorderSum+=ai;/構(gòu)成的序列的最大和構(gòu)成的序列的最大和 if (leftBorderSummaxLeftBorderSum)maxLeftBorder

46、Sum=leftBorderSum;maxRightBorderSum=0，rightBorderSum=0;for (j=mid+1;jmaxRightBorderSum)maxRightBorderSum=rightBorderSum;return max3(maxLeftSum，maxRightSum， maxLeftBorderSum+maxRightBorderSum); 【算法分析】設(shè)設(shè)求解序列求解序列a0.n-1最大連續(xù)子序列和的執(zhí)行時(shí)間最大連續(xù)子序列和的執(zhí)行時(shí)間為為T(n)，第（，第（1）、（）、（2）兩）兩種情況的執(zhí)行時(shí)間為種情況的執(zhí)行時(shí)間為T(n/2)，第（，第（3）種）種

47、情情況的執(zhí)行時(shí)間為況的執(zhí)行時(shí)間為O(n)，所，所以得到以下遞推式：以得到以下遞推式：T(n)=1當(dāng)當(dāng)n=1T(n)=2T(n/2)+n當(dāng)當(dāng)n1容易推容易推出，出，T(n)=O(nlog2n)。 【問題描述】有一個(gè)有一個(gè)2k2k（k0）的棋盤，恰好有一個(gè)方格）的棋盤，恰好有一個(gè)方格與其他方格不同，稱之為特殊方格。現(xiàn)在要用如與其他方格不同，稱之為特殊方格。現(xiàn)在要用如下下的的L型骨牌覆蓋型骨牌覆蓋除了特殊方格外的其他全部方格，骨牌可以任意旋轉(zhuǎn)，并且任何兩除了特殊方格外的其他全部方格，骨牌可以任意旋轉(zhuǎn)，并且任何兩個(gè)骨牌不能重疊。請(qǐng)給出一種覆蓋方法。個(gè)骨牌不能重疊。請(qǐng)給出一種覆蓋方法。 【問題求解】棋盤

48、中的方格數(shù)棋盤中的方格數(shù)=2k2k=4k，覆蓋使用的，覆蓋使用的L型骨牌個(gè)數(shù)型骨牌個(gè)數(shù)=(4k-1)/3。 采用的方法是：將棋盤劃分為采用的方法是：將棋盤劃分為4個(gè)大小相同個(gè)大小相同4個(gè)象限，根據(jù)特殊方格的個(gè)象限，根據(jù)特殊方格的位置位置（dr，dc），在中間位置放置一個(gè)合適的，在中間位置放置一個(gè)合適的L型骨牌。型骨牌。 例如，如例如，如下下圖所示，特殊方格在左上角象限中，在中間放置一個(gè)覆蓋圖所示，特殊方格在左上角象限中，在中間放置一個(gè)覆蓋其他其他3個(gè)象限中各一個(gè)方格的個(gè)象限中各一個(gè)方格的L型骨牌。型骨牌。其他情況類似！其他情況類似！特殊方格在左上角象限特殊方格在左上角象限（dr，dc）放置一個(gè)

49、放置一個(gè)L型骨牌型骨牌中間位置中間位置k=3，n=23=8333444888999222777555666101010111111111131313141414181818191919121212171717151515161616202020212121左上角左上角象限象限右上角右上角象限象限右下角右下角象限象限左下角左下角象限象限 用用（tr，tc）表示一個(gè)象限左上角方格的坐標(biāo)，表示一個(gè)象限左上角方格的坐標(biāo)，（dr，dc）是特殊是特殊方格所在的坐標(biāo)，方格所在的坐標(biāo)，size是棋盤的行數(shù)和列數(shù)。是棋盤的行數(shù)和列數(shù)。 用二維數(shù)組用二維數(shù)組board存放覆蓋方案，用存放覆蓋方案，用tile全局變

50、量表示全局變量表示L型骨牌的編型骨牌的編號(hào)（從整數(shù)號(hào)（從整數(shù)1開始），開始），board中中3個(gè)相同的整數(shù)表示一個(gè)個(gè)相同的整數(shù)表示一個(gè)L型骨牌。型骨牌。(tr,tc)(dr,dc)ss左上角（行左上角（行, ,列）列）#include#define MAX 1025/問題表示問題表示int k;/棋盤大小棋盤大小int x,y;/特殊方格的位置特殊方格的位置/求解問題表示求解問題表示int boardMAXMAX;int tile=1;void ChessBoard(int tr,int tc,int dr,int dc,int size) if(size=1) return;/遞歸出口遞歸出

51、口 int t=tile+;/取一個(gè)取一個(gè)L型骨，其牌號(hào)為型骨，其牌號(hào)為tile int s=size/2;/分割棋盤分割棋盤 /考慮左上角象限考慮左上角象限 if(drtr+s & dctc+s)/特殊方格在此象限中特殊方格在此象限中ChessBoard(tr,tc,dr,dc,s); else/此象限中無特殊方格此象限中無特殊方格 boardtr+s-1tc+s-1=t;/用用t號(hào)號(hào)L型骨牌覆蓋右下角型骨牌覆蓋右下角ChessBoard(tr,tc,tr+s-1,tc+s-1,s);/將右下角作為特殊方格繼續(xù)處理該象限將右下角作為特殊方格繼續(xù)處理該象限 s(tr,tc)(dr,dc

52、)s(tr,tc)(tr+s-1,tc+s-1)ss(tr,tc) /考慮右上角象限考慮右上角象限 if(dr=tc+s) ChessBoard(tr,tc+s,dr,dc,s);/特殊方格在此象限中特殊方格在此象限中 else/此象限中無特殊方格此象限中無特殊方格 boardtr+s-1tc+s=t;/用用t號(hào)號(hào)L型骨牌覆蓋左下角型骨牌覆蓋左下角ChessBoard(tr,tc+s,tr+s-1,tc+s,s); /將左下角作為特殊方格繼續(xù)處理該象限將左下角作為特殊方格繼續(xù)處理該象限 (tr,tc)s(tr,tc+s)(dr,dc)s(tr,tc+s)(tr+s-1,tc+s)ss /處理左

53、下角象限處理左下角象限 if(dr=tr+s & dc=tr+s & dc=tc+s)/特殊方格在此象限中特殊方格在此象限中 ChessBoard(tr+s,tc+s,dr,dc,s); else/此象限中無特殊方格此象限中無特殊方格 boardtr+stc+s=t; /用用t號(hào)號(hào)L型骨牌覆蓋左上角型骨牌覆蓋左上角ChessBoard(tr+s,tc+s,tr+s,tc+s,s); /將左上角作為特殊方格繼續(xù)處理該象限將左上角作為特殊方格繼續(xù)處理該象限 (tr,tc)k=3，n=23=83344889932048779522610107115566110111113131411

54、1819191312141418181719151212162017172115151616202021213.4.3 求解循環(huán)日程安排問題 【問題描述】設(shè)有設(shè)有n=2k個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：一個(gè)滿足以下要求的比賽日程表： （1）每個(gè)選手必須與其他）每個(gè)選手必須與其他n-1個(gè)選手各賽一次。個(gè)選手各賽一次。 （2）每個(gè)選手一天只能賽一次。）每個(gè)選手一天只能賽一次。 （3）循環(huán)賽在）循環(huán)賽在n-1天之內(nèi)結(jié)束。天之內(nèi)結(jié)束。 【問題求解】按問題要求可將比賽日程表設(shè)計(jì)成一個(gè)按問題要求可將比賽日程表設(shè)計(jì)成一個(gè)n行行n-1列列的二維表，

55、其中第的二維表，其中第i行、第行、第j列表示和第列表示和第i個(gè)選手在第個(gè)選手在第j天比賽的選手。天比賽的選手。 假設(shè)假設(shè)n位選手被順序編號(hào)為位選手被順序編號(hào)為1、2、n（2k）。）。2211k=1k=222114433左上角左上角左左下下角角右上右上角角右下右下角角44332211人為添加的人為添加的表示表示選手選手1與與選手選手2比賽比賽加加2k-1=2由由k=1創(chuàng)建創(chuàng)建k=2的過程的過程k=2左上角左上角左左下下角角右上右上角角右下右下角角2211443344332211由由k=2創(chuàng)建創(chuàng)建k=3的過程的過程22114433443322116655887788776655k=3加加2k-1=

56、422114433443322116655887788776655 將將n=2k問題劃分為問題劃分為4部分：部分： （1）左上角左上角：左上角為：左上角為2k-1個(gè)選手在前半程的比賽日程（個(gè)選手在前半程的比賽日程（k=1時(shí)直接給時(shí)直接給出，否則，上一輪求出的就是出，否則，上一輪求出的就是2k-1個(gè)選手的比賽日程）。個(gè)選手的比賽日程）。 （2）左下角左下角：左下角為另：左下角為另2k-1個(gè)選手在前半程的比賽日程，由左上角加個(gè)選手在前半程的比賽日程，由左上角加2k-1得到，例如得到，例如22個(gè)選手比賽，左下角由左上角直接加個(gè)選手比賽，左下角由左上角直接加2（2k-1）得到，）得到，23個(gè)個(gè)選手比賽

57、，左下角由左上角直接加選手比賽，左下角由左上角直接加4（2k-1）得到。）得到。 （3）右上角右上角：將左下角直接復(fù)制到右上角得到另：將左下角直接復(fù)制到右上角得到另2k-1個(gè)選手在后半程的個(gè)選手在后半程的比賽日程。比賽日程。 （4）右下角右下角：將左上角直接復(fù)制到右下角得到：將左上角直接復(fù)制到右下角得到2k-1個(gè)選手在后半程的比個(gè)選手在后半程的比賽日程。賽日程。#include #define MAX 101/問題表示問題表示int k;/求解結(jié)果表示求解結(jié)果表示int aMAXMAX;/存放比賽日程表（行列下標(biāo)為存放比賽日程表（行列下標(biāo)為0的元素不用）的元素不用）void Plan(int

58、k) int i,j,n,t,temp; n=2;/n從從21=2開始開始 a11=1; a12=2; /求解求解2個(gè)選手比賽日程個(gè)選手比賽日程,得到得到左上角左上角元素元素 a21=2; a22=1; for (t=1;tk;t+)/迭代處理迭代處理22(t=1),2k(t=k-1)個(gè)選手個(gè)選手 temp=n;/temp=2tn=n*2; /n=2(t+1)for (i=temp+1;i=n;i+ )/填填左下角左下角元素元素 for (j=1; j=temp; j+)aij=ai-tempj+temp; /產(chǎn)生產(chǎn)生左下角元素左下角元素for (i=1; i=temp; i+)/填填右上角右

59、上角元素元素 for (j=temp+1; j=n; j+)aij=ai+temp(j+temp)% n;for (i=temp+1; i=n; i+)/填填右下角右下角元素元素 for (j=temp+1; j1由此可得由此可得T(n)=O(n2)。采用分治法，采用分治法，把把X*Y寫成另一種形式：寫成另一種形式： X*Y=A*C*2n+(A-B)*(D-C)+A*C+B*D*2n/2+B*D雖然該式看起來比前式復(fù)雜些，但它僅需做雖然該式看起來比前式復(fù)雜些，但它僅需做3次次n/2位整數(shù)的位整數(shù)的乘法（乘法（A*C、B*D和和(A-B)*(D-C)），），6次加、減法和次加、減法和2次移位。次

60、移位。由此可以推出由此可以推出： T(n) = O(n1.59) （log23=1.59）【問題描述】對(duì)于對(duì)于兩個(gè)兩個(gè)nn的矩陣的矩陣A和和B，計(jì)計(jì)算算C=AB。【問題求解】常用常用的計(jì)算公式是的計(jì)算公式是Cij = ，對(duì)對(duì)應(yīng)算法應(yīng)算法的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為O(n3)。是否存在更有效的算法呢？假設(shè)是否存在更有效的算法呢？假設(shè)n=2k，考考慮采用分治法思慮采用分治法思路路，當(dāng)當(dāng)n2時(shí)時(shí)，將將A、B分成分成4個(gè)個(gè)n/2n/2的矩陣：的矩陣：nkkjikBA1222112112221121122211211CCCC，CBBBB，BAAAAA利用塊矩陣的乘利用塊矩陣的乘法法，矩矩陣陣C可表示為可表示為22221221212211212212121121121111BABABABABABABABAC2222122121221