算法分析-2016

算法分析(3)重要的数据结构二分查找（BinarySearch）1.判定树判定树适合于描述具有层次结构的数据树的定义树(tree)t是一个非空的有限元素的集合.其中一个元素为根(root),余下的元素(如果有的话)组成t的子树(subtree).层数(Level):指定树根的层数为1,其子节点(如果有)的层数为2,子节点的子节点的层数为3,等等。节点的度(degreeofanelement)是指其孩子的个数。树的度(degreeofatree)是其元素度的最大值。二叉树二叉树(binarytree)t是有限个元素的集合(可以为空).当二叉树非空时,其中有一个称为根的元素.余下的元素(如果有的话)被组成2个二叉树,分别称为t的左子树和右子树.二叉树的高度(height)或深度(depth)是指该二叉树的层数.从根节点到每个节点有唯一一条路径,路径上的边数称为该路径的长度.二叉树的数学性质性质1:包含n(n0)个元素的树的边数为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;有n个节点的扩充二叉树,当外节点分布在相邻两层时其深度,外路和内路长度达到最小(平衡原理).设扩充前深度为k,则有:2k-1≤n2k＝k=+1nlog续设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)二分查找判定树二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(DecisionTree)或比较树(ComparisonTree)。注意：判定树的形态只与结点个数n相关，而与输入实例中R[1..n]关键字的取值无关。具有11个结点的有序表可用下图所示的判定树来表示二分查找判定树的组成①圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。②外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。③树中某结点i与其左(右)孩子连接的左(右)分支上的标记、(、、)表示：当待查关键字KR[i].key(KR[i].key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。续二分查找算法的判定树为有n个内节点的扩充二叉树而且叶节点分布在相邻两层:二分查找算法最坏和平均情形的时间复杂度为基于关键字比较的有序表查找算法至少要做次比较)(logn)(logn2.等价类问题假定有一个具有n个元素的集合U={1，2，...，n}，另有一个具有r个关系的集合R={(i1,j1),(i2,j2),...,(ir,jr)}。关系R是一个等价关系（equivalencerelation），当且仅当如下条件为真时成立：•对于所有的a，有(a,a)∈R时（即关系是反身的）•当且仅当(b,a)∈R时(a,b)∈R（即关系是对称的）•若(a,b)∈R且(b,c)∈R，则有(a,c)∈R（即关系是传递的）在给出等价关系R时，我们通常会忽略其中的某些关系，这些关系可以利用等价关系的反身、对称和传递属性来获得例3-3假定n=14，R={(1,11)，(7,11)，(2,12)，(12,8)，(11,12)，(3,13)，(4,13)，(13,14)，(14,9)，(5,14)，(6,10)}。我们忽略了所有形如(a,a)的关系，因为按照反身属性，这些关系是隐含的。同样也忽略了所有的对称关系。比如(1,11)∈R，按对称属性应有(11,1)∈R。其他被忽略的关系是由传递属性可以得到的属性。例如根据(7,11)和(11,12)，应有(7,12)∈R。等价类（equivalenceclass）是指相互等价的元素的最大集合。“最大”意味着不存在类以外的元素，与类内部的元素等价。考察例3-3中的等价关系。由于元素1与11，11与12是等价的，因此，元素1,11,12是等价的，它们应属于同一个等价类。不过，这三个元素还不能构成一个等价类，因为还有其他的元素与它们等价（如7）。所以{1,11,12}不是等价元素的最大集合。集合{1,2,7,8,11,12}才是一个等价类。关系R还定义了另外两个等价类：{3,4,5,9,13,14}和{6,10}。离线等价类（offlineequivalenceclass）：已知n和R，确定所有的等价类。在线等价类（onlineequivalenceclass）：初始时有n个元素，每个元素都属于一个独立的等价类。需要执行以下的操作Combine(a,b)把包含a和b的等价类合并成一个等价类。Find(e)确定哪个类包含元素e，搜索的目的是为了确定给定的两个元素是否在同一个类之中可以利用两个Find操作和一个Union操作产生一个组合操作，该操作能把两个不同的类合并成一个类。Combine(a,b)等价于：i=Find(a);j=Find(b);if(i!=j)Union(i,j);在线等价类在线等价类问题也称作离散集合合并/搜索问题（disjointsetunion-findproblem）Union-Find数据结构设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值。Initialize和Union函数的复杂性均为Θ(n)，Find的复杂性为Θ(1)。在应用这些函数时，通常执行一次初始化，u次合并和f次搜索，故所需要的总时间为Θ(n+u*n+f)=Θ(u*n+f)。第二种解决方案针对每个等价类设立一个相应的链表，可以降低合并操作的时间复杂性，可以沿着类j的链表找到所有E[k]=j的元素，而不必去检查所有的E值在使用链表时，初始化和搜索操作的复杂性仍分别保持为Θ(n)和Θ(1)。每次合并操作的开销为(较小类的大小)。令i表示合并操作中的较小类。在合并期间，i中的每个元素从类i移向类j，因此u次合并的复杂性由移动元素的总次数确定。移动类i之后，新类的大小至少是类i的两倍（因为在移动前有size[i]≤size[j]，而移动之后新类的大小为size[i]+size[j]）。因此，由于在操作结束时没有哪个类的元素数会超过u+1，所以在u次合并期间，没有哪个元素的移动次数超过log2(u+1)。在u次合并过程中，最多可以移动2u个元素，所以，元素移动的总次数不会超过2ulog2(u+1)。至此可以知道执行u次合并操作所需要的时间为O(ulogu)1次初始化、u次合并操作和f次搜索的复杂性为O(n+ulogu+f)在线等价类的第三种解决方案把每个集合(类)描述为一棵树而树中每个非根节点都指向其父节点用根元素作为集合标识符如图8.15Union-Find算法集合的树表示Union-Find算法Program8.15Simpletreesolutiontounion-findproblem算法复杂性假设要执行u次合并和f次查找。因为每次合并前都必须执行两次查找，因此可假设f＞u。每次合并所需时间为Θ(1)。而每次查找所需时间由树的高度决定。在最坏情况下，有m个元素的树的高度为m。若使用重量规则(高度规则)，合并和查找序列的代价(不包括初始化时间)为O(u＋flogu)图8.17Union图8.18Twosampletrees算法改进使用加权规则定义[重量规则]若树i节点数少于树j节点数，则将j作为i的父节点。否则，将i作为j的父节点。定义[高度规则]若树i的高度小于树j的高度，则将j作为i的父节点，否则将i作为j的父节点。加权规则(Weightrule)续Program8.16UnioningwiththeweightruleWeightrulelemma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)1logp1log11pd1log22pd1logp优先队列问题优先队列中元素出队列的顺序由元素的优先级决定。例：假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，将他/她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。第一种方案1）采用无序线性表描述最大优先队列假设有一个具有n个元素的优先队列，插入操作可以十分容易地在表的右端末尾执行，插入所需时间为Θ(1)。删除操作时必须查找优先权最大的元素，即在未排序的n个元素中查找具有最大优先权的元素，所以删除操作所需时间为Θ(n)2）采用有序线性表删除时间均为Θ(1)，插入操作所需时间为Θ(n)第二种方案可以利用堆数据结构来高效地实现优先队列定义[最大树（最小树）]每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于2。定义[最大堆（最小堆）]最大（最小）的完全二叉树。Heaps图9.3Insertionintoamaxheap图9.4Deletionfromamaxheap图9.5Initializingamaxheap图9.5Initializingamaxheap(续)堆排序分析n个节点的完全二叉树的深度为堆插入和删除需即堆排序时间为O(nlogn)初始化:O(nlogn))1log(n)(logn1lognk