第三章divide-and-conquer技術(shù)(編輯修改稿)
2025-08-16 13:23 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ?22211211BBBB= 展開(kāi)并整理等式的右邊，即得到計(jì)算的方法 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 A12) (B11 + B12) ? 計(jì)算 n/2?n/2矩陣的 10個(gè)加減 和 7個(gè)乘法 算法 C11 = M5 + M4 M2 + M6 C12 = M1 + M2 C21 = M3 + M4 C22 = M5 + M1 – M3 – M7 ? 計(jì)算 n/2?n/2矩陣的 8個(gè)加減 ? 18個(gè) n/2?n/2矩陣加減法，每個(gè)需 O(n2) ? 7個(gè) n/2?n/2矩陣乘法 ? 建立遞歸方程 T(n)=O(1) n=2 T(n)=7T(n/2) + O(n2) n2 ? 使用 Master定理求解 T(n) T(n) = O(nlog7) ?O() 算法復(fù)雜性分析 Finding the closest pair of points 問(wèn)題定義 輸入 ： Euclidean空間上的 n個(gè)點(diǎn)的集合 Q 輸出 ： P1, P2?Q, Dis(P1, P2)=Min{Dis(X, Y) | X, Y?Q} Dis(X, Y)是 Euclidean距離 : 如果 X=(x1, x2), Y=(y1, y2)，則 221221 )() yyxxD i s ( X, Y ) ???? （一維 空間算法 ? 利用排序的算法 –算法 ?把 Q中的點(diǎn)排序 ?通過(guò)排序集合的線性掃描找出最近點(diǎn)對(duì) –時(shí)間復(fù)雜性 ? T(n)=O(nlogn) 一維空間算法 (續(xù) ) ? Divideandconquer算法 Preprocessing: 1. 如果 Q中僅包含 2個(gè)點(diǎn)，則返回這個(gè)點(diǎn)對(duì) ； 2. 求 Q中點(diǎn)的中位數(shù) m。 Divide: 1. 用 Q中點(diǎn)坐標(biāo)中位數(shù) m把 Q劃分為兩個(gè)
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1