第二章-算法分析优秀文档.ppt

第二章算法分析(3)重要的数据结构BinarySearch1.判定树n判定树适合于描述具有层次结构层次结构的数据树的定义n树(tree)t是一个非空的有限元素的集合非空的有限元素的集合.其中一个元素为根(root),余下的元素(如果有的话)组成t的子树(subtree).n层数层数(Level):指定树根的层数为1,其子节点(如果有)的层数为2,子节点的子节点的层数为3,等等。n节点的度节点的度(degreeofanelement)是指其孩子的个数。n树的度树的度(degreeofatree)是其元素度的最大值。二叉树二叉树n二叉树(binarytree)t是有限个元素有限个元素的集合(可以为空).当二叉树非空时,其中有一个称为根的元素.余下的元素(如果有的话)被组成2个二叉树,分别称为t的左子树和右子树.n二叉树的高度高度(height)或深度(depth)是指该二叉树的层数.n从根节点到每个节点有唯一一条路径,路径上的边数称为该路径的长度长度.二叉树的数学性质n性质性质1:包含n(n0)个元素的树的边数为n-1.n性质性质2:若二叉树的高度为h,h0,则该二叉树最少有h个元素,最多有2h-1个元素.n性质性质3:包含n个元素的二叉树的高度最大为n,最小为log2(n+1):n2h-1=2hn+1所以,hlog2(n+1),即:hlog2(n+1)续n扩充的二叉树扩充的二叉树:补齐外节点的二叉树.设n为其内节点数,则外节点数为n+1;n1nk1+2(k-2)n2kn有n个节点的扩充二叉树,当外节点分布在相邻两层时其深度,外路和内路长度达到最小(平衡原理平衡原理).n设扩充前深度为k,则有:2k-1nk=+1续n设E为根节点到外节点的路径长度之和;I为根节点到内节点的路径长度之和.n对有n个内节点的扩充二叉树,用归纳法可证明:E=I+2n(练习)n假定扩充二叉树的外节点分布在相邻两层则: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二分查找的平均复杂度n设I为内路长度,E为外路长度,则:平均失败查找次数U(n)=E/(n+1);平均成功查找次数S(n)=(I+n)/nn平均失败查找次数U(n)=E/(n+1)=(logn)n平均成功查找次数S(n)=(I+n)/n=(logn)二分查找判定树二分查找判定树n二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(DecisionTree)或比较树(ComparisonTree)。n注意：判定树的形态只与表结点个数n相关，而与输入实例中R1.n关键字的取值无关。n具有11个结点的有序表可用下图所示的判定树来表示 n二分查找判定树的组成圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。树中某结点i与其左(右)孩子连接的左(右)分支上的标记、)表示：当待查关键字KRi.key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。续n二分查找算法的判定树为有n个内节点的扩充二叉树而且叶节点分布在相邻两层:二分查找算法最坏和平均情形的时间复杂度为n基于关键字比较的有序表查找算法至少要做次比较等价类问题n假定有一个具有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（即关系是 传递的）n在给出等价关系R时，我们通常会忽略其中的某些关系，这些关系可以利用等价关系的反身、对称和传递属性来获得n例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)。n我们忽略了所有形如(a,a)的关系，因为按照反身属性，这些关系是隐含的。同样也忽略了所有的对称关系。n比如(1,11)R，按对称属性应有(11,1)R。其他被忽略的关系是由传递属性可以得到的属性。例如根据(7,11)和(11,1 2)，应有(7,12)R。n等价类等价类（equivalence class）是指相互等价）是指相互等价的元素的最大集合。的元素的最大集合。n“最大最大”意味着不存在类以外的元素，与类内意味着不存在类以外的元素，与类内部的元素等价。部的元素等价。n考察例3-3中的等价关系。n由于元素1与11，11与12是等价的，因此，元素1,11,12是等价的，它们应属于同一个等价类。不过，这三个元素还不能构成一个等价类，因为还有其他的元素与它们等价（如7）。所以1,11,12不是等价元素的最大集合。集合1,2,7,8,11,12才是一个等价类。n关系R还定义了另外两个等价类：3,4,5,9,13,14和6,10。n离线等价类离线等价类（offline equivalence class）：已知n 和R，确定所有的等价类。n在线等价类在线等价类（online equivalence class）：初始时有n 个元素，每个元素都属于一个独立的等价类。需要执行以下的操作nCombine(a,b)把包含a和b的等价类合并成一个等价类。nFind(e)确定哪个类包含元素e，搜索的目的是为了确定给定的两个元素是否在同一个类之中n可以利用两个Find操作和一个Union操作产生一个组合操作，该操作能把两个不同的类合并成一个类。nC o m b i n e(a,b)等价于：i=Find(a);j=Find(b);if(i!=j)Union(i,j);在线等价类n在线等价类问题也称作离散集合合并/搜索问题（disjoint set union-find problem）nUnion-Find数据结构n设U=1,2,n,Ai是U的某些不交子集；nunion(Ai,Aj)指对这些子集中的Ai和Aj做并操作AiAj;nfind(x),xU,指找x所在的子集Ai,即,xAi;n假定初始有n个单元素的子集Ai=i,1in;n试图找一种表示集合的数据结构和算法,使得在线(online)地执行任何n-1个union和mn个find操作的混合序列的累积时间接近线性的.n链表不是一个好的选择:find为O(n)假定初始有n个单元素的子集Ai=i,1in;union(Ai,Aj)指对这些子集中的Ai和Aj做并操作AiAj;所以 1,11,1 2 不是等价元素的最大集合。1次初始化、u次合并操作和f 次搜索的复杂性为O(n+u l o gu+f)否则，将i 作为j 的父节点。性质1:包含n(n0)个元素的树的边数为n-1.删除时间均为(1)，插入操作所需时间为(n)若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。针对每个等价类设立一个相应的链表，可以降低合并操作的时间复杂性，可以沿着类j的链表找到所有Ek=j 的元素，而不必去检查所有的E值定义重量规则 若树i 节点数少于树j 节点数，则将j 作为i 的父节点。当二叉树非空时,其中有一个称为根的元素.考察例3-3中的等价关系。n关键字的取值无关。为了合并两个不同的类，可从类中任取一个元素，然后把该类中所有元素的E 值修改成另一个类中元素的E 值。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。Union-Find算法第一种解决方案n在线等价类问题的一种简单解决办法是使用一个数组E并令E(e)代表包含元素e 的等价类。n完成初始化、合并及搜索操作的函数如程序3-46所示。nN 是元素的数目，n 和E 均被定义为全局变量。为了合并两个不同的类，可从类中任取一个元素，然后把该类中所有元素的E 值修改成另一个类中元素的E 值。nI n i t i a l i z e和U n i o n函数的复杂性均为(n)，F i n d的复杂性为(1)。n在应用这些函数时，通常执行一次初始化，u 次合并和f 次搜索，故所需要的总时间为(n+u*n+f)=(u*n+f)。第二种解决方案n针对每个等价类设立一个相应的链表，可以降低合并操作的针对每个等价类设立一个相应的链表，可以降低合并操作的时间复杂性，可以沿着类时间复杂性，可以沿着类j的链表找到所有的链表找到所有Ek=j 的元素，的元素，而不必去检查所有的而不必去检查所有的E值值n在使用链表时，初始化和搜索操作的复杂性仍分别保持为在使用链表时，初始化和搜索操作的复杂性仍分别保持为(n)和和(1)。n每次合并操作的开销为每次合并操作的开销为(较小类的大小较小类的大小)。令。令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)n1次初始化、次初始化、u次合并操作和次合并操作和f 次搜索的复杂性为次搜索的复杂性为O(n+u l o gu+f)在线等价类的第三种解决方案n把每个集合(类)描述为一棵树n而树中每个非根节点都指向其父节点n用根元素作为集合标识符Union-Find算法集合的树表示Union-Find算法Program 8.15 Simple tree solution to union-find problem算法复杂性n假设要执行u 次合并和f 次查找。因为每次合并前都必须执行两次查找，因此可假设fu。n每次合并所需时间为(1)。而每次查找所需时间由树的高度决定。在最坏情况下，有m个元素的树的高度为m。图8.17Union图8.18Twosampletrees我们忽略了所有形如(a,a)的关系，因为按照反身属性，这些关系是隐含的。扩充的二叉树:补齐外节点的二叉树.18 Two sample trees5 Initializing a max heap判定树适合于描述具有层次结构的数据而树中每个非根节点都指向其父节点对有n个内节点的扩充二叉树,用归纳法可证明:E=I+2n (练习)1次初始化、u次合并操作和f 次搜索的复杂性为O(n+u l o gu+f)在使用链表时，初始化和搜索操作的复杂性仍分别保持为(n)和(1)。对有n个内节点的扩充二叉树,用归纳法可证明:E=I+2n (练习)在线等价类（online equivalence class）：初始时有n 个元素，每个元素都属于一个独立的等价类。树(tree)t 是一个非空的有限元素的集合.扩充的二叉树:补齐外节点的二叉树.算法改进n使用加权规则n定义重量规则 若树i 节点数少于树j 节点数，则将j 作为i 的父节点。否则，将i 作为j 的父节点。n定义高度规则 若树i 的高度小于树j 的高度，则将j 作为i 的父节点，否则将i 作为j 的父节点。加权规则(Weightrule)续Program 8.16 Unioning with the weight ruleWeightrulelemman 假定从单元素集开始执行加权并.设t是上述过程产生的有p个节点的一棵树,则t的深度不超过n 证明:设t1,t2为产生t的Union序列中最后一次合并前的树.设t1、t2的节点数为p1和p2,(均小于p),又设p1p2,对p1和p2用归纳假设:nt的深度d=d2 或d1+1,无论何种情形都有 d (1+logp1=log2p1log(p1+p2)=logp)优先队列问题n优先队列中元素出队列的顺序由元素的优先级决定。优先队列中元素出队列的顺序由元素的优先级决定。n例：假设我们对机器服务进行收费。每个用户每次使用机器例：假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，权即为用户所需服务时间。当一个新的用户需要使用机器时，将他将他/她的请求加入优先队列。一旦机器可用，则为需要最她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。少服务时间（即具有最高优先权）的用户提供服务。n如果每个用户所需时间相同，但用户愿意支付的费用不同，如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，所交费用最则可以用支付费用作为优先权，一旦机器可用，所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。多的用户可最先得到服务，这时就要选择最大优先队列。第一种方案n1）采用无序线性表描述最大优先队列n假设有一个具有n 个元素的优先队列，插入操作可以十分容易地在表的右端末尾执行，插入所需时间为(1)。删除操作时必须查找优先权最大的元素，即在未排序的n 个元素中查找具有最大优先权的元素，所以删除操作所需时间为(n)n2）采用有序线性表n删除时间均为(1)，插入操作所需时间为(n)第二种方案n可以利用堆数据结构来高效地实现优先队列n定义最大树（最小树）每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。n最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于2。n定义最大堆（最小堆）最大（最小）的完全二叉树。Heaps图9.3Insertionintoamaxheap而树中每个非根节点都指向其父节点n个节点的完全二叉树的深度为删除时间均为(1)，插入操作所需时间为(n)对有n个内节点的扩充二叉树,用归纳法可证明:E=I+2n (练习)假定有一个具有n 个元素的集合U=1，2，.删除时间均为(1)，插入操作所需时间为(n)在线等价类的第三种解决方案3 Insertion into a max heap否则，将i 作为j 的父节点。扩充的二叉树:补齐外节点的二叉树.Find(e)确定哪个类包含元素e，搜索的目的是为了确定给定的两个元素是否在同一个类之中15 Simple tree solution to union-find problem每次合并所需时间为(1)。删除操作时必须查找优先权最大的元素，即在未排序的n 个元素中查找具有最大优先权的元素，所以删除操作所需时间为(n)最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于2。2k-1nk=+1图9.4Deletionfromamaxheap图9.5Initializingamaxheap图9.5Initializingamaxheap(续)堆排序分析nn个节点的完全二叉树的深度为n堆插入和删除需 即n堆排序时间为O(nlogn)n初始化:O(nlogn)