分治算法

工具书,文集,丛书,教材,教辅

本文由侯国英贡献
ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。
第三章 Divide-andDivide-and-Conquer 技术
邹权（博士） 邹权（博士） 计算机科学系
提要
3.1 3.2 3.3 3.4 Divide-and-Conquer原理 Divide-and-Conquer原理 整数乘法 矩阵乘法 Finding the closest pair of points
3.1 Divide-and-Conquer原理 Divide-and-Conquer原理
Divide-and-Conquer算法的设计 Divide-and-Conquer算法的设计 ? Divide-and-Conquer算法的分析 Divide-and-Conquer算法的分析
Divide-and-Conquer算法的设计 Divide-and-Conquer算法的设计
设计过程分为三个阶段 – Divide： 整个问题划分为多个子问题 Divide： – Conquer：求解各子问题(递归调用正设计的算法) Conquer：求解各子问题(递归调用正设计的算法) – Combine：合并子问题的解, 形成原始问题的解 Combine：合并子问题的解,
原始问题 问题分解 子问题
求解子问题
Divide
… 子问题
求解子问题
子问题
求解子问题
Conquer
子问题解
子问题解 … 子问题解 合并子解 原始问题的解
Merge
Homework
云计算、Map-Reduce、Hadoop、Mahout
Divide-and-Conquer算法的分析 Divide-and-Conquer算法的分析
分析过程
–建立递归方程 –求解
递归方程的建立方法
–设输入大小为n,T(n)为时间复杂性 设输入大小为n,T(n)为时间复杂性 –当n<c, T(n)=θ(1) n<c,
– Divide阶段的时间复杂性 Divide阶段的时间复杂性
划分问题为a个子问题。 划分问题为a个子问题。 ? 每个子问题大小为n/b。 每个子问题大小为n/b。 ? 划分时间可直接得到=D(n) 划分时间可直接得到=
– Conquer阶段的时间复杂性 Conquer阶段的时间复杂性
递归调用 ? Conquer时间= aT(n/b) 时间=
– Combine阶段的时间复杂性 Combine阶段的时间复杂性
时间可以直接得到=C(n) 时间可以直接得到=
–总之
T(n)=θ(1) if n<c ? T(n)=aT(n/b)+D(n)+C(n) otherwise T(n)=aT(n/b)+D(n)+C(n)
–求解递归方程T(n) 求解递归方程T(n)
使用第二章的方法
例1. Merge-sort算法 Merge-sort算法
9 4 8 6 T(n)=2T(n/2)+O(n) 5 T(n)=O(nlogn) T(n)=O(nlogn) 9 4 8 6 5 Merge-sort 4 5 6 8 9 Combine 1 2 3 4 5 6 7 8 9 10 Conquer 2 1 3 7 10 Divide 2 1 3 7 10 Merge-sort 1 2 3 7 10
例2. 求一个集合中的最大数算法
32
T(n)=2T(n/2)+1
29，14，15，1，6，10，32，12 29，14，15， 10，32， 29 29，14，15，1 29，14，15， 29 29，14 29， 15 15，1 15， 10 6，10
32
6，10，32，12 10，32， 32 32，12 32，
3.2 3.2 整数乘法
问题定义
输入： 位二进制整数X 输入：n位二进制整数X和Y 输出： 输出：X和Y的乘积 通常，计算X*Y时间复杂性位 时间复

第1页下一页