3
4
5
6
先序遍历 V－L－R 中序遍历 L－V－R
7 8 9 10 11
后序遍历 L－R－V
数据结构 (30230594)
14
吴及 电子工程系
分治算法的效率估计
设对于规模为n的问题，算法的时间复杂度为T(n) 采用分治法求解，设每次可以将一个实例分解成为若干个规模为
n/b的实例，其中a个实例需要求解 为简单起见，假设n=bk，则有：
持续这样处理，直至残差满足 f (c) <ε
数据结构
27
(30230594)
x1 x* x2 b
2 1
吴及 电子工程系
小球重量
如果有n个外表完全一样的小球，其中有一个小球比其它小球轻， 如何有一架天平把这个小球找出来？
采用减治法
把小球分为两堆，每堆有n/2个小球，n为奇数则多一小球
用天平比较两堆小球的重量，如果相等，多余的小球为所求
否则取较轻的一堆，继续分解
时间复杂度：T(n) = T(n/2)+ 1， 则T(n) = log2n
有无更好的方法？
数据结构 (30230594)
28
吴及 电子工程系
减治法
减一个常量： 选择排序 建一个常因子：折半查找，二分法求解非线性方程 减可变规模： 辗转相除法
数据结构 (30230594)
29
吴及 电子工程系
变治法
基本思想
是把一个求解困难的问题转换成为一个有已知解法的问题，并 且这种转换的复杂度不超过求解目标问题的算法复杂度
顺序查找
64
88
0,1,0 3,4,3 6,7,6 9,10,9
13 37
75
92
1,1,1 4,4,4 7,7,7 10,10,10
24
吴及 电子工程系
选择排序
ASORT I NGEXAMP L E 1 ASORT I NGEXAMP L E 2 AAORT I NGEXSMP L E 3 A A ER T I NGOX SMP L E 4 A A E E T I NGOX SMP L R 5 AAEEG I NTOXSMP L R 6 AAEEG I NTOXSMP L R 7 AAEEG I L TOXSMPNR 8 A A E EG I L MOX S T P NR 9 A A E EG I LMNX S T POR 10 A A E E G I L M N O S T P X R 11 A A E E G I L M N O P T S X R 12 A A E E G I L M N O P R S X T 13 A A E E G I L M N O P R S X T 14 A A E E G I L M N O P R S T X
A A E EG I LMNOPRS T X
数据结构 (30230594)
25
吴及 电子工程系
辗转相除法
求两个整数m 和n 的最大公因子
欧几里得算法，也称辗转相除法
1. 用n 去除m，将余数赋给r； 2. 将n 的值赋给m，将r 的值赋给n， 3. 如果n＝0；返回m 的值作为结果，过程结束；否则，返回第一步；
e d ge
e d ge
e d ge
e d ge
e d ge
最坏时间复杂度：O(m*n)，与KMP算法比较
数据结构
6
(30230594)
吴及 电子工程系
最大公因子
蛮力法求两个整数m和n的最大公因子
比较两个整数m和n的大小，不失一般性，设有m<n成立 则从2到m，逐个判断每个整数是否可以同时整除m和n，可以得到m和n的
的正确性和效率
数据结构 (30230594)
10
吴及 电子工程系
内容提要
算法设计技术
蛮力法 分治法 贪心算法 动态规划 搜索算法
数据结构
11
(30230594)
吴及 电子工程系
分治法
基本思想
把问题的一个实例分解成为属于同一问题的若干个较小规模的实例 重复这个过程直到规模较小的实例很容易求解， 求解这些规模较小的实例， 合并较小问题的解，以得到原始问题的解。
蛮力法
不采用任何技巧，基于问题的描述直接地解决问题的方法 思路直接，不考虑代价 蛮力法举例
蛮力字符串匹配 求两个整数的最大公因子 查找元素 百元买百鸡问题
数据结构 (30230594)
5
吴及 电子工程系
蛮力字符串匹配
Kn o w l e d ge i s po we r
e d ge
数据结构 (30230594)
23
吴及 电子工程系
折半查找
折半查找也称二分查找
0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92
56 l＝0, r =10, m = 5
数据结构 (30230594)
19 0,4,2
80 6,10,8
5
21
握某个特定算法更重要
数据结构 (30230594)
2
吴及 电子工程系
内容提要
算法设计技术 算法优化技术 计算复杂性理论简介
数据结构 (30230594)
3
吴及 电子工程系
内容提要
算法设计技术
蛮力法 分治法 贪心算法 动态规划 搜索算法
数据结构
4
(30230594)
吴及 电子工程系
二叉树遍历是线性时间复杂度O(n) 对一个序列求和采用分治法
在很多情形下，分治法确实有效，关键在于递推式中的参数
数据结构 (30230594)
16
吴及 电子工程系
大整数乘法
两个n位整数a和b的乘法如何进行？ 蛮力法：传统的计算方式
a = an an-1 …a2 a1， b = bn bn-1 …b2 b1
假设每个元素的查找概率相
等，则平均查找长度为：
n1
n1 1
n 1
ASL i0 PiCi i0 n (i 1) 2
对于规模为N的集合，平均
来说需要进行N/2次比较
数据结构 (30230594)
序号 1 2 3 4 5 6
204 205 206 207
8
学号 2002010972 2003010141 2003010142 2003010340 2003010415 2003010532
全部公因子cf1， cf2， cf13…… 这个公因子序列中最大的cfk，即为m和n的最大公因子 或者从m到2，逐个判断每个整数是否可以同时整除m和n，找到的第一个
能够同时整除m和n的整数就是最大公因子
针对蛮力法的优化 其它方法
数据结构 (30230594)
7
吴及 电子工程系
查找元素
按照蛮力法的思想，采用逐 个比较的方式
2003011327 2003080085 2003080086 2003080087
姓名 班级
林凌南 无37
姚泓毅 无34
秦文 无31
蓝青 无31
高天石 无32
陈树卫 无35
曾波 无311
阮玄清 无33
阮孟贵 无33
李炅敏 无33
吴及 电子工程系
百元买百鸡问题
百元买百鸡问题：公鸡每只5元、母鸡每只3元、小鸡3只1元，百元买百 鸡，问共有多少种买法？
分治法
子集S1和S2的划分， 时间复杂度：T(n) = 2T(n/2)+ M(n)，
由于M(n)∈O(n)， 因此：T(n)∈O(nlogn)
数据结构
22
(30230594)
吴及 电子工程系
减治法
减治法是把问题转化为规模较小的子问题，通过求解子问题来得 到原问题的解
对于有些问题，减治法与分治法存在一定的相关性
GI L
N PO
TX
IL
OP
T
I
P
A A E EG I LMNOPR S T X
数据结构 (30230594)
13
吴及 电子工程系
二叉树的遍历
树的遍历就是按某种次序访问树中的结点，
要求每个结点访问一次且仅访问一次。
0
设访问根结点记作 V 遍历根的左子树记作 L
1
2
遍历根的右子树记作 R
遍历方式
2010-2011春季学期数据与算法课程讲义
算法设计技术
吴及 wuji_ee@
清华大学电子工程系 2011年5月
科学研究的一般方法
客观 观察认识 数学 算法设计 算法 实验测试 结果
事物 和猜想 模型
求解
分析
反馈验证
从特定算法到算法设计的一般性技术 知道求解的方法比知道解更重要，掌握算法设计和优化技术比掌
c = a*b = a*bn* 10n-1+a*bn-1* 10n-1…a*b2* 10 +a*b1 考虑乘法的复杂度：n2次乘法
数据结构 (30230594)
17
吴及 电子工程系
大整数乘法
采用分治法
设a和b都为n位整数，则可表示为：
a = af10n/2+al，b = bf10n/2+bl af和bf分别为a和b的前半部分，al和bl分别为a和b的后半部分 c = a*b = (af * bf) 10n + (af * bl + al * bf ) 10n/2 + (al * bl)
Strassen矩阵乘法
矩阵乘法
蛮力法：需要8次乘法和4次加法
Strassen矩阵乘法
其中：
数据结构 (30230594)
20
吴及 电子工程系
Strassen矩阵乘法
Strassen矩阵乘法需要7次乘法和18次加减法 对于高维矩阵，可以引入分治法