算法分析(3) 重要的数据结构

二分查找（Binary Search） 折半查找or 二分查找

1. 判定树 判定树适合于描述具有层次结构的数据

树的定义 树(tree) t 是一个非空的有限元素的集合.其中一个元素为根(root),余下的元素(如果有的话)组成t 的子树(subtree). 层数(Level):指定树根的层数为1,其子节点(如果有)的层数为2,子节点的子节点的层数为3,等等。 节点的度(degree of an element)是指其孩子的个数。 树的度(degree of a tree)是其元素度的最大值。

二叉树 二叉树(binary tree)t 是有限个元素的集合(可以为空).当二叉树非空时,其中有一个称为根的元素.余下的元素(如果有的话)被组成2个二叉树,分别称为t的左子树和右子树. 二叉树的高度(height)或深度(depth)是指该二叉树的层数. 从根节点到每个节点有唯一一条路径,路径上的边数称为该路径的长度.

二叉树的数学性质 性质1 :包含n (n>0)个元素的树的边数为n-1. 性质2 :若二叉树的高度为h,h≥0,则该二叉树最少有h个元素,最多有2h-1个元素. 性质3 :包含n个元素的二叉树的高度最大为n,最小为「log2(n+ 1)ù: n≤ 2h-1=>2h≥n+1 所以,h≥log2 (n+1),即: h≥「log2(n+ 1)ù

续 扩充的二叉树:补齐外节点的二叉树.设n为其内节点数,则外节点数为n+1; 设扩充前深度为k,则有: 2k-1≤n<2k＝>k= +1

续 设E为根节点到外节点的路径长度之和; I为根节点到内节点的路径长度之和. 对有n个内节点的扩充二叉树,用归纳法可证明: E=I+2n (练习) 假定扩充二叉树的外节点分布在相邻两层则:E=m(k-1)+(n+1-m)k,其中m为第k层上的外节点数.又因外节点数n+1=m+2(2k-1-m),所以:m=2k-(n+1), E=(k+1)(n+1)-2k

二分查找的平均复杂度 设I为内路长度,E为外路长度,则: 平均失败查找次数U(n)=E/(n+1); 平均成功查找次数S(n)=(I+n)/n 平均失败查找次数U(n)=E/(n+1)=Θ(logn) 平均成功查找次数S(n)=(I+n)/n= Θ(logn)

二分查找判定树 二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。 注意：     　判定树的形态只与结点个数n相关，而与输入实例中R[1..n]关键字的取值无关。

具有11个结点的有序表可用下图所示的判定树来表示

二分查找判定树的组成 　 　①圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。 ②外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。 ③树中某结点i与其左(右)孩子连接的左(右)分支上的标记"<"、"("、">"、")"表示：当待查关键字K<R[i].key(K>R[i].key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。

续 二分查找算法的判定树为有n个内节点的扩充二叉树而且叶节点分布在相邻两层:二分查找算法最坏和平均情形的时间复杂度为 基于关键字比较的有序表查找算法至少要做 次比较

2. 等价类问题 假定有一个具有n 个元素的集合U= { 1，2，. . .，n}，另有一个具有r 个关系的集合R= { (i1, j1) ,(i2 , j2 ), ..., (ir , jr ) }。关系R是一个等价关系（equivalence relation），当且仅当如下条件为真时成立： • 对于所有的a，有(a, a) ∈R 时（即关系是反身的） • 当且仅当(b, a) ∈ R时(a, b) ∈ R（即关系是对称的） • 若(a, b) ∈R且(b, c) ∈R，则有(a, c) ∈R（即关系是 传递的）

在给出等价关系R时，我们通常会忽略其中的某些关系，这些关系可以利用等价关系的反身、对称和传递属性来获得 例3-3 假定n= 1 4，R= { ( 1 , 11 )，( 7 , 11 )，( 2 , 1 2 )，( 1 2 , 8 )，( 11 , 1 2 )，( 3 , 1 3 )，( 4 , 1 3 )，( 1 3 , 1 4 )，( 1 4 , 9 )，( 5 , 1 4 )，( 6 , 1 0 ) }。 我们忽略了所有形如( a , a )的关系，因为按照反身属性，这些关系是隐含的。同样也忽略了所有的对称关系。 比如( 1 , 11) ∈R，按对称属性应有( 11,1) ∈ R。其他被忽略的关系是由传递属性可以得到的属性。例如根据( 7 , 11) 和( 11 , 1 2 )，应有(7,12) ∈R。

等价类（equivalence class）是指相互等价的元素的最大集合。 “最大”意味着不存在类以外的元素，与类内部的元素等价。 考察例3-3中的等价关系。 由于元素1与11，11与1 2是等价的，因此，元素1 , 11 , 1 2是等价的，它们应属于同一个等价类。不过，这三个元素还不能构成一个等价类，因为还有其他的元素与它们等价（如7）。所以{ 1 , 11 , 1 2 }不是等价元素的最大集合。集合{ 1 , 2 , 7 , 8 , 11 , 1 2 }才是一个等价类。 关系R还定义了另外两个等价类：{ 3 , 4 , 5 , 9 , 1 3 , 1 4 }和{ 6 , 1 0 }。

离线等价类（offline equivalence class）：已知n 和R，确定所有的等价类。 在线等价类（online equivalence class）：初始时有n 个元素，每个元素都属于一个独立的等价类。需要执行以下的操作 Combine(a, b) 把包含a 和b 的等价类合并成一个等价类。 Find(e) 确定哪个类包含元素e，搜索的目的是为了确定给定的两个元素是否在同一个类之中 可以利用两个F i n d操作和一个U n i o n操作产生一个组合操作，该操作能把两个不同的类合并成一个类。 C o m b i n e ( a , b )等价于：i = Find(a); j = Find(b); if(i! = j) Union(i, j);

在线等价类 在线等价类问题也称作离散集合合并/搜索问题（disjoint set union-find problem） 设U={1,2,…,n},Ai是U的某些不交子集； union(Ai,Aj)指对这些子集中的Ai和Aj做并操作Ai∪Aj; find(x),x∈U,指找x所在的子集Ai, 即,x∈Ai; 假定初始有n个单元素的子集Ai={i},1≤i≤n; 试图找一种表示集合的数据结构和算法,使得在线(online)地执行任何n-1个union和m≥n个find操作的混合序列的累积时间接近线性的.

第一种解决方案 在线等价类问题的一种简单解决办法是使用一个数组E，并令E(e) 为代表包含元素e 的等价类。 完成初始化、合并及搜索操作的函数如程序3-46所示。 N 是元素的数目，n 和E 均被定义为全局变量。为了合并两个不同的类，可从类中任取一个元素，然后把该类中所有元素的E 值修改成另一个类中元素的E 值。 I n i t i a l i z e和U n i o n函数的复杂性均为Θ(n)，F i n d的复杂性为Θ( 1 )。 在应用这些函数时，通常执行一次初始化，u 次合并和f 次搜索，故所需要的总时间为Θ( n +u* n +f ) = Θ (u* n +f )。

第二种解决方案 针对每个等价类设立一个相应的链表，可以降低合并操作的时间复杂性，可以沿着类j的链表找到所有E[k]=j 的元素，而不必去检查所有的E值 在使用链表时，初始化和搜索操作的复杂性仍分别保持为Θ( n )和Θ( 1 )。 每次合并操作的开销为(较小类的大小)。令i 表示合并操作中的较小类。在合并期间， i 中的每个元素从类i 移向类j，因此u次合并的复杂性由移动元素的总次数确定。移动类i 之后，新类的大小至少是类i 的两倍（因为在移动前有s i z e [ i ]≤s i z e [ j ]，而移动之后新类的大小为s i z e [ i ] + s i z e [ j ]）。因此，由于在操作结束时没有哪个类的元素数会超过u+ 1，所以在u 次合并期间，没有哪个元素的移动次数超过l o g2 (u+ 1 )。在u次合并过程中，最多可以移动2u 个元素，所以，元素移动的总次数不会超过2u l o g2 (u+ 1 )。至此可以知道执行u 次合并操作所需要的时间为O (ul o gu) 1次初始化、u次合并操作和f 次搜索的复杂性为O (n+u l o gu+f) 定理3-1 如果开始时有n 个类，每个类有一个元素，则在执行u 次合并操作以后， a) 任何一个类的元素数都不会超过u+ 1。 b) 至少存在n- 2u个单元素类。 c) u < n。

在线等价类的第三种解决方案 把每个集合(类)描述为一棵树 而树中每个非根节点都指向其父节点 用根元素作为集合标识符 如图8.15

Union-Find算法

集合的树表示

Union-Find算法 Program 8.15 Simple tree solution to union-find problem

算法复杂性 假设要执行u 次合并和f 次查找。因为每次合并前都必须执行两次查找，因此可假设f＞u。 每次合并所需时间为Θ( 1 )。而每次查找所需时间由树的高度决定。在最坏情况下，有m个元素的树的高度为m。 若使用重量规则(高度规则)，合并和查找序列的代价(不包括初始化时间)为 O (u＋f l o gu)

图8.17 Union

图8.18 Two sample trees

算法改进 使用加权规则 定义[重量规则] 若树i 节点数少于树j 节点数，则将j 作为i 的父节点。否则，将i 作为j 的父节点。

加权规则(Weight rule)

续 Program 8.16 Unioning with the weight rule

Weight rule lemma Lemma8.1 假定从单元素集开始执行加权并. 设t是上述过程产生的有p个节点的一棵树,则t的深度不超过 证明:设t1,t2为产生t的Union序列中最后一次合并前的树. 设t1、t2的节点数为p1和p2,(均小于p),又设p1≤p2 ,对p1和p2用归纳假设: t的深度d=d2 或d1+1,无论何种情形都有 d≤ (1+logp1=log2p1≤log(p1+p2)=logp)

优先队列问题 优先队列中元素出队列的顺序由元素的优先级决定。 例：假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，将他/她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。 如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。

第一种方案 1）采用无序线性表描述最大优先队列 2）采用有序线性表 假设有一个具有n 个元素的优先队列，插入操作可以十分容易地在表的右端末尾执行，插入所需时间为Θ( 1 )。删除操作时必须查找优先权最大的元素，即在未排序的n 个元素中查找具有最大优先权的元素，所以删除操作所需时间为Θ(n) 2）采用有序线性表 删除时间均为Θ( 1 )，插入操作所需时间为Θ(n)

第二种方案 可以利用堆数据结构来高效地实现优先队列 定义[最大树（最小树）] 每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。 最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于2。 定义[最大堆（最小堆）] 最大（最小）的完全二叉树。

Heaps

图9.3 Insertion into a max heap

图9.4 Deletion from a max heap

图9.5 Initializing a max heap

图9.5 Initializing a max heap(续)

堆排序分析 n个节点的完全二叉树的深度为 堆插入和删除需 即 堆排序时间为O(nlogn) 初始化:O(nlogn)