计算机算法基础 第2版 习题及答案 第17章

PAGE7第17章平摊分析和斐波那契堆假设对某个数据结构作n个操作。第i个操作实际需要的时间c(i)是：如果i正好是2的整数k次方，即i=2k，那么c(i)=i，否则c(i)=1。请用聚集法分析其平摊时间a(i)。解： 这n个操作总共需要的时间是：T(n)=i=1nc(i)=1≤i≤ni≠2k1+1≤i≤ni=n+k=1=n+(2lgn+1–2) n+2n3n。所以平摊时间是a(i)=T(n)/n3。用计账法分析第1题中n次操作的时间复杂度。解： 第2种操作一次所需要的时间是，当i=2k时，c(i)=i。我们注意到，在两次第2种操作之间，从i=2k-1到i=2k(k2)第1种操作做了(2k-2k-1–1)=(2k-1–1)次。所以，如果我们给第1种操作多赋以2个单位时间并用来支付下一次的第2种操作，那么，第2种操作最多只需2个单位时间。很容易看到，这个观察在k=0和k=1时，没有第1种操作帮助，也正确。所以，为计算方便，我们可定义两种操作的平摊时间如下：第1种操作的平摊时间是3，第2种操作的平摊时间也是3。那么，第2种操作的总时间2第1种操作的次数+2第2种操作的次数2第1种操作的次数+3第2种操作的次数所以，我们有如下分析：第1题中n次操作的总时间=第1种操作的总时间+第2种操作的总时间1第一种操作的次数+（2第1种操作的次数+3第2种操作的次数）=3第一种操作的次数+3第二种操作的次数=每次操作的平摊时间(第一种操作的次数+第二种操作的次数)=3n=O(n)重新考虑例17.2中，有k位的二进制计数器的连续增值问题。假设我们除了給二进制计数器增值（即加1）的操作外，还允许在任意次连续增值后清零的操作，也就是把每个比特置为0的操作。另外，如果某次增值后的数字大于计数器能表达的范围，也要清零。请解释如何在二进制计数器（即一个二进制比特的序列）上实现增值（Increment）和清零（Reset）的操作，使得对初值为0的计数器进行n次增值和清零的操作总共需要O(n)时间。请用计账法分析这n个操作的复杂度。（提示：用一个指针指向最高位的1。）解： 我们用数组A[0..k-1]表示一个有k个比特的计数器。初始时，所有比特为0。另外，我们用一个指针maxA指向值为1的最高比特位。初始时，所有比特为0，置maxA=-1。下面是增值（Increment）和清零（Reset）的操作的伪码。Increment(A)i0whilei<kandA[i]=1 A[i]0 ii+1endwhileifi<k then A[i]1 ifi>maxA //更新最高位的1的位置 thenmaxAi endif else maxA-1 //数字超出了计数器能表达的范围endifEndReset(A) //清零fori0tomaxA A[i]0 //重置比特A[i] maxA-1 //更新指针maxAendforEnd在增值和清零的操作中，计入时间复杂度的基本操作及它们需要的实用时间可假设如下：把比特0翻转为1需要一个单位时间把比特1翻转为0需要一个单位时间重置一个比特需要一个单位时间更新指针maxA需要一个单位时间。我们为以上每种基本操作设置平摊时间如下： 把0翻转为1： 平摊时间=3(单位时间)把1翻转为0： 平摊时间=0重置一个比特： 平摊时间=0更新指针maxA： 平摊时间=1。我们有以下分析：把0翻转为1的基本操作的总次数：因为0翻转为1只在增值操作中出现，且每次增值只需翻转一次，所以有：把0翻转为1的总次数增值操作的次数n。把1翻转为0的基本操作的总次数：和书中例17.4的分析一样，这个总次数把0翻转为1的总次数。重置比特的总次数：重置比特的操作只出现在清零操作中。在一次清零操作中，重置比特的个数是p=maxA+1。因为指针maxA能到达现在的位置，一定是从上一次清零开始，记数器中数经过了p次进位而得，也就是说，至少经过了p次把比特0翻转为1的操作。所以有： 重置比特的总次数把0翻转为1的总次数。更新指针maxA的总次数：因为每次增值操作或清零操作中，指针maxA最多被更新一次，所以有：更新指针maxA的总次数增值操作的次数+清零操作的次数n。由上面的分析，我们得到对记数器进行n次增值和清零操作的时间复杂度是：把0翻转为1的总次数+把1翻转为0的总次数+重置比特的总次数+更新maxA的总次数3把0翻转为1的总次数+更新maxA的总次数=把0翻转为1的平摊时间把0翻转为1的次数+n3n+n=4n=O(n)。在第3章习题13中，我们介绍了最小优先树。对应于数组A[1..n]的一个完全二叉树T称为最小优先树，如果它满足以下条件：T的根存有数组A[1..n]中最小的数。假设根中的数为A[r]，则根的左子树由数组A[1..r-1]中数递归建立，而根的右子树由数组A[r+1..n]中数递归建立。当数组为空时，对应的子树为叶结点而过程停止。显然，在最小优先树中，父亲结点里的数要小于等于儿子结点里的数。給定数组A[1..n]，下面的算法是用逐个插入的方法构造其最小优先树。让我们用T表示这棵树。它有一个属性T.root，指向这棵树的根。树中每个结点x可用子程序，MakeNode(x)，建立。它有4个属性，其中x.key是存于这个结点的数字，x.left，x.right，x.parent是3个指针，分别指向左儿子，右儿子，和父亲结点。属性为空时，记为nil。建最小优先树的算法如下，Min-First(A[1..n],T) //n>1MakeNode(x) //建一结点x，它的4个属性初始都是nilx.keyA[1] //把A[1]存入结点xT.rootx //x是树根，树中只插入一个数A[1]lastx //指针last指向最后插入到树中的结点fori2ton //从A[2]开始，逐个插入这个二叉树T MakeNode(new) new.keyA[i] //new.parent=new.left=new.right=nil whilelast.parentnilandlast.key>new.key lastlast.parent //沿last到根的路径，找小于等于A[i]的数 endwhile iflast.parent=nilandlast.key>new.key //last是根，表示A[i]小于树里所有数字 then new.leftlast //原来的树成了A[i](=new.key)的左儿子 last.parentnew //保持new.parent=new.right=nil T.rootnew //A[i]是新的树根 else new.leftlast.right //否则last的右子树成为A[i]的左子树 last.rightnew //A[i]成为last的右子树 new.parentlast //双向联结 ifnew.leftnil //也就是原先的last.right thennew.left.parentnew //因为要双向联结 endif endif lastnew //有last.right=new.right=nilendforEnd证明算法Min-First的正确性。用平摊分析的计账法证明算法Min-First的复杂度是O(n)。用平摊分析的势能法证明算法Min-First的复杂度是O(n)。解： (a) 证明算法Min-First的正确性。我们归纳证明以下命题：插入第i个数后的二叉数是A[1..i]的一个最小优先树。归纳基础：当i=1时，算法一开始建立一个数A[1]的二叉数。这显然是一个最小优先树。归纳步骤：假设插入A[i-1]后的树T是A[1..i-1]的一个最小优先树(i2)。我们证明，插入A[i]后的树也是一个最小优先树。因为A[i-1]是序列A[1..i-1]最后一个数，last.key=A[i-1]，所以，树T中对应A[i-1]的结点的右子树一定是空(nil)，而且它是树中最右边的一个叶子。如果我们顺着从A[i-1]到根这条路径走的话，数字会一个比一个小。当我们碰到一个结点的数a满足aA[i]时停下。假定结点a的右儿子是数字b，那么我们有aA[i]<b。这说明，未插入A[i]前，a严格小于序列A[1..i-1]中它右边的任何数，而b是a右边数中最小的。因为现在有aA[i]<b，那么，A[i]就是序列A[1..i]中点a右边最小的数。所以，A[i]可成为a的右儿子。因为A[i]是序列A[1..i]中最后的数，所以，序列A[1..i-1]中点a右边的所有数形成A[i]的左子树。显然，这棵左子树正好是未插入A[i]前，以b为根的子树，也就是a的右子树。因为A[i]是序列A[1..i]中最后的数，它的右子树必定是空(nil)。容易看出，如果b=nil，那么必有a=A[i-1]，算法仍然正确。所以，按以下步骤插入A[i]后的二叉树仍然是最小优先树。顺着从A[i-1](也就是结点last)到根的路径找到第一个结点A[k]满足A[k]A[i]。如果A[k]=nil和A[k]>A[i]，那么A[i]是所有数中最小的，它成为树根。A[1..i-1]形成的最小优先树成为A[i]的左儿子。跳过步骤(3)(4)(5)。不论A[k]nil或者A[k]=nil，有A[k]A[i]。那么，A[i]是A[k]右边最小的数，切下A[k]的右儿子R。置A[k]的右儿子为A[i]，并置A[i]的父亲为A[k]。置A[i]的左儿子为R。如Rnil，置R的父亲为A[i]。置A[i]的右儿子为一片树叶。题中算法正是实现上面的步骤。所以归纳成功，算法正确。 (b)用平摊分析的计账法证明算法Min-First的复杂度是O(n)。现在来分析一下复杂度。算法Min-First每次插入一个数A[i]时做以下3件事。为这个数建一个结点，这只需常数时间，可认为是一个单位时间。沿着A[i-1](=last)到根的路径走，直到发现一个结点的数a满足aA[i]时停下或发现A[i]比根还小时停下。这一步由第7行的while循环完成。把结点a的右子树切下，取而代之，结点A[i]成为结点a的右子树。这棵切下的子树成为结点A[i]的左子树，而A[i]的右子树是一片树叶。如果A[i]比根还小，那么结点A[i]成为树根，而原树根成为结点A[i]的左儿子。不论哪种情况，这第3件事只需常数时间，也可认为是一个单位时间。上面第2件事所需时间与比较的次数成正比。我们注意到，除了最后比较的结点a外，其它任何与A[i]比较过的数字将不会再有比较。这是因为这些比较过的结点，除结点a外，属於被切去的结点a的右子树，而一旦被切去，这棵子树中所有的点就不再有可能与以后插入的任何数比较了。因此，如果把一次比较的时间也算为一个单位时间，那么这第2件事所需时间等于1(A[i]与点a的比较)加上比较后被切去的结点数。因为每个结点最多只能被切去一次，所以导致结点被切去的比较次数总共不会大于n。当然，这第2件事的最后一次比较，即与点a的比较，不导致结点a被切去。但是这样的比较次数总共不会大于n。所以，这n次插入中第2件事所需要的总时间不大于n+n=2n。由以上分析，我们可各附加一个单位时间给第一件和第三件事，即它们的平摊时间都是2。因为n次插入产生2n个附加的单位时间，足够支付第二件事所需时间，我们可把第二件事所需平摊时间定为0。所以，n次插入的总时间最多是：平摊时间(第一件事次数+第二件事次数)=22n=4n=O(n)。因此，算法Min-First的复杂度是O(n)。(c) 用平摊分析的势能法证明算法Min-First的复杂度是O(n)。由问题(b)知，算法Min-First每次插入一个数时做3件事。一是为这个数建一个结点，需1个单位时间。二是沿着A[i-1]到根的路径走，直到发现a满足aA[i]或A[i]比根还小。第三件事是把结点a的右子树切下，结点A[i]成为结点a的右子树，这棵切下的子树成为结点A[i]的左子树，而A[i]的右子树是一片树叶。这第三件事也可认为需要1个单位时间。这第二件事所需时间与比较的次数成正比。我们注意到，这第二件事所需时间等于1(与点a的比较)加上比较后被切去的结点数。因为每个结点最多只能被切去一次，所以导致结点被切去的比较次数不会大于n。 根据以上分析，我们定义一棵最小优先树的势能函数：=从根到最右边叶结点的路径上的内结点的个数–1。(也就是关键字的个数–1)。显然，一开始，算法建立只含一个关键字的二叉树，我们有(0)=1–1=0。又因为每次插入一个数后，这条路径上至少有一个内结点，所以(i)0。这个势能函数的定义正确。我们注意到，插入第i个数A[i]需要的实际时间是2+k,其中k是第二件事所需比较的次数。势能的增量最多是–k+2，这是因为至少有k-1个数字要从这个路径上被切走，但是A[i]会加入到这个路径上。所以，插入第i个数的平摊时间最多是2+k–k+2=4。因此，算法Min-First的复杂度是O(4n)=O(n)。在17.2.2一节，我们用如下一个例子证明用装填因子0.5作为收缩的标准不行。假设当前表格T的容量是size(T)=2k和number(T)=2k-1。如果下面两个操作是插入，那么，在插入第一个数后，我们需要把表格扩张后插入第2个数，总共用时2k+2个单位时间。如果接下来两个操作是删除，那么，因为删除两个数据后的表格有number(T)=2k-1，导致小于0.5的装填因子，我们需要在删除第一个数后把表格收缩，总共用时也是2k+2个单位时间。这时，表格恢复到这4次操作前的状态。可以想像，如果我们接下去有一系列的插入2个和删除2个的操作，那么平均一次操作的时间是2k-1+1。因为k不是常数，所以，用0.5的装填因子作为表格收缩的标准不可能保证平均一次操作的时间是常数。以上的证明不是很严格，因为上面的反例不是从空表开始。另外，如果我们固定一个正整数k，然后給出一系列插入2个和删除2个的操作，那么对一个给定的k，2k-1+1是常数。请严格证明，如果用装填因子0.5作为收缩的标准，那么存在一个例子使得平均一次操作的时间可以任意大。解： 如果用装填因子0.5作为收缩的标准，我们考虑下面的一系列对表格的插入和删除操作。设开始时，k=1，size(T)=2=2k，number(T)=1=2k-1。取一正整数h>0。重复2k次插入2个数和删除2个数的操作。这需要(2k+1+4)2k个单位时间。size(T)和number(T)不变。插入2k个数使size(T)=2k+1，number(T)=2k+1-1。这需要(2k+2k)=2k+1个单位时间(包括一次扩展)。以上两步，我们一共进行了52k个插入和删除操作，至少需要2k+12k>4k个单位时间。现在，k变成k+1了。不断重复上面(1)(2)两步直到k=h+1。这样，我们一共进行了k=1h5×2k52h+1=102h个插入和删除操作。因为至少需要总共k=1h4k4h个单位时间，所以平均一次操作的时间>4h/(10因为整数h可以取的任意大，所以存在一个例子使得平均一次操作的时间可以任意大。证明，对任一給定正整数n，都可以通过一系列的斐波那契堆的操作得到只含一棵树的斐波那契堆。并且，这棵树上有n个结点，它们形成一条链，即除最后一个结点外，每个结点只有一个儿子，最后一个结点的儿子是nil。解： 給定正整数n，我们把这样一颗树称为一个链条(chain)。我们先为n=1和n=2设计一个子程序如下。1-chain(H,x) //含一个点x的链条Make-Fib-Heap(H)createanobjectu //为x建一个结点的对象uu.keyxFib-Heap-Insert(H,u)End2-chain(H,a,b) //建含两个点a和b，0<a<b，的链条1-chain(H,a)createanobjectv //为b建一个结点vv.keybFib-Heap-Insert(H,v)createanobjectw //为数字0建一个结点ww.key0Fib-Heap-Insert(H,w)Fib-Heap-Extract-Min(H)End1-chain的正确性显然。2-chain的正确性也显然。在建立一个点a的斐波那契堆后，我们插入b和0。这时，树根环有3棵树，分别含有关键字0，a，b。因为0<a<b，当我们删除最小点时，含0的树被删去，而点a和点b则合并为一棵以a为根的树。它有唯一的儿子b。这棵树就是一个2-chain。当n>2时，我们为Chain设计以下递归算法。Chain(H,A[p..r],n) //设0<A[p]<A[p+1]<…<A[r],r-p+1=nifn=1 then 1-chain(H,A[p]) returnendififn=2 then 2-chain(H,A[p],A[p+1]) return else Chain(H1,A[p+1...r],n-1) //递归调用 yA[r]+1 2-chain(H2,A[p],y) //A[p]最小，y最大 Fib-Heap-Union(H,H1,H2) createanobjectw w.key0 Fib-Heap-Insert(H,w) Fib-Heap-Extract-Min(H) Fib-Heap-Delete(H,y)End上面伪码的正确性可以归纳证明。当n=1和2时，伪码显然正确。假设当n=1,2,…,k时，伪码可以正确地建立只含一棵树的斐波那契堆。并且，堆中k个结点形成一条链。我们证明，当n=k+1时，伪码仍正确。由伪码第8行知，当n=k+1时，伪码先递归地建立只含一棵树的斐波那契堆H1，堆中k个结点形成一条链，树根是A[p+1]。然后，算法产生只含两个数，A[p]和y=A[r]+1的的斐波那契堆H2。当我们合并H1和H2为H后，堆H有两个树根，A[p]和A[p+1]。插入点w=0后有3个树根。所以，伪码第14行删除最小点后，子程序Consolidate(H)会把根A[p+1]联到A[p]上，从而得到一棵树的斐波那契堆H。显然，把点y从点A[p]上切除后，这棵树是一个从A[p]到A[r]的一条链。归纳成功。假设有一个斐波那契堆如下图所示，请比照图17-4，显示删除最小点的步骤和最后的斐波那契堆。1111H.min1735242810271320314219201422解： 删除最小点的第一步是把最小点10的所有儿子并入树根表，第二步把最小点10从树根表中摘除。同时，指向最小点的指针指向最小点10右边的点19。第三步做Cons