1
分治法与时间复
杂度计算
陈长城
2007-10-31
2
总目录1（时间复杂度）
null一理论上的可计算与现实上的可计算
null二算法时间复杂度分析
null2.1概念、数学表示
null2.2时间复杂度分析
null2.2.1循环
null2.2.2递归
3
总目录2（分治法）
null三分治策略
null主要思想、实例、总结
null四递归算法与递推方程
null递推方程定义、求解、实例
null五降低递归算法复杂性的途径
null5.1代数变换减少子问题个数、实例
null5.2预处理减少递归的操作、实例
null六各类算法比较
null七思考题
4
一理论上的可计算与现实上的可计算
null1.1理论上的可计算
null可计算性理论
null1.2现实上的可计算
null计算复杂性理论
5
1.1理论上的可计算――可计算性理论
研究目标
确定什么问题是可计算的
合理的计算模型
已有的：递归函数、Turing机、λ演算、Post系统等
条件：计算一个函数只要有限条指令
每条指令可以由模型中的有限个计算步骤完成
指令执行的过程是确定的
Church-Turing论题
如果一个函数在某个合理的计算模型上可计算，那么它在
Turing机上也是可计算的
可计算性是不依赖于计算模型的客观性质
6
1.2现实上的可计算――计算复杂性理论
内容
算法复杂度——算法所使用的时间、空间的估计
问题复杂度——估计问题的难度
术语和概念
问题
算法
算法的时间复杂度
复杂度函数的阶
多项式时间的算法与指数时间的算法
问题的复杂度分析
7
8
二算法的时间复杂度
最坏情况下的时间复杂度
算法求解输入规模为n的实例所需要的最长时间W(n)
平均情况下的时间复杂度
算法求解输入规模为n的实例所需要的平均时间A(n)
复杂度表示
针对问题选择基本运算
将基本运算次数表示为输入规模的函数
9
∑
=
?+
+
=?+=
=
n
i
np
np
np
n
p
inA
nnW
1
)1(
2
)1(
)1()(
)(
例搜索问题
输入：非降顺序排列的数组L，元素数为n.数x
输出：j.若x在L中，j是x首次出现的序标；
否则j=0
算法顺序搜索
假设x在L中的概率为p
x在L中不同位置是等概分布的，则
10
复杂度函数的阶
设f和g是定义域为自然数集N上的函数
f(n)=O(g(n)).
若存在正数c和n
0
使得对一切n≥n
0
有0≤f(n)≤cg(n)
f(n)=Ω(g(n)).
若存在正数c和n
0
使得对一切n≥n
0
有0≤cg(n)≤f(n)
f(n)=o(g(n)).
对所有正数c<1存在n
0
使得对一切n≥n
0
有0≤f(n)
f(n)=Θ(g(n))
f(n)=O(g(n))且f(n)=Ω(g(n))
O(1)表示常数函数
11
例设证明f(n)=Θ(n
2
)
证若存在正数c,d使得
那么d≥1/2,n≥1;c≤1/14,n≥7
取c=1/14,d=1/2,n
0
=7
例设f(n)=6n
3
,证明f(n)≠Θ(n
2
)
证要使6n
3
≤cn
2
，则6n≤c,
即n≤c/6,与c是常数矛盾
,3
2
1
)(
2
nnnf?=
,
3
2
1
d
n
c≤?≤
12
大O表示法的常用计算规则
null加法规则
nullT(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=
O(max(f1(n),f2(n)))
null乘法规则
nullT(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=
O(f1(n)×f2(n))
13
14
1.310
13
世纪210
8
世纪3855世纪6.5年58分.059秒
3
n
366世纪35.7年12.7天17.9分1.0秒.001秒
2
n
13.0分5.2分1.7分24.33.210
-1
n
5
21610
-3
12510
-3
6410
-3
2710
-3
810
-3
10
-3
n
3
3610
-4
2510
-4
1610
-4
910
-4
410
-4
10
-4
n
2
610
-5
510
-5
410
-5
310
-5
210
－5
10
－5
n
605040302010
问题规模时间复杂
度函数
多项式时间的算法与指数时间的算法
多项式时间的算法
时间复杂度函数为O(p(n))的算法，其中p(n)是n的多项式
指数时间的算法
不存在多项式p(n)使得该算法的时间复杂度为O(p(n))
15
N
6
+6.29N
6
+4.19N
6
3
n
N
5
+9.97N
5
+6.64N
5
2
n
3.98N
4
2.5N
4
N
4
n
5
10N
3
4.64N
3
N
3
n
3
31.6N
2
10N
2
N
2
n
2
1000N
1
100N
1
N
1
n
快1000倍的计算机快100倍的计算机
计算机
1小时可解的问题实例的最大规模
时间复杂
度函数
16
2.2时间复杂度分析
多项式时间可解的问题与难解的问
多项式时间可解的问题P
存在着解P的多项式时间的算法
难解的问题P
不存在解P的多项式时间的算法
实际上可计算的问题
多项式时间可解的问题
17
2.2时间复杂度分析
null算法的执行时间绝大部分花在循环和递归
上，现分别讨论
null循环
null递归
18
2.2.1循环
null循环语句的时间代价一般用以下三条原则分析
null对于一个循环，循环次数乘以每次执行循环体内的简单
语句的数目即为其时间代价
null对于多个并列循环，可先计算每个循环的时间代价，然
后按大Ｏ表示法的加法规则计算总代价
null对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计
算。但如果嵌套是有条件的，为精确计算其时间代价，
要仔细累加循环中简单语句的实际执行数目，以确定其
时间代价
19
2.2.2递归
null写出递推方程
null求解递推方程
详见本讲义第四部分
20
总目录2（分治法）
null三分治策略
null主要思想、实例、总结
null四递归算法与递推方程
null递推方程定义、求解、实例
null五降低递归算法复杂性的途径
null5.1代数变换减少子问题个数、实例
null5.2预处理减少递归的操作、实例
null六各类算法比较
null七思考题
21
分治思想在生活中普遍存在
所谓分而治之，如
null社会分工分工/干活/整体
null扑克牌分拣分工/分拣/合一
null下面我们一起看看“归并排序”这个算法
22
归并排序
null归并排序是大家十分熟悉的一种排序算法
null但是，大家有没有思考过导致归并算法高效
的本质原因是什么呢？
null好了，假设我们现在都不知道什么是归并排
序，让我们来把它“设计”出来！
null归并排序从头说…
23
考虑排序…
null对于单独的一个元素，不需要做任何比较和移动，
它已经有序了；
null对于两个元素，进行一次比较和最多一次移动，便
能将它们排序；
null对于三个元素，三次比较，最多两次移动，便能将
它们排序；
null……
null对于n个元素呢？
24
分而治之…
null对于n个元素，恩，看上去比较复杂。
null何不把它分成两个部分，先把两部分分别解决了，
再想办法将这两部分合并起来呢？
nulln个元素分成两半，每半最多只有[n/2]+1个元素，
当n>2时，[n/2]+1
小，而且可以预见，最终将会缩小到只剩1个或者2
个元素！
null1个或者2个元素的排序！呵呵。。。
25
“并”…
null别太得意，才想了一半呢！
null怎么把两个有序的子序列合并成一个有序序列呢？
null这个不难，用一个临时数组，将两个有序子序列中
的元素按大小依次倒进去就好了。时间复杂度为
O(n)。
null这样我们就从简单到复杂把归并排序‘设计’出来了！
26
分治法
null在我们把归并排序“想”出来的过程当中，用到
了这样三个思想：
null分——将问题分解为规模更小的子问题；
null治——将这些规模更小的子问题逐个击破；
null合——将已解决的子问题合并，最终得出“母”问
题的解。
null事实上，这便是分治思想了！怎么样？一点
也不神奇吧~
27
定义
null对于一个规模为n的问题，若该问题可以容易
地解决（比如说规模n较小）则直接解决，否
则将其分解为k个规模较小的子问题，这些子
问题互相独立且与原问题形式相同，递归地
解这些子问题，然后将各子问题的解合并得
到原问题的解。这种算法设计策略叫做分治
法。
28
分、治、合…
null请记住这三个字：
null分！
null治！
null合！
null这就是分治算法的精髓所在！一定要把握
住！
29
实例1：统计逆序对
null“统计逆序对个数”
null给n个数a
1
,a
2
…a
n
null如果存在存在a
i
>a
j
且i
i
,a
j
>为一个逆序对
null统计这n个数中逆序对的总数
null比如说，n=5，a
1
到a
5
分别为5,3,1,4,3
null则逆序对有
<5,3>,<5,1>,<5,4>,<5,3>,<3,1>,<4,3>共6对
30
解答
null朴素的O(n
2
)的算法
null既然在讲分治，当然应该用往分治方向想
啦！
null下面我们来看看怎么利用分治算法更高效地
解决这道题。
31
分、治
null分：类似于归并排序，我们将这n个数平均分成两
部分：a
1
~a
[n/2]
元素为第一部分，a
[n/2]+1
~a
n
为第二
部分
null治：在得到了规模较小的子问题后，我们分别“搞
定”它们，求出它们的逆序对个数。
null如果子问题元素个数仅仅一个，显然逆序对个数为0；
null如果元素为两个，那么第一个数大于第二个数则逆序对个
数为1，否则为0；
null若元素个数超过2个……
null递归伺候！将它继续分治。
32
合，怎么办？
null“合”这一步往往比较让人头疼，分治算法效率，往
往也取决于这一步做得怎么样。
null获利于“分”和“治”两步，我们现在已经知道a
1
~a
[n/2]
和a
[n/2]+1
~a
n
中逆序对的个数。
null而a
1
~a
n
中逆序对，不但包括分别处于两个子序列中
的逆序对，还包括第一个数在a
1
~a
[n/2]
中，第二个数
在a
[n/2]+1
~a
n
中的逆序对（为方便，我们称这种逆序
对为“另类逆序对”吧）。所以我们不能把两个子序
列中逆序对的个数单纯相加来得到答案。
33
这么合.
null当然，我们可以通过枚举来统计“另类逆序对”的个
数，可是时间效率……
null呵呵，这样还不如直接来O(n
2
)干脆多了
null但是，如果我们假设序列a
1
~a
[n/2]
和序列a
[n/2]+1
~a
n
已经分别有序呢？
null相信大家心中有数了，下面我们用一个直观的例子
来说明如何在两个有序的子序列中统计“另类逆序
对”个数。
34
例
null假设序列一为：1，3，5，6
序列二为：1，2，4，7
null在序列一中从小往大扫描：
null先扫描1，序列二中没有比1小的数；
null扫描到3，序列二中比3小的最大数是2，因此存在两个逆序对<3,2>,<3,1>
null扫描到5，序列二中比5小的最大数是4，因此存在三个逆序对
<5,4>,<5,2>,<5,1>
null扫描到6，序列二中比6小的最大数是4，同样存在三个逆序对
<6,4>,<6,2>,<6,1>
null共计8个“另类逆序对”
null因为序列一是从小到大扫描，序列二中的指针也总是右移的。
null这样仅仅扫描一遍，即O(n)的时间，便能统计“另类逆序对”的个数。
35
保证有序
null怎么样保证序列1和序列2有序呢？
null大家回忆一下归并排序，难道不觉得……
null好了，这道题我就讲到这里，留一点点同学
们自我思考的空间吧?
null时间复杂度将是O(nlogn)
36
实例2：导线与开关
null如图所示，一个黑盒里头有n根导线。
null黑盒有两个测试端，A端有n个接线头，每个接线
头都严格连接了黑盒内一根导线的一端；B端是n
个开关，开关连接导线的另一端。开关可以连接
任意多根导线，但是每根导线一端只能连接一个
开关。
null我们对这个黑盒进行测试，希望能用较少的测试
次数得到它内部每根导线的连接方式。
37
测试方法
null有以下两种测试方法：
null改变第k个开关的状态（往标准输出写入一行“Ck”，将在
标准输入中得到一行反馈“Y”或者“N”表示开关在操作后接
通或断开）；
null用一个带电源和灯泡的装置接通接线头j和所有开关，测试
它们之间是否有导线连接（往标准输出写入一行“Tj”将在
标准输入中得到一行反馈“Y”或者“N”表示灯亮或者不
亮）。
null在我们确定了黑盒内部结构之后，我们往标准输出中写
入一行“DA1A2…An”，表示第i个接线头与第Ai个开关
间有导线连接。
38
例子
null标准输出标准输入意义
nullC3Y开关3闭合
nullT1Y导线1与开关3连接
nullT2N导线2不与开关3连接
nullT3Y导线3与开关3连接
nullC3N开关3断开
nullC2Y开关2闭合
nullT2N导线2不与开关2连结
nullD313确定黑盒内部连接
39
朴素的思路
null低效的算法总是很容易想的?
null对于本题，我们可以每次接通一个开关，然
后试探所有的接线头，来看看它们之间有没
有导线连接。
null这种方法平均要n
2
次测试才能检测出黑盒内
部导线的连接情况。
40
分治的思路
null对于一个接线头一个开关的情况，我们可以
直接断定它们之间有导线连接；
null对于两个接线头两个开关的情况，最多进行3
次测试就能知道它们之间的连接情况；
null……
nulln个接线头m个开关呢？
41
分治思路
null假设n个开关编号为b
1
~b
n
，与之有导线连接的m个
接线头编号a
1
~a
n
，
null分：将n个开关分为两部分，b
1
~b
[(n+1)/2]
和b
[(n+1)/2]+1
~b
n
null治：我们将开关b
1
~b
[(n+1)/2]
改变状态，试探所有接
线头，便可以确定每个接线头是与开关b
1
~b
[(n+1)/2]
有关系还是与开关b
[(n+1)/2]+1
~b
n
连接了。然后我们
递归确定开关b
1
~b
[(n+1)/2]
和b
[(n+1)/2]+1
~b
n
具体连接方
式，除非n=2，因为开关分成两部分后各只有一
个，可以直接确定了。n=1当然也是。
null合：几乎没留下工作交给“合”。
42
复杂度分析
null设确定n对开关和接线头需要T(n)次操作，我
们假设每次都能将接线头和开关均分，可以
写递推方程如下：
nullT(n)=n/2+n+2T(n/2)，且T(1)=0
null这个方程的解T(n)=O(nlogn)
null但是我们要注意到这只是平均情况，在极端
坏情况下可能退化成O(n
2
)。和快速排序类
似，我们可以在划分开关的时候随机化来避
免出现这种极端情况。
43
二分查找
null在一个有序序列中，查找给定的元素，通常使用二分查找较
为高效。
null二分查找是分治算法中比较特殊的一类。
null分：将有序序列分为相等的两半
null治：比较需要查找元素的关键字和序列中位数比较，如果中
位数较小，则继续在较大的半段中继续查找；如果中位数较
大，则在较小的半段中查找；如果相等，则返回中位数地
址，查找成功。
null合：返回在自序列中查找的结果即可。
null二分查找的时间复杂度为O(logn)
44
实例3：查找两个不下降序列中位数
null给定两个长度为n的不下降序列a
1
~a
n
，
b
1
~b
n
，设计一个最坏情况下时间复杂度为
O(logn)的算法，找出两个序列中第n大的
数，即中位数。
null比如两序列分别为1,3,5,9和2,3,6,9，合并后
为1,2,3,3,5,6,9，其中第4大的数是3。
45
将问题变化一下
null不妨假设，两个序列合并后前n大的数包含p个序列a中的
数，q个序列b中的数。
null显然有p+q=n，而且a
p+1
>=b
q
，b
q+1
>=a
p
null反证一下：如果a
p+1
q
，而b
q
属于两序列合并后前n大的
数，那么a
p+1
也必然属于合并序列中前n大的数，这与开始的
假设是矛盾的。同理，b
q+1
p
也与假设矛盾。
null很容易证明，p+q=n以及a
p+1
>=b
q
，b
q+1
>=a
p
不光是必要条
件，同时也是充分条件(有一种特殊情况需要讨论一下)
null于是问题变化为，寻找满足上述两个条件的p和q，中位数即
为a
p
、b
q
中较大者。
46
二分查找
null由于p+q=n，即q=n-p，我们只需确定p。
null利用上页分析的性质，我们在序列a中进行二分查
找：
null假设当前查找区间为[x,y]，取区间中点m=[(x+y)/2]。
null若m满足a
m+1
>=b
n-m
且b
n-m+1
>=a
m
，那么m即为我们需要
的p，返回值；
null否则，若a
m+1
>=b
n-m
，则在区间[x,m-1]递归查找；不然，
在区间[m+1,y]中递归查找。
47
复杂度分析
null很显然，最多进行log
2
n次二分后，查找区间
将收缩为一个点。
null算法的最坏时间复杂度为O(logn)
48
特殊情况
null差点忘了提开始说的特殊情况了
null如果a，b合并后序列第n大的元素就是a
n
或者
b
n
的话，开始提及的公式就“越界”了，所以要
事先判断下：
null若a
1
>=b
n
，则中位数为b
n
；若b
1
>=a
n
，则中
位数为a
n
。
49
分治策略总结
null1分割分割成p个子问题。子问题间相互独立(才能分别求
解)。
null问题：应该把原问题分割成多少个子问题才合适？子问题规模是否
应该相同？
null答：需具体问题具体分析。一般来讲，均匀获得较好效果。举例。
null2求解如果子问题大于预定阈值m，则递归应用算法求解，
否则直接对子问题求解。
null问题：一般递归代价较大，故而有阈值m，那m如何确定。
null答：具体问题具体分析。严格数学分析，经验等。举例。
null3合并
null具体问题具体分析
50
划分原则
>>尽量均匀
null排序算法的比较
null插入排序
null子问题不均衡！
null归并排序
null子问题均衡！
2
W(n)=W(n-1)+n-1
W(1)=0
W(n)=(n)?Θ
k
n=2
W(n)=2W(n/2)+cn
W(1)=1
W(n)=(nlogn)?Θ
51
附0：直接插入排序
null逐个处理待排序的记录，当
处理第k个记录时，序号i
记录都已经排成序列R。
null把第k个记录与R中的记录依
次比较，直到找到待插入的
位置i然后插入之，形成新的
R
2
2
W(n)=W(n-1)+n-1
W(1)=0
W(n)=(n)
(n)
(n)
?Θ
Θ
Θ
52
分治法能解决的问题满足的特征
null最优子结构：该问题可以分解为若干个规模较小的
相同问题.(子问题与原问题相似,递归使用的必要条
件,分治法使用的前提,大部分问题可以满足).
null小规模可解易解：该问题的规模缩小到一定的程度
就可以容易地解决；(不断划分,子问题最终可解,这
是大多数问题都满足的条件)
null可以合并：利用该问题分解出的子问题的解可以合
并为该问题的解；(如果子问题可解,那么最终的问
题也可解,这是关键,分治法能否使用完全取决于这
一点)
53
)()()(
)()()(
1
nd
b
n
afnf
nginfanf
k
i
i
+=
+?=
∑
=
分治策略的算法分析工具----递推方程
定义
给定数列f(0),f(1),…,f(n),一个把f(n)和某些f(i)，
0≤i
给定关于f(n)的递推方程和初值，求f(n)称为解递推方程
两类递推方程
求解方法
第一类递推方程:公式法略
第二类递推方程:迭代法、递归树、Master定理
四递归算法与递推方程
54
当d(n)为常数时
?
?
?
=
≠
=
1)(log
1)(
)(
log
anO
anO
nf
a
b
当d(n)=cn时
?
?
?
?
?
>
=
<
=
banO
bannO
banO
nf
a
b
)(
)log(
)(
)(
log
)()()(nd
b
n
afnf+=
55
递归树法——迭代
例
2
)
2
(2)(n
n
TnT+=
22222
222
22
4
1
)
4
()
4
()
4
()
4
(
2
1
)
2
()
2
(
n
nnnn
n
nn
nn
%$%$
%$
logn层Θ（n
2
）
56
例
n
n
T
n
TnT++=)
3
2
()
3
()(
n
nnnn
n
nn
nn
9
4
9
2
9
2
9
3
2
3
%$%$
%$
log
3/2
n层Θ(nlogn)
57
Master定理
))(()(
),()/(
1,0),()(.3
)log()(),()(.2
)()(,0),()(1.
),()/()(
)(,)(1,1
log
loglog
loglog
nfnT
ncfbnafn
cnnf
nnnTnnf
nnTnOnf
nfbnaTnT
nTnfba
a
b
a
b
a
b
a
b
a
b
Θ=
≤
<>Ω=
Θ=Θ=
Θ=>=
+=
>≥
+
?
那么有所有的充分大的
和且对于某个常数
那么
那么
则有以下结果：
为非负整数为函数为常数，设
ε
ε
ε
ε
58
例
nnTnT+=)3/(9)(
)()(),()(
,,)(,3,9
219
3
log
29
3
log
nnTnOnf
nnnnfba
Θ==
====
?
例
1)3/2()(+=nTnT
)log()(),()(
,1,1)(,2/3,1
1log
01log
2/3
2/3
nnTnnf
nnnfba
Θ=Θ=
=====
例
nnnTnTlog)4/(3)(+=
)log()(
,4/3
),(log)4/3()4/log()4/(3)/(
,2.0),()(
),(,log)(,4,3
3
4
log
793.03
4
log
nnnT
nc
ncfnnnnbnaf
nnf
nOnnnnfba
Θ=
=
=≤=
≈Ω=
====
+
充分大
ε
ε
59
计算一个数的幂
60
61
62
63
五降低递归算法复杂性的途径
null5.1代数变换
null减少子问题个数
null5.2预处理
null递归算法中的处理步尽可能提到递归过程外,作
为预处理
64
5.1.代数变换减少子问题个数
位乘问题设X,Y是两个n位二进制数，
n=2
k
,求XY.
传统算法：一位一位的乘，W(n)=O(n
2
)
分治法：
令X＝A2
n/2
+B,Y=C2
n/2
+D.
XY=AC2
n
+(AD+BC)2
n/2
+BD
W(n)=4W(n/2)+cn,
W(1)=1
解得W(n)=O(n
log4
)=O(n
2
)
65
代数变换
AD+BC=(A－B)(D－C)+AC+BD
递推方程
W(n)=3W(n/2)+cn
W(1)=1
解
W(n)=O(n
log3
)=O(n
1.59
)
66
Strassen矩阵乘法问题
A,B为两个n阶矩阵，n=2
k
,计算C=AB.
传统算法W(n)=O(n
3
)
分治法将矩阵分块，得
其中
递推方程
W(n)=8W(n/2)+cn
2
W(1)=1
解W(n)=O(n
3
).
?
?
?
?
?
?
?
?
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2221
1211
2221
1211
2221
1211
CC
CC
BB
BB
AA
AA
2222122122
2122112121
2212121112
2112111111
BABAC
BABAC
BABAC
BABAC
+=
+=
+=
+=
67
分治变换方法
M
1
=A
11
(B
12
－B
22
)
M
2
=(A
11
+A
12
)
B22
M
3
=(A
21
+A
22
)B
11
M
4
=A
22
(B
21
－B
11
)
M
5
=(A
11
+A
22
)(B
11
+B
22
)
M
6
=(A
12
－A
22
)(B
21
+B
22
)
M
7
=(A
11
－A
21
)(B
11
+B
12
)
C
11
=M
5
+M
4
－M
2
+M
6
C
12
=M
1
+M
2
C
21
=M
3
+M
4
C
22
=M
5
+M
1
－M
3
－M
7
由Master定理得
2
22
()7()18()
(1)1
nn
WnW
W
=+
=
)()()(
8075.27log
2
nOnOnW==
68
5.2.预处理
递归算法中的处理步骤尽可能提到递归过程外,作为预处理
平面点对问题
输入：集合S中有n个点，n>1，
输出：所有的点对之间的距离。
通常算法：C(n,2)个点对计算距离，比较最小，需O(n
2
)时间
分治策略：取S的子集P，将P中的点划分成两个子集P
L
和P
R
?
?
?
?
?
?
=
?
?
?
?
?
?
=
2
||
||
2
||
||
P
P
P
P
RL
69
算法MinDistance(P,X,Y)
输入：n个点的点集P,X是横坐标的排序数组，Y是纵坐标的排序数组。
输出：最近的两个点及距离。
1.如果P中点数小于等于3，则直接计算其中的最小距离；
2.排序X,Y;
3．做垂直线l将P划分为P
L
和P
R
，P
L
的点在l左边，P
R
的点在l右边
4．MinDidtance(P
L
,X
L
,Y
L
);δ
L
=P
L
中的最小距离；
5．MinDistance(P
R
,X
R
,Y
R
);δ
R
=P
R
中的最小距离；
6．δ=min(δ
L
,δ
R
);
7．对于在垂直线两边距离δ范围内的每个点，
检查是否有点与它的距离小于δ，
如果存在则将δ修改为新值.
70
分析：步1O(1)
步2O(nlogn)
步3O(1)
步4-52T(n/2)
步6O(1)
步7O(n)
3)1()(
)log()
2
(2)(
≤=
+=
nOnT
nnO
n
TnT
由递归树估计T(n)=O(nlog
2
n).
nullδnull|
nullδnull|
|
null
δ
null
||
null
δ
null
|
71
预排序的处理方法
在每次调用时将已经排好的数组分成两个排序的子集，
每次调用这个过程的时间为O(n)
3)1()(
)()(2)(
)log()()(
2
≤=
+=
+=
nOnT
nOTnT
nnOnTnW
n
解得W(n)=O(nlogn).
72
六各类算法比较（1）
null分治法
null通过把问题化为较小的问题
来解决原问题，从而简化或
减少了原问题的复杂度
null贪心法
null通过分阶段地挑选最优解，
较快地得到整体的较优解，
在要求不太严格的情况下，
可用这个较优解替代最优解
null动态规划法
null用填表的方法保存了计算的
中间结果，从而避免了大量
重复的计算
null回溯法
null跳过大量无须测试的元组，
很快地得到需要的解
null分枝界限法
null在系统搜索问题解的空间
时，加入上下界的条件检查
以达到有效剪枝的目的
73
各类算法比较（2）
null这些方法的共同之处是运用技巧避免穷举测试
null分治法和动态规划法都是将问题分成子问题来做的
null贪心法、动态规划法以及回溯法都是从某一集合中选出子集，通过
一系列的判定来得到解
null贪心法、分枝界限法和回溯法都要进行逐项的测试比较逐步达到整
个解
null动态规划法和回溯法都是逐步逼近最优解而最终得到满足条件的解
null分枝界限法、动态规划法和回溯法得到问题的最优解
null贪心法既可能得到次优解，也可能得到最优解，依赖于具体
问题的特点和贪心策略的选取
74
七思考题
null一般性元素选择问题
输入：数组L，L的长度n，正整数k，1≤k≤n
输出：第k小的数
用分治法实现，算法复杂度可到W(n)=O(n)
75
参考文献
null屈婉玲，算法设计与分析讲义之顺序算法设计技
术，北京大学计算机系
null雷加贝，分治法讲稿，00448246
null王晓东，算法设计与分析，清华大学出版社，
2003，P108-141
null刘景，计算机算法引论----设计与分析技术，科学出
版社，2003年，P104-121
null原福永，算法设计与分析，机械工业出版社，
1998，P193-211
76
谢谢各位！
|
|
