第四章不相交集数据结构UnionFind介绍.ppt

* 定义4.2 对于任意整数，定义为： 0 若n=0或1 Log*n= min{i?0|loglog…logn?1} 若n?2. 共i个log 例如： Log*2=1,Log*4=2,Log*16=3,Log*65536=4, Log*265536=5。 * 定义单变量Ackerman函数F(n)=A(n,n),则有： 1 若j=0; F(j)= 2F(j-1) 若j?1. 显然，Log*n=min{j|F(j)?n}. F(j)的重要特性是其爆炸性的增长,例如： F(1)=2，F(2)=4， F(3)=16， F(4)=65536， F(5)=265536。 * 例如秩0和1在组0中，秩2在组1中，秩3和4在组2中，秩5到16在组3中，秩17到65536在组4中。 由推论4.1知：最大可能的秩是?logn?,故最大的组号至多是log*logn=log*n-1. 设?为m个合并和寻找指令的序列，我们把秩分成组，秩r放在组log*r中。 * 为了界定执行?序列中所有FIND指令的开销,我们利用“记账(bookkeeping)”方法进行分析。 把执行一条FIND指令的开销分为： FIND指令自身的开销与确定路径上的节 点(因为要压缩路径)的开销。则总的 开销即为所有FIND指令的开销加上所有 节点的开销。 * 计算FIND(u)指令的开销如下: 设v是在包含u的树中从节点u到根节点x的路径上的一个节点。 (1)如果v是根，或者是根的一个子节点， 或者FATHER[v]与v在不同的秩组时，那么令FIND指令花费一个时间单元； (2)如果v?x并且v和FATHER[v]在相同的秩组时，那么令v花费一个时间单元。 * 注意到从u到x的路径上各节点的秩是单调递增的,又至多有log*n个不同的秩组，因此FIND(i)指令的花费不会超过O(log*n)个时间单元, 从而，在规则(1)下?序列中的所有s个FIND指令花费的总的时间单元数是O(s log*n)。 * 对于规则(2)的情景，节点v将被移动为秩比FATHER[v]更高的节点的孩子。 如果节点v是在秩组g0中，那么节点v在从更高的秩组中获得父节点之前可以移动，且开销至多是F(g)-F(g-1)的时间。 如果节点是在秩组0中，移动v的开销将作为指令FIND的,因为此时至多移动一次。 * 下面求所有节点自身开销的一个上界： 由引理4.2可知，秩为r的节点个数至多是n/2r，秩组g中的节点个数至多是： 由于秩组g0中任意节点的花费小于等 于F(g)-F(g-1)，那么秩组g0中所有节 点的花费是： * 由于至多有log*n个秩组(0,1,…,log*n-1)则所有节点的开销总数为O(nlog*n)。 综上可得，m个UNION和FIND指令的?序列的开销总数T(m)为： ?(mlog*n)+?(nlog*n)=?((m+n)log*n) 由于在实际应用中log*n?5，因此m个 UNION和FIND指令的?序列的开销总数 为： T(m)=?(m+n). 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * * 一个n元素的堆的高度是 ，在任意的高度h上，最多有结点数 设SIFT-DOWN()在h层上的作用时间是O(h)，则应该有一个上确界： （1） * 数论上存在如下等式成立： 设x=1/2带入（1）的右边的和式 * 4.2.3 堆排序 算法SELECTIONSORT(选择排序)的复杂度： 用线性有哪些信誉好的足球投注网站来找最小值的时间需要用Θ(n)的时间，算法就要用Θ(n2) 时间。 如何提高选择排序的复杂度呢，使用堆是一个好的选择。 * 给出数组A[1…n]，将其中的元素用如下方法以非降序有效排序。 step 1.首先将A变换成堆，并使其具有这样的性质，每个元素的键值是该元素本身，即key(A[i])= A[i],1 ≤i ≤n。 * step 2.由于A中各项的最大值存储在A[1]中，可以将A[1] 和A[n]交换，使得A[n]是数组中最大元素。