大三01算法設(shè)計(jì)第六講

1、Algorithms Design Techniques and Analysis第六章 分 治Algorithms Design Techniques and Analysis本章主要內(nèi)容分治基本概念引言 兩個(gè)簡單例子二分搜索合并排序分治范式分治策略解決的一些問題選擇算法快速排序大整數(shù)乘法矩陣乘法最近點(diǎn)問題Algorithms Design Techniques and Analysis6.1 引言什么是分治算法形式?一個(gè)分治算法把問題實(shí)例劃分成若干子實(shí)例(多數(shù)情況是分成兩個(gè))；并分別遞歸地解決每個(gè)子實(shí)例；然后把這些子實(shí)例的解組合起來，得到原問題實(shí)例的解；Algorithms Design

2、Techniques and Analysis尋找最大值和最小值 問題描述在一個(gè)整數(shù)組A1.n中，同時(shí)尋找最大值和最小值。為了簡化問題，不妨假定n是2的整數(shù)冪。一種直接的算法如下1. xA1; yA12. for i2 to n3. if Aiy then yAi5. end for6. return (x,y) 顯然，由此方法執(zhí)行的元素比較次數(shù)是2n一2是否存在更有效的算法?Algorithms Design Techniques and Analysis分治方法基本思想 將數(shù)組分割成兩半， A1.n/2 和A(n/2) + 1.n；在每一半中找到最大值和最小值；并返回這兩個(gè)最小值中的最小值

3、及這兩個(gè)最大值中的最大值；Algorithms Design Techniques and Analysis算法6.1 MINMAX輸入: n個(gè)整數(shù)元素的數(shù)組A1.n ，n為2的冪。輸出: (x,y): A中的最大元素和最小元素。 1. minmax(1,n)過程 minmax(low,high) 1. if high-low=1 then 數(shù)組只有2個(gè)值的情況 2. if AlowAhigh then return (Alow,Ahigh) 3. else return (Ahigh, Alow) 4. end if 5. else 6. mid (low+high)/2 7. (x1,y1

4、)minmax(low,mid) 8. (x2,y2)minmax(mid+1,high) 9. xmin(x1,x2) 10. ymax(y1,y2) 11. return(x,y) 12. end if Algorithms Design Techniques and Analysis算法分析設(shè)C(n)表示算法在由n個(gè)元素(n是2的整數(shù)冪)組成的數(shù)組上執(zhí)行的元素比較次數(shù)。見P112 定理 6.1 設(shè)數(shù)組A1.n包含n個(gè)元素，其中n是2的冪，則僅用3n/2一2次元素比較就能夠在數(shù)組A中找出最大和最小元素。Algorithms Design Techniques and Analysis6.2

5、 二分搜索 問題描述在數(shù)組A1.n中搜索已知元素x基本思想將一個(gè)給定的元素x與一個(gè)已排序數(shù)組Alow.high.的中間元素做比較如果x Amid，則放棄Alow.mid，而對(duì)Amid+1.high重復(fù)實(shí)施相同的方法.Algorithms Design Techniques and Analysis算法6.2 BINARYSEARCHREC輸入: 按非降序排列的n個(gè)元素的數(shù)組A1.n和元素x。輸出:如果x=Aj，1j n，則輸出j；否則輸出0 1. binarysearch(1,n)過程 binarysearch(low,high) 1. if lowhigh then return 0 2.

6、else 3. mid (low+high)/2 4. if x=Amid then return mid 5. else if xAmid then return binarysearch(low,mid-1) 6. else return binarysearch(mid+1,high) 7. end ifAlgorithms Design Techniques and Analysis算法分析 假設(shè) 為了求出算法的執(zhí)行時(shí)間，我們計(jì)算元素間的比較次數(shù)，因?yàn)檫@是一個(gè)基本運(yùn)算，也就是說，算法的執(zhí)行時(shí)間與完成元素間比較次數(shù)是成比例的(見1.11.2節(jié))。我們將假定每個(gè)三向比較當(dāng)做一次比較來計(jì)算推

7、導(dǎo)見P113 定理6.2算法BINARYSEARCHREC在n個(gè)元素組成的數(shù)組中搜索某個(gè)元素所執(zhí)行的元素比較次數(shù)不超過logn+1。算法BINARYSEARCHREC的時(shí)間復(fù)雜性是O(logn)。 算法遞歸深度為O(log n)，并且由于每個(gè)遞歸層次需要 (l)的空間，本算法所需的空間總量是(log n)。和遞歸算法相反，其迭代形式算法僅需要 (l)空間Algorithms Design Techniques and Analysis6.3 合并排序BOTTOMUPSORT :在每一層中，我們有已排序的序列對(duì)，同時(shí)它們兩兩被合并而得到較大的排序序列。沿著樹一層一層向上繼續(xù)這個(gè)過程，直到到達(dá)根為

8、止，這最后的序列是已經(jīng)排序好的。 讓我們從反向來考慮，是否能用自頂向下取代自底向上？Algorithms Design Techniques and Analysis合并排序 基本思想首先，將該數(shù)組分成兩個(gè)各一半元素的數(shù)組接著分別對(duì)這兩個(gè)數(shù)組的元素排序然后只是將它們合并來得到所希望的排序數(shù)組至于對(duì)每一半子數(shù)組，可隨意使用任何排序算法來對(duì)這兩個(gè)子數(shù)組排序。特別是可以使用算法SORT本身。如果這樣，我們實(shí)際上得出了著名的算法MERGESORT，此算法的完整描述見下面。Algorithms Design Techniques and Analysis算法6.3 Mergesort輸入: n個(gè)元素的數(shù)

9、組A1.n。輸出:按非降序排列的數(shù)組A1.n。1. mergesort(A,1,n)過程 mergesort(A,low,high)1. if lowhigh then2.mid (low+high)/23.mergesort(A,low,mid)4.mergesort(A,mid+1,high)5.MERGE(A,low,mid,high)6. end if Algorithms Design Techniques and Analysis6.3.1 算法的操作過程?算法MERGESORT對(duì)下列數(shù)組A排序的操作過程： A=9,4,5,2,1,7,4,6.定義mergesort(A, low,

10、 high) 為 MS(low, high). Merge(A, low, mid, high) 為 M(low, mid, high).Algorithms Design Techniques and AnalysisMERGESORT算法過程9452174612445679945224591746146749942552171746469944552211774466Success!MS(1,8)MS(1,4)MS(1,2)MS(1,1)M(1,1,1)MS(2,2)M(2,2,2)M(1,1,2)MS(3,4)MS(3,3)M(3,3,3)MS(4,4)M(4,4,4)M(3,3,4)M

11、(1,2,4)MS(5,8)MS(5,6)MS(5,5)M(5,5,5)MS(6,6)M(6,6,6)M(5,5,6)MS(7,8)M(7,7,8)M(7,7,7)M(8,8,8)M(5,6,8)MS(7,7)MS(8,8)M(1,4,8)Algorithms Design Techniques and AnalysisHow the algorithm works?這個(gè)調(diào)用鏈對(duì)應(yīng)于樹的前序遍歷:訪問根、左子樹和右子樹。計(jì)算卻對(duì)應(yīng)于樹的后序遍歷:訪問左子樹，右子樹，最后是根。為了實(shí)現(xiàn)這個(gè)遍歷，用一個(gè)棧來存儲(chǔ)每次調(diào)用過程的局部數(shù)據(jù)。在算法BOTPOMUPSORT中，合并是一層接一層進(jìn)行的;而在算

12、法MERGESORT中，合并是以后序遍歷的方式進(jìn)行的。兩種算法的區(qū)別僅在于合并的次序，因此，當(dāng)n是2的冪時(shí)，由算法MERGESORT執(zhí)行的比較次數(shù)和算法BOTIOMUPSORT執(zhí)行的次數(shù)相同。Algorithms Design Techniques and Analysis6.3.2 合并算法分析基本運(yùn)算: 元素比較。為了簡單，假定n是2的冪。如果n=1，則算法不執(zhí)行任何元素的比較，比較次數(shù)是0。如果 n2，則將問題分解為(whose size is n)2個(gè)子問題 (whose size are n/2)。合并兩個(gè)子數(shù)組所需的元素比較次數(shù)在n/2與n-1之間。這樣算法所需的最小比較次數(shù)：Al

13、gorithms Design Techniques and Analysis合并算法分析最大比較次數(shù)：Algorithms Design Techniques and Analysis合并算法分析如果n是任意的正整數(shù)(不必是2的冪)，對(duì)于由算法MERGESORT執(zhí)行的元素比較次數(shù)： 定理6.3 算法MERGESORT對(duì)一個(gè)n個(gè)元素的數(shù)組排序所需的時(shí)間是(nlogn) ，空間是(n)。Algorithms Design Techniques and Analysis6.4 分治范式P117一般來說分治范式由以下的步驟組成劃分步驟。在算法的這個(gè)步驟中，輸入被分成p 1個(gè)部分，每個(gè)子實(shí)例的規(guī)模嚴(yán)格

14、小于n，n是原始實(shí)例的規(guī)模。盡管比2大的其他小的常數(shù)很普遍，但P的最常用的值是2。治理步驟。如果問題的規(guī)模大于某個(gè)預(yù)定的閾值n。，這個(gè)步驟由執(zhí)行P個(gè)遞歸調(diào)用組成，閾值是由算法的數(shù)學(xué)分析導(dǎo)出的組合步驟。這個(gè)步驟是組合P個(gè)遞歸調(diào)用的解來得到期望的輸出值。Algorithms Design Techniques and Analysis一般而言，分治算法有以下形式如果實(shí)例I的規(guī)模是“小”的，則使用直接的方法求解問題并返回其答案，否則繼續(xù)做下一步。把實(shí)例I分割成P個(gè)大小幾乎相同的子實(shí)例I1, I2, . . . , Ip。對(duì)每個(gè)子實(shí)例Ij，1jp,遞歸調(diào)用算法，并得到P個(gè)部分解。組合P個(gè)部分解的結(jié)果得

15、到原實(shí)例I的解，返回實(shí)例I的解。Algorithms Design Techniques and Analysis6.5 尋找中項(xiàng)和第k小元素 選擇問題在一個(gè)包含n個(gè)元素的集合中尋找第k個(gè)最小元素。 (中值是第n/2個(gè)最小元素)直接方法:對(duì)所有的元素排序并取出中間一個(gè)元素，這個(gè)方法需要(nlogn)時(shí)間，因?yàn)槿魏位诒容^的排序過程在最壞的情況下必須至少要花費(fèi)這么多時(shí)間 Can we find an efficient method in optimal linear time?能否在最優(yōu)線性時(shí)間內(nèi)找到更快的算法？Algorithms Design Techniques and Analysis

16、SELECT 算法假設(shè)遞歸算法中，在每個(gè)遞歸調(diào)用的劃分步驟后，我們丟棄元素的一個(gè)固定部分并且對(duì)剩余的元素遞歸。則問題的規(guī)模以幾何級(jí)數(shù)遞減，也就是在每個(gè)調(diào)用過程中，問題的規(guī)模以一個(gè)常因子被減小。假設(shè)某個(gè)算法丟棄1/3并對(duì)剩余的2/3部分遞歸，那么在第二次調(diào)用中，元素的數(shù)目變?yōu)?n/3個(gè)，第三次調(diào)用中為4n/9，第四次調(diào)用中變?yōu)?n/27，等等。現(xiàn)在假定在每次調(diào)用中，算法對(duì)每個(gè)元素耗費(fèi)的時(shí)間不超過一個(gè)常數(shù)，則耗費(fèi)在處理所有元素上的全部時(shí)間產(chǎn)生一個(gè)幾何級(jí)數(shù)：這里。c是某個(gè)被適當(dāng)選擇的常數(shù)，由等式2.12，這個(gè)總數(shù)小于Algorithms Design Techniques and AnalysisS

17、ELECT 算法基本思想首先，如果元素個(gè)數(shù)小于預(yù)定義的閾值44，則算法使用直接的方法計(jì)算第k小的元素，至于如何選擇閡值在以后的算法分析中將會(huì)清楚。下一步把n個(gè)元素劃分成n/5組，每組由5個(gè)元素組成，如果n不是5的倍數(shù)，則排除剩余的元素，這應(yīng)當(dāng)不影響算法的執(zhí)行。每組進(jìn)行排序并取出它的中項(xiàng)即第三個(gè)元素接著將這些中項(xiàng)序列中的中項(xiàng)元素記為mm，它是通過遞歸計(jì)算得到的。將數(shù)組A中的元素劃分成三個(gè)數(shù)組: A1, A2, A3 ，其中分別包含小于、等于和大于mm的元素。最后，求出第k小的元素出現(xiàn)在三個(gè)數(shù)組中的哪一個(gè)，并根據(jù)測(cè)試結(jié)果，算法或者返回第k小的元素，或者在A1 or A3上遞歸。Algorithms

18、 Design Techniques and Analysis算法6.4 SELECT輸入: n個(gè)元素的數(shù)組A1.n和整數(shù)k,1k n 。輸出: A中的第k小元素。1.select(A,1,n,k)過程 select(A,low,high,k)1. phigh-low+12. if p44 then 將A排序 return (Ak)3. Let q= p/5.將A分成9組，每組5個(gè)元素。如果5不整除P，則排除剩余的元素4.將q組中的每一組單獨(dú)排序，找出中項(xiàng)。所有中項(xiàng)的集合為M5. mmselect(M,1,q ,q/2) mm 為中項(xiàng)集合的中項(xiàng)6. 將Alow.high 分成三組: A1=a|

19、amm7. case|A1| k: return select(A1,1,|A1|,k)|A1|+|A2| k: return mm |A1|+|A2|k: return select(A3,1,|A3|,k-|A1|-|A2|)8. end case Algorithms Design Techniques and Analysis例子為方便起見，讓我們暫時(shí)將算法中的閾值44改為一個(gè)較小的數(shù)6假設(shè)存在數(shù)組A1.25 :8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2,13, 32,12, 6, 29, 32, 54, 5, 16, 22, 23,

20、 7 我們要在數(shù)組A中找到第13個(gè)最小的元素Algorithms Design Techniques and Analysis例子83317515749351125371432135212629325451622237partition83317515749351125371432135212629325451622237sort81733515711253537492313145261229325457162223median1316293335partition81711251432131265162223729335157493537523254discardAlgorithms Des

21、ign Techniques and Analysis例子817112514321312651622237A115partition817112514321312651622237sort811141725236121357162223median61416partition811321312657141725162223discardAlgorithms Design Techniques and Analysis例子1725162223A1115sort1617222325Succeed! The result is A13=22Algorithms Design Techniques a

22、nd Analysisselection算法分析其中的元素已被劃分成具有5元素的各個(gè)組，每組元素從底到頂按升序排列。而且這些組以這樣的方式整齊排列:它們的中項(xiàng)是從左到右以升序排列的。Algorithms Design Techniques and Analysisselection算法分析所有圍在矩形W 中的元素是小于或等于mm的，所有圍在矩形x中的元素是大于或等于mm 的。設(shè)A1表示小于或等于mm的元素集， A3是大于或等于mm的元素集這個(gè)算法中， A1是嚴(yán)格小于mm的元素集， A3是嚴(yán)格大于mm的元素集Algorithms Design Techniques and Analysis由于A

23、1至少與w同樣大，我們有因此由參數(shù)的對(duì)稱性得到這樣就為在A1和A3的元素個(gè)數(shù)建立了上界：即小于mm的元素的個(gè)數(shù)和大于mm的元素個(gè)數(shù)不能夠超過大約0.7n( n的常分?jǐn)?shù)倍)。Algorithms Design Techniques and Analysis時(shí)間復(fù)雜度算法的運(yùn)行時(shí)間T(n) P112在算法中select過程的步驟1和步驟2耗費(fèi)的時(shí)間都是(1) 步驟3為(n)時(shí)間。由于對(duì)每組排序需要時(shí)間為常量，步驟4耗費(fèi)(n)時(shí)間，步驟5所需的時(shí)間為T( n/5 )，步驟6需要(n)時(shí)間。由以上的分析，步驟7耗費(fèi)的時(shí)間至多是T(0.7n+1.2)。當(dāng)n 44時(shí)，如果0.7n + 1.2 0.75n-

24、 1這個(gè)不等式將成立。得出的結(jié)論為，對(duì)于n 44 ，步驟7所耗費(fèi)的時(shí)間至多是T(0.75n)。Algorithms Design Techniques and Analysis時(shí)間復(fù)雜度這個(gè)分析蘊(yùn)含著算法SELECT的運(yùn)行時(shí)間有以下的遞推式 定理6.4 在一個(gè)由n個(gè)元素組成的線序集合中提取第k小元素，所需的時(shí)間是(n) ，特別地，n個(gè)元素的中值可以在(n)時(shí)間找出。Algorithms Design Techniques and Analysis6.6 快速排序快速排序是另外一種排序算法,該排序算法具有(nlogn)的平均運(yùn)行時(shí)間這個(gè)算法優(yōu)于MERGESORT算法的一點(diǎn)是它在原位上排序，即對(duì)于

25、被排序的元素，不需要輔助的存儲(chǔ)空間。Algorithms Design Techniques and Analysis6.6.1 劃分算法基本思想設(shè)Alow.high是一個(gè)包含n個(gè)數(shù)的數(shù)組，并且x=Alow我們考慮重新安排數(shù)組A中的元素的問題，使得小于或等于x的元素在x的前面，隨后x又在所有大于它的元素的前面經(jīng)過數(shù)組中元素改變排列后，對(duì)于某個(gè)w，lowwhigh，x在Aw 中。例如, 如果A= ,3,9,2,7,1,8；則經(jīng)過重新排列其中的元素后，得到 A=1,3,2, ,7,9,8 其中 w=4。55Algorithms Design Techniques and Analysis劃分算法這

26、種重排列行動(dòng)也稱為圍繞x的拆分或劃分，x稱為主元或拆分元素。定義6.1 如果元素Aj既不小于Alow.j-1中的元素，也不大于Aj+1.high中的元素，則稱其處在一個(gè)適當(dāng)位置或正確位置。觀察結(jié)論6.2 用x(x A)作為主元?jiǎng)澐謹(jǐn)?shù)組A后，x將處于一個(gè)正確位置。Algorithms Design Techniques and Analysis算法6.5 SPLIT輸入:數(shù)組Alow.high.輸出: (1)如有必要，輸出按上述描述的重新排列的數(shù)組A 。 (2)劃分元素Alow的新位置w。1. ilow2. xAlow3. for jlow+1 to high4. if Aj x then5.i

27、i+16.if i j then 互換Ai and Aj7.end if 8. end for9. 互換Alow and Ai10. wi11. return A and wAlgorithms Design Techniques and Analysis例子6570758085605550ij65x=jjjjijij50Success!Algorithms Design Techniques and Analysis算法分析觀察結(jié)論6.3 由算法SPLIT執(zhí)行的元素比較次數(shù)恰好是n-1，這樣它的時(shí)間復(fù)雜性為(n)。最后注意到算法僅僅用到一個(gè)額外空間用于存儲(chǔ)它的局部變量，因此算法的空間復(fù)雜性為

28、(1)。Algorithms Design Techniques and Analysis6.6.2 快速排序算法基本思想要排序的元素Alow.high通過算法SPLIT重新排列元素，使得原先在Alow中的主元占據(jù)其正確的位置Aw，并且所有小于或等于Aw的元素所處的位置為Alow.w-1，而所有大于Aw的元素所處的位置是Aw+1.high。子數(shù)組Alow.w-1和Aw1.high 遞歸地排序，自動(dòng)產(chǎn)生整個(gè)排序數(shù)組Algorithms Design Techniques and Analysis算法6.6 QIUCKSORT輸入: n個(gè)元素的數(shù)組A1.n輸出:按非降序排列的數(shù)組A中的元素1. q

29、uicksort(A,1,n)過程 quicksort(A,low,high)1. if lowhigh then2.SPLIT(Alow.high,w) w為Alow的新位置3.quicksort(A,low,w-1)4.quicksort(A,w+1,high)5. end ifAlgorithms Design Techniques and Analysis例子假設(shè)數(shù)組A=4,6,3,1,8,7,2,5.4631872523148765231123113376587685576576766766Success!Algorithms Design Techniques and Analys

30、isMERGESORT 和 QUICKSORT算法SPLIT和算法QUICKSORT的關(guān)系類似于算法MERGE和算法MERGESORT的關(guān)系。兩個(gè)排序算法都由名為SPLIT和MERGE的算法之一的一系列調(diào)用組成。在算法MERGESORT中，合并排序序列屬于組合步驟，而在算法QUICKSORT中的劃分過程則屬于劃分步驟。事實(shí)上，在算法QUICKSORT中組合步驟是不存在的。Algorithms Design Techniques and Analysis6.6.3 快速排序算法分析空間復(fù)雜度:雖然算法不需要輔助空間存儲(chǔ)數(shù)組元素，但算法還是至少需要(n)的空間，工作空間在(logn)和(n)之間變

31、化。這是因?yàn)樵诿看芜f歸調(diào)用中，表示下一次要排序的數(shù)組右邊部分的左右界w1和high必須保存。Algorithms Design Techniques and Analysis6.6.3.1 最壞情況的行為定理6.5 在最壞的情況下，算法QUICKSORT的運(yùn)行時(shí)間是(n2) ，然而如果總是選擇中項(xiàng)作為主元，它的時(shí)間復(fù)雜性是(nlogn)。推導(dǎo)見P116Algorithms Design Techniques and Analysis6.6.3.2 平均情況的行為 假設(shè)假定對(duì)于數(shù)1，2，n的i個(gè)排列中的每一個(gè)排列的出現(xiàn)是等可能性的，這一點(diǎn)確保了在數(shù)組中的每個(gè)數(shù)以同樣可能作為第一個(gè)元素，并被選為主

32、元，也就是說，數(shù)組A中的任意元素被選為主元的概率是1/n.設(shè)C(n)表示對(duì)大小為n的輸入數(shù)據(jù)算法所做的平均比較次數(shù)，根據(jù)觀察結(jié)論6.3，得到：步驟2恰好耗費(fèi)n-1次比較；步驟3和步驟4分別耗費(fèi)了C(w-1)和C(n-w)次比較；因此總的比較次數(shù)為：Algorithms Design Techniques and Analysis因?yàn)?因此如果用n-1代替n，得到：推導(dǎo)見P1176.6.3.2 平均情況的行為Algorithms Design Techniques and Analysis等式6.3減去等式6.4，再重新排列各項(xiàng)得到現(xiàn)在把變量更換為一個(gè)新的變量D，并設(shè)那么,其解為6.6.3.2

33、平均情況的行為Algorithms Design Techniques and Analysis因?yàn)?結(jié)果,定理6.6: 算法QUICKSORT對(duì)n個(gè)元素的數(shù)組進(jìn)行排序執(zhí)行的平均比較次數(shù)是(nlogn)。6.6.3.2平均情況的行為Algorithms Design Techniques and Analysis6.7 大整數(shù)乘法我們假定大小一定的整數(shù)相乘需要耗費(fèi)定量的時(shí)間，而當(dāng)兩個(gè)任意長的整數(shù)相乘時(shí)，這個(gè)假定就不再有效了對(duì)于處理不定長數(shù)的算法的數(shù)據(jù)輸入，通常是按二進(jìn)制的位數(shù)來計(jì)算的(或按二進(jìn)制數(shù)字來計(jì)算)設(shè)u和v是兩個(gè)n位的整數(shù)，傳統(tǒng)的乘法算法需要(n2)數(shù)字相乘來計(jì)算u和v的乘積。Is t

34、here much more efficient method?Algorithms Design Techniques and Analysis6.7 大整數(shù)乘法設(shè)u和v都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積u*v。我們可以用小學(xué)所學(xué)的方法來設(shè)計(jì)一個(gè)計(jì)算乘積u*v的算法，但是這樣做計(jì)算步驟太多，顯得效率較低。如果將每2個(gè)1位數(shù)的乘法或加法看作一步運(yùn)算，那么這種方法要作O(n2)步運(yùn)算才能求出乘積u*v 。下面我們用分治法來設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。我們將n位的二進(jìn)制整數(shù)u和v各分為2段，每段的長為n/2位(為簡單起見，假設(shè)n是2的冪)，Algorithms Design Techn

35、iques and Analysis分治技術(shù)假定n是2的冪.wxyzu和v的乘積可以計(jì)算為：時(shí)間復(fù)雜度函數(shù)為：遞推式的解：n/2n/2Algorithms Design Techniques and Analysis分治技術(shù)現(xiàn)在考慮：我們得到：時(shí)間復(fù)雜度是：遞推式的解是：Algorithms Design Techniques and Analysis6.8 矩陣乘法 兩個(gè)矩陣 A，B：A 的列數(shù)等于 B 的行數(shù)，則A、B可以相乘。即，如果 A = （aij）是一個(gè)m * n的矩陣，B =（bjk）是一個(gè) n * p 的矩陣，則它們的乘積 C = AB 是 m * p 矩陣 C = （cik）

36、。A23B32C22Algorithms Design Techniques and Analysis6.8 矩陣乘法 問題描述令A(yù)和B是兩個(gè)nn的矩陣，我們希望計(jì)算它們的乘積C=AB。Algorithms Design Techniques and Analysis6.8.1 矩陣乘法在傳統(tǒng)方法中， C=AB是由以下公式計(jì)算的因?yàn)槊坑?jì)算一個(gè)元素Ci，j，需要做 n 個(gè)乘法和 n 1 次加法很容易看出算法需要n3次乘法運(yùn)算和n3-n2次加法運(yùn)算。這導(dǎo)致其時(shí)間復(fù)雜度為(n3).Is there much more efficient method?Algorithms Design Techni

37、ques and Analysis6.8.2 遞歸方法假定n=2k ，k 0，如果n2 ，則A，B和C可分別分成4個(gè)大小為n/2n/2的子矩陣用分治方法來計(jì)算C的組成：Algorithms Design Techniques and Analysis遞歸方法計(jì)算量總耗費(fèi)是： 最終結(jié)果： 觀察結(jié)論 6.4遞歸方法需要n3次乘法運(yùn)算和n3-n2次加法運(yùn)算，這些剛好和前面?zhèn)鹘y(tǒng)方法所講述的一樣。兩種算法的區(qū)別僅僅在于矩陣元素相乘的次序上，其他方面是一樣的Algorithms Design Techniques and Analysis6.8.3 STRASSEN算法基本思想增加加減法的次數(shù)來減少乘法次

38、數(shù)和Algorithms Design Techniques and AnalysisSTRASSEN算法 基本思想我們首先計(jì)算以下的乘積接著從一下面式子計(jì)算出CAlgorithms Design Techniques and Analysis時(shí)間復(fù)雜度 算法用到的加法是18次，乘法是7次，對(duì)于其運(yùn)行時(shí)間產(chǎn)生以下遞推式 （P121）或即運(yùn)行時(shí)間為：Algorithms Design Techniques and Analysis時(shí)間復(fù)雜度Strassen算法的高效之處，就在于，它成功的減少了乘法次數(shù)，將8次乘法，減少到7次。不要小看這減少的一次，每遞歸計(jì)算一次，效率就可以提高1 / 8，比如一

39、個(gè)大的矩陣遞歸5次后，（7 / 8）5 = 0.5129，效率提升一倍。不過，這只是理論值，實(shí)際情況中，有隱含開銷，并不是最常用算法。矩陣是稀疏矩陣時(shí)，為稀疏矩陣設(shè)計(jì)的方法更快。所以，稠密矩陣上的快速矩陣乘法實(shí)現(xiàn)一般采用Strassen算法。Algorithms Design Techniques and Analysis6.8.4 三個(gè)算法的比較三種算法所做的算術(shù)運(yùn)算的次數(shù)乘法加法復(fù)雜度傳統(tǒng)算法.n3n3- n2(n3)遞歸方法.n3n3- n2(n3)STRASSEN算法.nlog76 nlog7 -6 n2(nlog7)Algorithms Design Techniques and A

40、nalysis6.9 最近點(diǎn)對(duì)問題 問題:設(shè)S是平面上n個(gè)點(diǎn)的集合，在這一節(jié)中，我們考慮在S中找到一個(gè)點(diǎn)對(duì)p和q的問題，使其相互距離最短。換句話說，希望在S中找到具有這樣性質(zhì)的兩點(diǎn)p1 = (x1,y1)和p2 = (x2,y2)，使它們間的距離在所有S中點(diǎn)對(duì)間為最小。Algorithms Design Techniques and Analysis最近點(diǎn)對(duì)問題蠻力算法就是簡單地檢驗(yàn)所有可能的n(n-1)/2個(gè)距離并返回最短間距的點(diǎn)對(duì)。耗費(fèi)(n2) 的時(shí)間我們將運(yùn)用分治設(shè)計(jì)技術(shù)描述一個(gè)時(shí)間復(fù)雜性為(nlogn)的算法來解決最近點(diǎn)對(duì)間題。Algorithms Design Techniques

41、and Analysis分治方法Sort:第一步是以x坐標(biāo)增序?qū)中的點(diǎn)排序Divide:S點(diǎn)集被垂直線L大約劃分成兩個(gè)子集Sl和Sr ，使|Sl| = |S|/2 ， |Sr| = |S|/2 ，設(shè)L是經(jīng)過x坐標(biāo)Sn/2的垂直線，這樣在Sl中的所有點(diǎn)都落在或靠近L的左邊，而所有Sr中的點(diǎn)落在或靠近L的右邊。Conquer:現(xiàn)在按上述遞歸地進(jìn)行，兩個(gè)子集Sl和Sr的最小間距l(xiāng)和r可分別計(jì)算出來。Combine:組合步驟是把在Sl中的點(diǎn)與Sr中的點(diǎn)之間的最小間距計(jì)算出來。最后所要求的解是l ，r 和.中的最小值。Algorithms Design Techniques and Analysis基

42、本思想sortdivideconquercombine比較這三個(gè)距離，返回最小值lrAlgorithms Design Techniques and Analysis怎樣合并結(jié)果，這一步的關(guān)鍵在于計(jì)算，計(jì)算Sl中的每個(gè)點(diǎn)與Sr中每個(gè)點(diǎn)之間的距離的樸素方法需要(n2)。設(shè) = minl, r，如果最近點(diǎn)對(duì)由Sl中的某個(gè)點(diǎn)pl與Sr中的某個(gè)點(diǎn)pr組成，則pl和pr一定在劃分線L的距離內(nèi)。這樣，如果令Sl和Sr分別表示為在線L距離內(nèi)的Sl和Sr 中的點(diǎn)，則pl一定在Sl中， pr一定在Sr中。Algorithms Design Techniques and Analysis假設(shè) ，則存在兩點(diǎn)plSl和prSr ，有d(pl