分治策略-databasegroup@depart-展示頁
2025-02-01 11:57本頁面
【正文】 r 技術 鄒權（博士） 計算機科學系 DivideandConquer原理 整數(shù)乘法 矩陣乘法 Finding the closest pair of points 提要 ? 設計過程分為三個階段 – Divide： 整個問題劃分為多個子問題 – Conquer： 求解各子問題 (遞歸調(diào)用正設計的算法 ) – Combine： 合并子問題的解 , 形成原始問題的解 原始問題 求解子問題 子問題 子問題 子問題 … 求解子問題 求解子問題 子問題解 子問題解 子問題解 … 合并子解 問題分解 Divide Conquer Merge 原始問題的解 Homework ? 云計算、 MapReduce、 Hadoop、 Mahout ?分析過程 – 建立遞歸方程 – 求解 ?遞歸方程的建立方法 – 設輸入大小為 n,T(n)為時間復雜性 – 當 nc, T(n)=?(1) – Divide階段的時間復雜性 ?劃分問題為 a個子問題 。 ?每個子問題大小為 n/b。 ? 建立遞歸方程 T(n)=?(1) if n=1 T(n)=3T(n/2)+O(n) if n1 ?使用 Master定理 T(n)=O(nlog3)=O() 算法的分析 算法的數(shù)學基礎 ?把 C=AB中每個矩陣分成大小相同的 4個子矩陣 每個子矩陣都是一個 n/2 ? n/2矩陣 ?于是 ??????22211211CCCC??????22211211AAAA??????22211211BBBB= 展開并整理等式的右邊，即得到計算的方法 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) ? 計算 n/2?n/2矩陣的 10個加減 和 7個乘法 算法 C11 = M5 + M4 M2 + M6 C12 = M1 + M2 C21 = M3 + M4 C22 = M5 + M1 – M3 – M7 ? 計算 n/2?n/2矩陣的 8個加減 ? 18個 n/2?n/2矩陣加減法，每個需 O(n2) ? 7個 n/2?n/2矩陣乘法 ? 建立遞歸方程 T(n)=O(1
數(shù)學相關推薦
鄂ICP備17016276號-1