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

PAGE15第3章 基于比较的排序给出一例证明在最坏情况下，合并算法至少需要n1+n2-1次比较。解：作为一个例子，如果数组A[1..n1]和数组B[1..n2]中数满足以下条件，那么合并算法需要n1+n2-1次比较:A[1]<A[2]<A[3]<…<A[n1-1]<B[1]<B[2]<B[3]<…<B[n2]<A[n1]。(a) 设计一个复杂度为O(nlgn)的算法以确定数组A[1..n]中的n个数是否有相同的数字。 (b) 设计一个复杂度为O(nlgn)的算法把数组A[1..n]中出现奇数次的数字挑选出来。解：这两个问题可以用排序来解决。我们假定n2。(a)Repeated-Number(A[1..n])Heap-sort(A[1..n]) //用堆排序对A[1..n]进行排序fori2ton ifA[i]=A[i-1] thenreturn“Yes,A[i]andA[i-1]areidentical.” //报告A[i]和A[i-1]相同 endifendforreturn“Norepeatednumbers.” //没有重复的数字End因为该算法的大部分时间化在第一步的排序，所以算法复杂度为O(nlgn)。(b)Odd-occurrence(A[1..n])Heap-sort(A[1..n]) //用堆排序对A[1..n]进行排序sA[1] //A[1]是第一个要检查的数j0 //出现奇数次的数将被按序放入B[1..j]oddtruefori:=2ton ifs=A[i] then ifodd=true thenoddfalse elseoddtrue endif else ifodd=false //A[i]有一个不同的值 then oddtrue sA[i] else jj+1 //odd=true，记录到B中 B[j]s sA[i] //odd仍然为true，未变 endif endifendforifodd=true //最后一轮中，s=A[n]，此时处理 then jj+1 B[j]s endifreturnB[1..j]End 因为该算法的大部分时间化在第一步的排序，其复杂度为O(nlgn)，而后面步骤所需时间为O(n)，所以算法复杂度为O(nlgn)。(a) 一棵高为h

的堆最少和最多能含有多少个结点(包括所有内结点和叶结点)？ (b) 证明一个含有n个数的堆的高为ëlgnû。解

: (a) 当一棵高为h

的堆是一棵满二叉树时含有最多的结点。此时的结点数是：Nmax(h)=1+2+22+23...+2h=2h+1–1。 当一棵高为h

的堆的底层只含有一个叶结点时，它含有的结点数最少。此时的结点数是：Nmin(h)=Nmax(h-1)+1=2h。(b) 设一个含有n个数的堆的高为h。从上题(a)可知：Nmin(h)£n£Nmax(h)，即2h£n£2h+1–1，也就是2h£n<2h+1。由此可得h£lgn<h+1。所以有h=ëlgnû。假设Heap-Delete(A[1..n],i)表示将A[i]这个数从数组A[1..n]构成的堆中删去，并使所余n-1个数形成一个堆的操作。用伪码设计一个复杂度为O(lgn)的算法来实现Heap-Delete(A[1..n],i)(1in)。解：Heap-Delete(A[1..n],i) //1inkey←A[i]A[i]«A[n]n←n–1ifin //如果i=n+1，则已被刪去 then ifkey>A[i] then Max-Heapify(A[1..n],i) else key←A[i] Heap-Increase-Key(A[1..n],i,key) endifendifEnd假设Heap-Decrease-Key(A[1..n],i,key)表示在数组A[1..n]构成的堆中把A[i]的值减少为key，并把A[1..n]修复为一个堆的操作。用伪码设计一个复杂度为O(lgn)的算法来实现Heap-Decrease-Key(A[1..n],i，key)(1in)。解：Heap-Decrease-Key(A[1..n],i,key) //1inifkey>A[i] thenreturn“error,newkeyislargerthancurrentkey” //错误，新值大于现有值endifA[i]¬keyMax-Heapify(A[1..n],i)End给定一个排好序的数组A[1]≤A[2]≤…≤A[n]，第2章里例2.1中的二元搜索算法可以用一棵二元搜索树来描述。树中每个内结点含有一个数组中的数。树根里的数是算法进行比较的第一个数，即A[mid]。如果x=A[mid]，则搜索成功并报告。否则，根据结果是x<A[mid]还是x>A[mid]，算法决定是递归搜索左半部分，还是递归搜索右半部分。因而这棵二元搜索树的左右两子树可相应地递归构造。下图给出了当n=1，2，3，4时二元搜索树的例子。其中叶结点表示搜索失败的情况。证明一棵二元搜索树T的叶结点只出现在最底下二层。证明一棵含n个数的二元搜索树的高度为h=élg(n+1)ù。解: (a)证明一棵二元搜索树T的叶结点只出现在最底二层。我们对n进行数学归纳。归纳基础：当n£4，上面图例直接证明了这个结论。归纳步骤： 假设当n=1，2，…，k-1(k>4)时，一棵含n个内结点的二元搜索树T的叶结点只出现在最底二层。下面我们证明当n=k时结论仍正确。我们分两种情况证明。n是奇数。在这种情况下，左右两子树L和R都含有(n-1)/2个内结点因而形状完全相同。由归纳假设，它们的叶结点只出现在最底二层。这些叶结点也就是T的叶结点。所以结论正确。n是偶数。在这种情况下，左子树含(n-2)/2=n/2-1个数字而右子树含n/2个数字。因为左右子树都是完全二叉树，所以左子树总共含有(n-1)个结点而右子树含(n+1)个结点(包括叶结点)。右子树正好比左子树多二个结点。如果左右两子树L和R的高度相等，那么结论得证。故假定他们高度不等。如下图所示，右子树比左子树必定高一层。因为右子树的底层至少含二个叶子，左子树必须是一个满二叉树，否则它会比右子树少至少3个结点，不可能。所以左子树的所有叶子必须在最底层。这就是说，左右子树的所有叶子都在最底二层。归纳成功。LLRh1h2h1-1证明一棵含n个数的二元搜索树的高度为h=élog(n+1)ù。证明： 因为一棵含n个数的二元搜索树有(n+1)个叶子，它总共有2n+1个结点。假设它的高度为h。由(a)部分的解知，它的所有叶子在最底二层。因为底层至少有两个叶子，但不会多于2h个叶子，所以有(1+2+…+2h-1)+2£2n+1£1+2+…+2h-1+2h，即2h+1£2n+1£2h+1–1，即(2h+2)£2n+2£2h+1。由此得 2h-1+1£(n+1)£2h，2h-1<(n+1)£2hh-1<log(n+1)£hh-1<élog(n+1)ù£h。所以有h=élog(n+1)ù。*一个结点在一棵树中的高度就是以这个结点为根的子树的高度。证明在一个有n个数字的堆中，高度为h的结点数最多为én2h+1ù证明: 设x是一个有n个数字的堆中高度为h的结点数。我们注意到两棵高为h的子树的结点不相交，即一棵高为h的子树中结点不属于任一个其他的高为h的子树。另外，因为所有叶结点都在最底两层，所有高为h的子树，最多除一个外，都必定是满二叉树。下面的图清楚地解释了这一点。唯一可能不是满二叉树的子树唯一可能不是满二叉树的子树一棵高为h的满二叉树一共有2h+1-1个结点。而一棵不是满二叉树的高为h的子树，也至少有2h个结点。现在，试想把这x个子树中除了根以外的结点从T中刪除，剩下的部分是一个有x个叶子的完全二叉树。这个树中除叶子外的内结点数正好是(x-1)个。他们正好是T中除高为h的子树以外的结点集合。所以我们可得以下不等式：n≥(x-1)+(x-1)(2h+1-1)+2h=(x-1)(2h+1)+2h=x(2h+1)-2h+1+2h≥x(2h+1)-2h因此有x≤(n+2h)/(2h+1)=(n/2h+1)+1/2≤én2h+1ù+因为x必须是整数，故有x≤én2h+1(K路合并问题) 利用最小堆(min-heap)设计一个时间复杂度为O(nlgk)的算法将k个排好序的序列合并为单一排好序的序列。这里n是所有k个序列中数字的总数。解: 假定A1，A2，...，Ak为k个要合并的序列。假设每个序列已从小到大排好，算法思路如下：首先，把每个序列的头，A1[1],A2[1],...,Ak[1]，即各序列中最小的数取出并组织为一个最小堆。那么，堆中的根显然是所有n个数中最小的数。 然后，每次将堆的根中的数取出并放到输出序列中。根中的数必定是还未输出的所有数中最小的数。如果根中的数来自序列Aj(1£j£k)，那么将根中的数输出之后，我们把Aj中下一个最小的数，即当前Aj的头从序列Aj取走放到堆的根结点并将堆修复。如果序列Aj中没有数字了，那么我们把堆的规模减一并修复。这时参加合并的序列少了一个。因为堆由各序列中最小的数组成，在根中的数显然是当前还未输出的所有数中最小的数，算法显然正确。下面是这个算法的伪码。我们假定初始时，每个序列至少有一个数字并用一个特殊记号¥表示序列结束。k-Merge(A1,A2,...,Ak)Buildamin-heapH[1..k]fromA1[1],A2[1],...,Ak[1] //由k个序列头建堆fori¬1tok ifH[i]=Aj[1] thenQ[i]¬j //记住堆中第i个数是从第j个序列来的。 endifendforforj¬1tok head[j]¬2 //head[j]是序列Aj中当前剩余部分的首项，即最小数的位置。endfor i¬0 //用于输出序号heap-size¬kwhileheap-size¹0 i¬i+1 C[i]¬H[1] //C是输出序列。 j¬Q[1] p¬head[j] ifAj[p]¹¥ then H[1]¬Aj[p] head[j]¬p+1 else H[1]¬H[heap-size] Q[1]¬Q[heap-size] Heap-size¬heap-size-1 endif ifheap-size>0 thenHeapify(H[1..heap-size],1) //注意，移动H[k]时，Q[k]要相应更新。 endifendwhileEnd因为每输出一个数之后我们需要修复含有不超过k个元素的堆，其时间为O(lgk)，所以总的时间复杂度为O(nlgk)。大家熟知，数组A[1..n]形成的堆里，第i个数A[i](1≤i≤n)的左儿子、右儿子、及父亲的所在位置可以由下面公式算出：Left(A[i])=A[2i]Right(A[i])=A[2i+1]Parent(A[i])=A[ëi/2û]但是我们很多时侯不能把这个堆存放在从A[1]开始的数组中，而是存放在从A[p]开始的n个单元中，即存放在A[p..r]中，这里r=p+n–1。这相当于把这n个数在数组中向右平移了(p-1)个位置。请给出在这种情况下，确定数字A[i](p≤i≤r)的左儿子、右儿子、及父亲的所在位置的公式。解: 我们把A[p..r]一一对应地映射到另一个数组B[1..n]中，A[i]=B[i-p+1]，p≤i≤r，而B[j]=A[j+p-1]，1≤j≤n。因此新的公式是：Left(A[i])=Left(B[i-p+1])=B[2(i-p+1)]=B[2i-2p+2]=A[2i–p+1]，Right(A[i])=Right(B[i-p+1])]=B[2(i-p+1)+1]=B[2i–2p+3]=A[2i–p+2]，Parent(A[i])=Parent(B[i-p+1])=B[ë(i-p+1)/2û]=A[ë(i-p+1)/2+p-1]=A[ë(i+p-1)/2û]。证明一个有n个数字的堆的左子树最多含有2n/3个结点。证明: 如下图所示，我们用L代表左子树中的结点数，用R代表右子树中的结点数。在左子树中，我们用B代表在底层的叶子结点数，而用U代表底层上面的结点数，L=U+B。显然，我们有关系B≤U+1和U≤R。因而得到L=U+B≤2U+1≤2R+1。因为L+R+1=n，所以R=n–L-1。从而有L≤2R+1≤2(n–L-1)+1=2n-2L-1<2n-2L，也就是L<2n/3，即L2n/3。假设给定一个n个数的数组A[1..n]和一个常数x。我们希望确定数组中是否存在两个数，A[i]和A[j](1i<jn)，使得A[i]+A[j]=x。设计一个复杂度为O(nlgn)的算法解决这个问题。如果这样两个数存在，则报告这两个数，否则报告不存在。解: 主要思路如下。我们先将数组A[1..n]从左到右排序为A[1]≤A[2]≤A[3]≤…≤A[n]。然后把最小的数和最大的数相加(开始是A[1]和A[n]相加)。如果其和等于x，则问题解决。如果其和小于x，则最小的数不可能在解之中而丢弃。如其和大于x，则最大的数不可能在解之中而丢弃。每次我们从左丢弃一个最小数或从右丢弃一个最大数直至找到答案。Search-SUM(A[1..n]，x)Heap-sort(A[1..n])使得A[1]≤A[2]≤A[3]≤…≤A[n]exist¬falsei¬1j¬nwhilei<jandexist=false ifA[i]+A[j]=x then return(true,i,j) else ifA[i]+A[j]<x theni¬i+1 elsej¬j-1 endif endifendwhilereturn(nosolution)End因为排序需要O(nlgn)时间而以后的搜索只需要O(n)时间，上面算法的复杂度是O(nlgn)。锦标赛排序法是一个基于比较的排序算法。它可以用一个称之为锦标赛树(tournamenttree)的完全二叉树来描述。这个二叉树要求正好有n个叶子来存储n个要排序的数字，并且所有叶子在底层或倒数第2层。下面是一个有5个叶子的一个锦标赛树图例。9924710算法开始前，被排序的n个数字被放在这n个叶子中。每个内结点代表一次比较。每次比较中胜者，即较小的数，参加下一轮在其父结点处的比较。在每个内结点处，当它的两个子结点处的比较有了结果之后，该结点处的比较即可进行。最后，在根结点处的比较决出冠军，即最小的数。因为一共有(n-1)个内结点，所以只需(n-1)次比较便可以找到最小数。当最小的数被确定后，即可把它送到输出序列中。另外，把它原来所在的叶子中的值改为。显然，重复上面的过程可得到下一个最小的数。如果重复所有在内结点处的比较去找下一个最小的数，我们又需要(n-1)次比较。这个复杂度太高。请设计一个只需O(lgn)次比较的算法去找下一个最小的数。(只须解释步骤，不要求伪码。)请用伪码设计一个用数组来实现锦标赛排序的算法，使其复杂度为O(nlgn)。解：在找下一个最小数时，如果我们重复所有在内结点的比较的话，那么，在大部分结点处所比较的两个数仍然是在找前一个最小数时进行过比较的两个数，这部分比较不需再做。那么，在哪些结点处所比较的两个数会有变化呢？容易看出，可能有变化的结点必定是在从前一个最小数所在的叶子到根的这条路径上。所以我们的算法是，在每个结点处记录每次比较后谁是胜者、谁是败者。然后在找下一个最小数时，沿着前一个最小数所在的叶子到根的这条路径，在每个结点处作一次比较。最后，在根结点处比较的胜者为下一个最小数。因为有n个叶子的这个二叉树的高度是lgn，所以这条路最长为lgn。因此，找下一个最小的数最多只需lgn-1=O(lgn)次比较。假设要排序的n个数放在数组A[1..n]中。我们用数组W[1..2n-1]来代表锦标赛树的结点，做法和堆完全一样。一开始，这n个被排数放在从W[n]到W[2n-1]之中而W[1..n-1]为空。然后从W[n-1]开始到W[1]为止，在每一个内结点处做比较以求得最小数。我们用数组W[1..n-1]记录各次比较的胜者。排好序的n个数输出在数组C[1..n]中。在结点W[i]，1in-1，比较的两个数分别从它两个子结点的胜者，即W[2i]和W[2i+1]，中取得。在求得最小数之后，把它所在叶结点的值改为。然后，按照(a)中叙述办法求得第2小数，第3小数，直至排序完成。为了能找到最小数所在叶结点位置，每次比较时记录的是胜者在原序列A中的序号而不是数值本身。下面是实现这一算法的伪码。因为找到最小数需要O(n)时间，而以后每找下一个最小数只需要O(lgn)时间，整个排序需要O(nlgn)时间。Tournament-sort(A[1..n],W[1..2n-1],C[1..n]) fori¬1ton W[i+n-1]¬i //数组A的序号依次放入W[n]到W[2n-1]之中endforforj¬(n-1)downto1 left¬W[2j] //W[j]的左儿子 right¬W[2j+1] //W[j]右左儿子 ifA[left]A[right] thenW[j]¬left elseW[j]¬right endifendforwinner¬W[1]C[1]¬A[winner] //找到了最小数并输出，winner是在原数组A中序号A[winner]¬fori¬2ton //顺序找出下一个最小数 j¬winner+n-1 //最小数在数组W中位置 p¬j/2 //最小数的父亲 whilep0 left¬W[2p] right¬W[2p+1] ifA[left]A[right] thenW[p]¬left elseW[p]¬right endif p¬p/2 //p的父亲 endwhile winner¬W[1] C[i]¬A[winner] //找到笫i个最小数并输出 A[winner]¬endforEnd给定一个数组A[1..n]，我们希望建一个有n个内结点的完全二叉树T。它满足以下条件：T的根中存有数组A[1..n]中最小的数。假设根中的数为A[r]，那么根的左子树由数组A[1..r-1]中数递归建立，而根的右子树由数组A[r+1..n]中数递归建立。当数组为空时，对应的子树为叶结点而过程停止。让我们称这样的二叉树为最小优先树。下面图示给出一个例子。画出对应于下面序列的最小优先树：6，5，2，9，7，1，3，10，9。解:设计一个构造最小优先树的算法，其平均复杂度为O(nlgn)。我们假设最小数出现在序列中任何位置的概率相同。(注：可以有O(n)算法)解：调用下面分治算法可为数组A[1..n]构造最小优先树。min-first(A[p,r],T)ifp>r then returnaleaf else findqsuchthatA[q]=min{A[p],A[p+1],…,A[r]} min-first(A[p,q-1],T1) min-first(A[q+1,r],T2) constructT(root=A[q],lefttree=T1,righttree=T2) returnTendifEnd数组A[1..n]的最小优先树可以通过调用min-first(A[1,n],T)得到。这个算法与快排序递归过程完全一样。不同的只是，快排序是找到中间点后划分序列为两段，而最小优先树是找到最小数后将原序列分为两段。因为两算法的划分步骤都需要(n-1)次比较，所以上面算法与快排序的复杂度相同。他们的平均复杂度均为Q(nlgn)。如图所示，平面上有上、下两条平行线。每条线上各自分布有n个点，并从左到右顺序标为1，2，…，n。我们把上面的n个点与下面的n个点配成一一对应的n个对子后，用一个直线段把每对点连上。若上面的点i与下面的点k相连，则记为k=π(i)(1≤i,k≤n)。如果i<j但π(i)>π(j)，那么线段(i,π(i))和线段(j,π(j))会有交叉点。例如，在下图中一共有10个交点。请设计一个O(nlgn)的算法，对一个给定的n对连结线段(i,π(i))(1≤i≤n)，计算出一共有多少个交叉点。解：我们用类似合并排序的方法对序列π(i)(1≤i≤n)一边排序，一边计数。我们把序列π(p..r)平分为π(p..q)和π(q+1..r)后，分别统计各子序列中的交叉点数并将序列排序。然后，在把二序列合并为一个序列时，如果左序列中首项L[i]比右序列的首项R[j]小，那么L[i]对应的线段(i,π(i))与右序列中任一个线段不会有交点，L[i]从左序列中输出后，i加1。否则，R[j]与当前左序列中所有线段都有交点，在R[j]从右序列中输出后，j加1，同时加上交点个数。 Merge-and-Count(,p,q,r,c) //合并π[p..q]和π[q+1..r]的子程序，c是交点个数n1q-p+1 //左序列中数字个数n2r-q //右序列中数字个数fori1ton1 L[i][p+i-1] //Copy左序列π[p..q]到L[1..n1]endforforj1ton2 R[j][q+j] //Copy右序列π[q+1..r]到R[1..n2]endforc0 //交叉点数初值ij1kp //顺序属出[p..r]whilein1andjn2 ifL[i]<R[j] then [k]L[i] ii+1 else [k]R[j] cc+(n1–i+1) jj+1 endif kk+1endwhileifi>n1 then whilejn2 [k]R[j] jj+1 kk+1 endwhile else whilein1 [k]L[i] ii+1 kk+1 endwhileendifReturn(c) 分治算法的主程序如下：Mergesort-and-Count(,p,r,c)ifp=r thenreturn(c=0) else q(p+r)/2 Mergesort-and-Count(,p,q,cl) Mergesort-and-Count(,q+1,r,cr) Merge-and-Count(,p,q,r,cm) ccl+cr+cmendifreturn(c)End当我们置p=1，r=n时，Mergesort-and-Count(,1,n,c)输出这n个线段的交点数c。每个内结点都有两个儿子的二叉树称为完全二叉树。设L为一个完全二叉树T的叶子的集合。用数学归纳法证明以下等式:x∈L12depthx=(depth(x)表示x的深度，即从根到点x的路径长度。) 证明：我们对树的高度进行数学归纳。 归纳基础：当h=0时，树T中只有一个结点，通常视为叶子。因为它的深度为0，显然有120当h=1时，树T中只有一个根结点和两个深度为1的叶子。因为121+归纳步骤：假设当h=0,1,…,k时，要证的等式成立。现在证明当h=k+1时等式也成立。因为T是完全二叉树，它的两个子树也是完全二叉树，但高度小于或等于k。我们用L-left表示左子树中的叶子集合，用L-right表示右子树中的叶子集合，L=L-leftL-right。因为depth(x)–1是x在左子树（或右子树）中的深度，由归纳假设，我们有：x∈L-left12x∈L-right1因此，我们有：x∈L12depthx=12x∈L-left12=12+12归纳成功。设T为一个高度为h的完全二叉树，而它的所有结点的集合是V。用数学归纳法证明以下不等式: xV12证明： 我们对树的高度h进行数学归纳。归纳基础:当h=0时，树T中只有一个结点，通常视为叶子。因为它的深度为0，显然有120=1=当h=1时，树T中只有一个根结点和两个深度为1的叶子。因为120+121+12归纳步骤:假设当h=0,1,…,k，(k1),时要证的等式成立。现在证明当h=k+1时等式也成立。因为T是完全二叉树，它的两个子树也是完全二叉树，但高度小于或等于k。我们用h-left和h-right分别表示左子树和右子树的高度，则有h-leftk，h-rightk。我们用L表示左子树中所有结点的集合，用R表示右子树中的所有结点的集合，V={root}LR。因为depth(x)–1是x在左子树（或右子树）中的深度，由归纳假设，我们有：xL12depthx-1h-left+xR12depthx-1h-right因此，我们有：xV12depth(x)=1+12xL12depthx-1+12xR12depthx-1

=(k+1)+1=h+1。归纳成功。 重新考虑第8题的k-路合并问题。假设A1,A2,...Ak是k个排好序的序列。序列Ai有ni个数(1≤i≤k)并且有n1+n2+…+nk=n。下面的分治算法k-merge(A,i,j,B,m)把Ai到Aj(1≤i≤j≤k)的序列合并为单一的排好序的序列B。这里，m=h=ijnh是序列B中数字的个数。调用k-merge(A,1,k,B,n)則可把A1,A2,...Ak合并为单一的排好序的序列B。假设合并一个有p个数的序列和一个有q个数的序列需要（p+q-1）次比较，请为算法k-merge(A,i,j,B,m)的复杂度建立一个递推关系并证明k-merge(A,1,k,B,n)的复杂度是O(nlgk-merge(A,i,j,B,m) //TheoutputisinB[1..m]，1≤i≤j≤k ifi=j then mni B[1..m]Ai[1..ni] else mid(i+j)/2 k-merge(A,i,mid,B1,m1) k-merge(A,mid+1,j,B2,m2) mm1+m2 Merge(B1[1..m1],B2[1..m2],B[1..m]) //合并B1和B1为序列B endifEnd解： 我们用T(i,j)表示把Ai到Aj合并所需的时间。我们可得以下递推关系：T(i,j)=T(i,mid)+T(mid+1,j)+O(m)，如果i<j，这里，m=h=ijnT(i,i)=O(ni)。从以上递推关系，可见存在常数c使得 T(i,j)<T(i,mid)+T(mid+1,j)+cmT(i,i)<cni。 现在证明，T(i,j)≤cm(lgh+1)，这里，h=j-i+1是所合并的序列的个数。我们对h进行数学归纳。归纳基础：当h=1，已知T(i,i)<cni=cm，故命题成立。归纳步骤：当h=j–i+1>1时，记h1=mid–i+1=h/2，和h2=j–mid=h/2。由归纳假设，我们有：T(i,mid)cm1(lgh1+1)，这里，m1=h=imidT(mid+1,j)cm2(lgh2+1)，这里，m2=h=mid+1j再由递推关系，可得：T(i,j)<T(i,mid)+T(mid+1,j)+cm //m1+m2=m≤cm1(lgh1+1)+cm2(lgh2+1)+cm我们分两种情形。 h是偶数。我们有h1=h2=h/2。T(i,j)<cm1(lgh1+1)+cm2(lgh2+1)+cm=cm1(lg(h/2)+1)+cm2(lg(h/2)+1)+cm=cm1(lgh-1+1)+cm2(lgh-1+1)+cm=cm1lgh+cm2lgh+cm=cmlgh+cm=cm(lgh+1)。h是奇数。我们有h1=(h+1)/2和h2=(h-1)/2。由递推关系，可推导如下：T(i,j)<T(i,mid)+T(mid+1,j)+cm <cm1(lgh1+1)+cm2(lgh2+1)+cm=cm1(lg(h+1)-1+1)+cm2(lg(h-1)-1+1)+cm=cm1lg(h+1)+cm2lg(h-1)+cm=cm1lgh+cm2lg(h–1)+cm //因为h是奇数时，lg(h+1)=lgh。cm1lgh+cm2lgh+cm =cm(lgh+1)。归纳成功。当h=k,m=n时，k-merge(A,1,k,B,n)有复杂度O(nlgk)。假设数组A[1..n]是一个堆。请设计一个O(lgn)的算法，对任一个元素A[i]，它可以找出并打印出在对应的二叉树中，从根A[1]到A[i]的这条路径。用left和right表示每一步的走向。例如，在下面的堆里，A[10]的路经是root,left,right,left。15157238138106512345678910解： 我们给出一个用分治法的算法如下：Print-Path(A[1..n],i) //OutputthepathfromroottoA[i]ifi=1 then print“root” else fatheri/2 Print-Path(A[1..n],father) ifi=2father then print“，left” else print“，right” endifendifEnd 显然算法是正确的。因为路径长是O(lgn)，所以复杂度是O(lgn)。证明，在最坏情况时，3.3.3节中建堆的算法Build-Max-Heap(A[1..n],1)需要至少2n-2lg(n+1)次比较。解： 我们只需证明，在一个特例中，Build-Max-Heap(A[1..n],1)需要至少2n-2lg(n+1)次比较。我们置n=2h+1-1，那么A[1..n