调用函数和被调用函数是同一个函数，需要注意 的是途归函数的调用层次，如果把调用途归函数的 主函数称为第 0 层，进入函数后，首次途归调用自 身称为第 1 层调用；从第 i 层途归调用自身称为第 i +1 层。反之，退出第 i +1 层调用应该返回第 i 层。 采用图示方法描述途归函数的运行轨迹，从中可较 直观地了解到各调用层次及其执行情况。
mid= 1 low=2
7<14
Page 11
mid= 2
14=1 4
查找成功！
2015-4-12
定理2.1 任何基于比较的排序算法，对n个元素
进行排序的时间下界为Ω(nlog2n)
所谓（Optimality Algorithm）是指在某一种
度量标准下，优于该问题的所有（可能的）算法。
如果能够证明求解问题Π的任何算法的运行时间下
界是Ω(g(n))，那么，对以时间O(g(n))来求解问题 Π
问题描述：一个长度为n（n≥1）的升序序列 S，处在第n/2个位置的数称为序列S的中位 数 。两个序列的中位数是他们所有元素的升 序序列的中位数。现有两个等长升序序列A 和B，试设计一个在时间和空间两方面都尽 可能高效的算法，找出两个序列的中位数。
层治法只对一个子问题求解，并且不需要进行 解的合并。应用层治法（例如层半法）得到的算法 通常具有如下递推式： 0 n 1 T (n) n 1 T (n / 2) 1 所以，通常来说，应用层治法处理问题的效率 是很高的，一般是O(log2n)数量级。 对比分治法：
1. 循环直到序列A和序列B均只有一个元素 1.1 a = 序列A的中位数； 1.2 b = 序列B的中位数； 1.3 比较a和b，执行下面三种情况之一： 1.3.1 若a=b，则返回a，算法结束； 1.3.2 若a<b，则在序列A中舍弃a之前的元素， 在序列B中舍弃b之后的元素，转步骤1； 1.3.3 若a>b，则在序列A中舍弃a之后的元素， 在序列B中舍弃b之前的元素，转步骤1； 2. 序列 A和序列 B均只有一个元素，返回较小者；
如果k<rmid查找这里 如果k>rmid查找这里
Page 10第5章 层治法2源自15-4-1201
2
3
4
5
6
7
8
9
10
11
12
13
7 14 18 21 23 29 31 35 38 42 46 49 52 low=1
mid=7 31>14 18>1 mid= 4 high=6
high=13
3 high=2
8.2
图问题中的流塑法
8.2.46
二路归并排序设计思路
引理2.1 若T是至少具有n！和叶子结点的二叉树，则T的 高度至少是：nlog2n-1.5n=Ω(nlog2n)
• 通常称为信息论下界，说明任何基于比较的对n个元素 排序的算法，判定树的高度都不会大于Ω(nlog2n)。因 此，Ω(nlog2n)是这些算法的时间下界。
Page 7
g (n) T (n) 2T (n / 2) f (n)
n足够小
2015-4-12
想法：分别求出两个序列的中位数，记为a和b；比 较a和b，有下列三种情况： ① a = b：则a即为两个序列的中位数； ② a < b：则中位数只能出现在a和b之间，在序列 A中舍弃a之前的元素得到序列A1，在序列B中舍弃 b之后的元素得到序列B1； ③ a > b：则中位数只能出现在b和a之间，在序列 A中舍弃a之后的元素得到序列A1，在序列B中舍弃 b之前的元素得到序列B1； 在A1和B1中分别求出中位数，重复上述过程，直 到两个序列中只有一个元素，则较小者即为所求。
基本思想：在有序表中，取中间记录作为比较对象， 若给定值与中间记录的关键码相等，则查找成功；若给 定值小于中间记录的关键码，则在中间记录的左半区继 续查找；若给定值大于中间记录的关键码，则在中间记 录的右半区继续查找。不断重复上述过程，直到查找成 功，或所查找的区域无记录，查找失败。
k
[ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] （mid=(1+n)/2）
的任何算法，都认为是最优算法。
通常将存在多项式时间算法的问题看作是易解问题（Easy Problem），将
需要指数时间算法解决的问题看作是难解问题（Hard Problem）。
如果一个问题П 存在一个时间复杂性是O(nk)的算法，其中，n是问题规模，k 是一个非负整数，则称问题П存在多项式时间算法。 例：易解问题——排序问题、查找问题、欧拉回路 难解问题——TSP问题、 Hanio问题、Hamilton回路