计算机算法基础第2版沈孝钧习题答案1-7章

第1章 概述假设f(n)和g(n)为两个定义域为自然数的正函数。证明f(n)+g(n)=(max(f(n),g(n)))。证明：因为对任一n≥0，max(f(n),g(n))≤f(n)+g(n)≤2max(f(n),g(n))，所以有f(n)+g(n)=O(max(f(n),g(n)))和f(n)+g(n)=(max(f(n),g(n)))，也就是f(n)+g(n)=(max(f(n),g(n)))。假设f(n)=(p(n))，g(n)=(q(n))，并且都是正函数。证明以下结论。f(n)+g(n)=(p(n)+q(n))f(n)g(n)=(p(n)q(n))f(n)/g(n)=(p(n)/q(n))证明：因为f(n)=(p(n))，g(n)=(q(n))，所以存在常数a0,b0,c0,d0和n0使得当n≥n0时有ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)。从以上关系可知，当n≥n0时，ap(n)+cq(n)≤f(n)+g(n)≤bp(n)+dq(n)。让u=min(a,c),v=max(b,d)，上式可写为u(p(n)+q(n))≤f(n)+g(n)≤v(p(n)+q(n))所以有f(n)+g(n)=(p(n)+q(n))。由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)，我们可得，当n≥n0时，ap(n)cq(n)≤f(n)g(n)≤bp(n)dq(n)。让u=ac,v=bd，上式可写为u(p(n)q(n))≤f(n)g(n)≤v(p(n)q(n))。所以有f(n)g(n)=(p(n)q(n))由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n),我们可得，当n≥n0时，ap(n)/dq(n)≤f(n)/g(n)≤bp(n)/cq(n)。让u=a/d,v=b/c，上式可写为u(p(n)/q(n))≤f(n)/g(n)≤v(f(n)/q(n))。所以有f(n)/g(n)=(p(n)/q(n))。对以下每个函数，用theta()记号表示与其同阶的只含一项的函数。例如，f(n)=(n+1)3可表示为f(n)=(n3)。(a)f(n)=n2+nlgn(b)f(n)=n(c)f(n)=(解：(a)f(n)=n2+nlgn=Q(n2)(b)f(n)=n(nlgn+2n)lg2n+n=Q((c)f(n)=(n2+lgn)(n+1)n+n用theta()记号表示对下面一段程序中语句x¬x+1被执行的次数的估计。fori¬1tonforj¬ito3ix¬x+1; endforendfor解：T(n)=i=1=i=1=2n(n+1)2+=Q(n2)。对以下每个级数和T(n)，用theta()记号表示与其同阶的只含一项的函数。T(n)=k=1T(n)=k=1解：(a)因为T(n)=k=1nk3lgk+1kT(n)<ck=1nklgk<c=cn2lgn。所以有T(n)=O(n又因为T(n)=k=1nΘ(klgk)T(n)>dk=1nklgk>dk=n/2nklgk>dk=n/2nn/2lgn/2=dn所以有T(n)=(n2lgn)和T(n)=(n2lgn)。(b)T(n)=k=1nk+klgk+83k2lgk+5k+1在我们讨论例1.3的线性搜索算法的平均复杂度时，我们假设数字x总可以在数组A中找到。这简化了问题。如果我们假定，x不出现在数组A中的概率是Pr(xA[1..n])=0.2，而x等于A中任一个数的概率相同，即Pr(x=A[1])=Pr(x=A[2])=…=Pr(x=A[n])，求线性搜索算法的平均复杂度。解：平均复杂度是：0.2n+1−0.2n(1+2+…+n)=0.2n+0.8n+12=0.6第2章 分治法用分治法设计一个算法找出数组A[1..n]中的最大的数，并分析所需的比较次数。解：以下用分治法的算法是作用在数组A[p,r]上的，p≤r。在调用该算法时，只须置p=1，r=n即可。Maximum(A[p..r],Max)ifp=rthenMaxA[p] exitendifq(p+r)/2Maximum(A[p..q],Max1)Maximum(A[q+1,r],Max2)Maxmax{Max1,Max2}End 我们用T(n)表示数组中数字间的比较次数，则有以下递推关系：T(n)=T(n/2)+T(n/2)+1T(1)=0我们用归纳法证明T(n)=n–1。归纳基础：因为T(1)=0，所以T(n)=n–1显然在n=1时正确。归纳步骤：由递推关系和归纳假设我们有以下推导：T(n)=T(n/2)+T(n/2)+1=(n/2-1)+(n/2-1)+1=n/2+n/2-1=n–1。归纳成功。用分治法设计一个算法同时找出数组A[1..n]中的最大和第二大的数，n2，并分析所需的比较次数。解：以下分治法的算法是作用在数组A[p,r]上的,p≤r。在调用该算法时，只须置p=1，r=n即可。Largest-and-second-largest(A[p..r],L,S)//L和S分别为最大和第二大的数ifp=rthenL¬A[p] S¬- //表示没有第二大数endifq¬ë(p+r)/2ûLargest-and-second-largest(A[p..q],L1,S1)Largest-and-second-largest(A[q+1..r],L2,S2)ifL1>L2thenL¬L1 S¬max{L2,S1}elseL¬L2 S¬max{L1,S2}endif End我们用T(n)表示数组中数的比较次数，则有以下递推关系：T(n)=T(ën/2û)+T(én/2ù)+2 T(1)=0它的解可用主方法得到。令n=2k，则有T(n)=2T(n/2)+2=Q(n)。如果想知道更为准确的常数因子，我们可用归纳法证明T(n)=2n–2。归纳基础：因为T(1)=0所以T(n)=2n–2显然在n=1时正确。归纳步骤：由递推关系和归纳假设有以下推导：T(n)=T(ën/2û)+T(én/2ù)+2=(2ën/2û-2)+(2én/2ù-2)+2=(2n-4)+2=2n–2。归纳成功。假设GOOGLE公司在过去n天中的股票价格记录在数组A[1..n]中。我们希望从中找出两天的价格，其价格的增幅最大。也就是说，我们希望找到A[i]和A[j]，i<j，使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1i<jn}。试设计一个复杂度为O(nlgn)或更好的分治算法。解：以下算法找出数组A[p..r]中序号i和j使得M=A[j]–A[i]的值最大，pi<jr。Divide-Conquer-Max-profit(p,r,m,i,j)//假设r³pifp=r thenm¬-¥ exit //m=-¥表示只有一天的价格endifq=ë(p+r)/2ûDivide-Conquer-Max-profit(p,q,ml,il,jl)Divide-Conquer-Max-profit(q+1,r,mr,ir,jr)FindxsuchthatA[x]=min(A[p],…,A[q])FindysuchthatA[y]=max(A[q+1],…,A[r])mc¬A[y]–A[x]ifmc³max{ml,mr} thenm¬mc i¬x j¬y elseifml³mr thenm¬ml i¬il j¬jl elsem¬mr i¬ir j¬jr endifendifEnd调用Divide-Conquer-Max-profit(1,n,m,i,j)后即可找到对数组A[1..n]的解。上面算法的复杂度可由下面递推关系求出：T(n)=T(ën/2û)+T(én/2ù)+Q(n)=Q(nlgn)。稍加修改后，我们可以得到O(n)复杂度的分治术算法。我们留给读者思考。设A和B是两个nn矩阵。众所周知，计算乘积C=AB通常需要(n3)次乘法和加法。基於分治术的Strassen算法可以改进这个复杂度。下面是这个算法。为简化起见，我们假设n=2k。Strassen’salgorithm(A,B,n);将A和B各自划分为4个n/2n/2的矩阵如下。A=A11A12A按下面公式递归计算出7个n/2n/2的矩阵。P=(A11+A22)(B11+B22); Q=(A21+A22)B11;R=A11(B12–B22); S=A22(B21-B11);T=(A11+A22)B22; U=(A21-A11)(B11+B12);V=(A12–A22)(B21+B22)。按下面公式计算出4个n/2n/2的矩阵。C11=P+S–T+V

; C12=R+T

;C21=Q+S; C22=P+R–Q+U;输出结果如下。C=AB=C11请分析Strassen算法的复杂度。你不必证明其正确性。解: 将A和B各自划分为4个n/2´n/2的矩阵后，第2步和第3步递归地进行7次n/2´n/2矩阵之间的乘法和18次n/2´n/2矩阵间的加法。所以，我们可以有以下的递推关系：T(n)=7T(n/2)+18n2它的解是T(n)=Q()=Q()。如果我们只考虑乘法次数，那么其递推关系是T(n)=7T(n/2)，它的解仍是T(n)=Q()=Q()。证明式（2.1）满足T(n)=T(ën/2û)+1lg(n+1)。证明：我们用归纳法证明。归纳基础：当n=0时，式（2.1）给出T(0)=0。因为lg(0+1)=0，命题T(n)lg(n+1)正确。当n=1时，T(1)=T(0)+1=1。因为lg(1+1)=1，命题T(n)lg(n+1)也正确。归纳步骤：假设当n=0，1，2，…，k-1（k2）时我们有T(n)lg(n+1)。我们证明当n=k时也有T(n)lg(n+1)。由递推关系，我们有T(k)=T(ëk/2û)+1。因为k2，有ëk/2ûk-1。从归纳假设，T(ëk/2û)lg(ëk/2û+1)，从而有：T(k)=T(ëk/2û)+1lg(ëk/2û+1)+1=lg(ëk/2û+1)+1=lg(ëk/2û+1)+lg2=lg(2ëk/2û+2)。如果k是一个奇数，我们有：T(k)lg(2ëk/2û+2)=lg(2(k-1)/2û+2)=lg(k+1)。 如果k是一个偶数，我们有：T(k)lg(2ëk/2û+2)。=lg(k+2)=lg(k+1)。（因为k+1是奇数，向上取整后，两者相等。）归纳成功。用替換法获得以下递推关系的一个渐近上界。(a) T(n)=T(n/2)+2T(n/4)解: 我们归纳证明，存在一个正数c使得T(n)≤cn。归纳基础：显然我们可以找到正数c，使得在n=1，2，3，4时，T(n)≤cn。归纳步骤：假设存在正数c，当n=1，2，3，4，5，…，k-1（k5）时我们有T(n)£cn。我们证明当n=k时也有T(n)£cn。因为当n5时有n/2<n，n/4<n，由归纳假设有T(n/2)£cn/2和T(n/4)cn/4。把这两个关系代入到原递归关系中，得到T(n)=T(n/2)+2T(n/4)cn/2+2cn/4=cn。归纳成功，所以有T(n)=O(n)。(b) T(n)=2T(ën/2û+5)+n解：我们归纳证明，存在一个正数c使得在n≥1时有T(n)£c(n-10)lg(n–10)。归纳基础：这样的正数c在n20时显然可以找到，使得T(n)£c(n-10)lg(n–10)。归纳步骤：设存在正数c，当n=1，2，…，k-1（k21）时我们有T(n)£c(n-10)lg(n–10)。我们证明当n=k时也有T(n)£c(n-10)lg(n–10)。我们可设c>10。首先，因为k-1≥20，ën/2û10。所以ën/2û+5ën/2û+ën/2û-1k-1。由归纳假设有T(ën/2û+5)£c[(ën/2û+5)-10]lg[(ën/2û+5)-10]，即T(ën/2û+5)£c(ën/2û-5)lg(ën/2û-5)。把这个关系代到原递推关系中，得到T(n)=2T(ën/2û+5)+n£2c(ën/2û-5)lg(ën/2û-5)+nc(n–10)lg(n/2-5)+n=c(n–10)lg[(n-10)/2]+n=c(n–10)[lg(n-10)-1]+n=c(n–10)lg(n-10)–c(n–10)+n<c(n–10)lg(n-10)–10(n–10)+n<c(n–10)lg(n-10) (因为–10n+100+n=100-9n<0)所以有T(n)£c(n-10)lg(n–10)=O(nlgn)。证明以下递推关系有T(n)=O(2n)

:(a) T(n)=nT(n/2)+nT(1)=1。解：我们用归纳法证明，存在正数c>0使得当n1时有T(n)c2n。归纳基础：我们可假定当n≤5时，存在正数c>1使得T(n)c2n。归纳步骤：假定当n=1，2，…，k-1(k6)时，T(n)c2n。我们证明当n=k时仍有T(n)c2n。由归纳假设，我们有T(n/2)c2n/2。因此，由递推关系，我们可得：T(n)=nT(n/2)+ncn2n/2+n 很容易观察到，当n6时，n2n/2–1，我们有T(n)cn2n/2+nc(2n/2–1)2n/2+nc2n–c2n/2+n<c2n (因为n<2n/2和c>1)所以T(n)=O(2n)

。(b) T(n)=T(n-1)+T(n-2)+n2T(1)=1，T(2)=2。解：我们用归纳法证明，存在正数c>0使得当n1时有T(n)c2n。归纳基础：当n=1和n=2时，取c=5，显然有T(n)<52n。归纳步骤：假定当n=1，2，…，k-1时，我们有T(n)52n。我们证明当n=k时仍有T(n)52n。由归纳假设，我们有T(n-1)52n-1和T(n-2)52n-2。因此，由递推关系，我们可得：T(n)=T(n-1)+T(n-2)+n252n-1+52n-2+n2 因为当n>1时，显然有n252n-2，所以我们有T(n)52n-1+52n-2+n252n-1+52n-2+52n-2=52n归纳成功，所以T(n)=O(2n)

。(c) T(n)=5n2T(n/2)+n3T(1)=1。解：我们用归纳法证明存在正数c>0使得当n1时有T(n)c2n。归纳基础：我们可假定当n≤30时，存在正数c>1使得T(n)c2n。归纳步骤：假定当n=1，2，…，k-1(k31)时，存在正数c>1使得T(n)c2n。我们证明当n=k时仍有T(n)c2n。由归纳假设，我们有T(n/2)c2n/2，因此，由递推关系，我们可得：T(n)=5n2T(n/2)+n35n2c2n/2+n3。因为当n>30时，显然有n32n/2–1，所以，当n>30时，我们有T(n)5n2c2n/2+n3n3c2n/2+n3(2n/2–1)c2n/2+n3c2n–c2n/2+n3c2n (因为n32n/2-1和c>1)所以T(n)=O(2n)

。用序列求和法解以下递推关系。(a) T(n)=4T(n/2)+n2lgn解：设n=2k，得到T(2k)=4T(2k-1)+22klg2k。令W(k)=T(2k)，得到W(k)=4W(k-1)+k4k。用序列求和法，得到以下演算：W(k)=4W(k-1)+k4k=4[4W(k-2)+(k-1)4(k-1)]+k4k=42W(k-2)+(k-1)4k+k4k =42[4W(k-3)+(k-2)4(k-2)]+(k-1)4k+k4k=... =4kW(0)+4k+24k+...+(k-2)4k+(k-1)4k+k4k=4kW(0)+4k(1+2+...+(k-2)+(k-1)+k)=4kW(0)+4k(k(k+1)/2)=(22kk2)。因为k=lgn，故有T(n)=(n2(lgn)2)。(b) T(n)=3T(n/3)+n解：设n=3k，得T(3k)=3T(3k-1)+3k 用序列求和法，得到以下演算：T(3k)=3T(3k-1)+3=3[3T(3k-2)+3k−1(k−1)=32T(3k-2)+3k(k−1)=...=3kT(30)+3klg3[11+12+…=(3klg3=(nlglgn)。用主方法解以下递推关系。T(n)=4T(n/2)+nT(n)=4T(n/2)+n2T(n)=4T(n/2)+n3T(n)=7T(n/2)+n2T(n)=4T(n/3)+nT(n)=3T(n/9)+5nT(n)=4T(n/2)+n2n解：(a)a=4,b=2,logba=2。显然，可令=0.5使f(n)=n=O(n2-)=O(n1.5)。所以T(n)=(n2)。(b)a=4,b=2,logba=2。显然，f(n)=n2=(nlgba)。所以T(n)=(n2(c)a=4,b=2,logba=2。显然，可令=0.5使f(n)=n3=(n2+)=(n2.5)。再有af(n/b)=4(n/2)3=0.5n30.5f(n)。所以T(n)=(f(n))=(n3)。(d)a=7,b=2,logba=2.81。因为lgba=log27>2，所以T(n)=Q(nlg2(e)a=4,b=3,logba=1.26。显然，可令e=0.1>0使f(n)=n=O(n1.26-)。所以有T(n)=Θ(nlogba)=Q((f)a=3,b=9,logba=0.5。因为f(n)=5n=Θ(nlogba)，所以有T(n)=Θ(nlogbalgn)=(n0.5lg(g)a=4,b=2,logba=2。因为f(n)=n2n=n5/2=W(n2+0.1)，再有af(n/b)=4n22n2=12n2ncf(n)，这里cT(n)=Q(f(n))=(n2n)。解递推关系T(n)=2T(n)+lgn。解：令n=2k，得到T(2k)=2T(2k/2)+k。定义W(k)=T(2k)，我们有如下推导：W(k)=2W(k/2)+k=(klgk)。 因此，T(n)=(klgk)=(lgnlglgn)。证明以下序列和的公式的正确性。(a)k=1nk2k=(n-1)2n+1+2证明：令T(n)=k=1nT(n)=2T(n)-T(n)=k=1nk=[n2n+1+k=2n(k−1)2k]=n2n+1–2-k=2=n2n+1–2–(2n+1–4)=(n-1)2n+1+2。(b)k=1nklgk=(n证明:令T(n)=k=1n首先我们有T(n)=k=1nklgkk=1nklgn=lgnk=1T(n)=k=1nklgkk=n/2nklgkk=n/2n(n2lgn2)n2所以有T(n)=(n2lgn)。*(c)k=2nklgk证明: 令T(n)=k=2nklgk并假定T(n)=k=2nklgk>k=2nkT(n)=k=2nklgk=k=2nklgk+k=n+1<k=2nk<k=2nk<k=2nk<k=2nk+=O(n)+O(n2=O(n2 所以有T(n)=Q(n2lg用积分法证明1k+2k+3k+…+nk=(nk+1)，这里k是任一个固定的正整数。证明： 因为i−1ixkdx<i0nxkdx<i=1n1k+1nk+1<i=1nik<1k+1[(n+因为nk+1=((n+1)k+1)，我们有i=1nik=1k+2k+3k+…+nk=(n假设我们开一部卡车从城市A到城市B，中间一共经过n个苹果市场，包括城市A和城市B的苹果市场，并且编号为1到n。在市场i，1≤i≤n，从顾客的观点看，其每市斤的买入价B[i]和卖出价S[i]都已知，单位是元。下图给出了一个n=6的例子。现在我们计划找一个市场i买苹果，然后再找一个市场ji把苹果卖掉使得赚的钱最多(如果根本赚不到钱，则使亏损越小越好)。我们假设卡车不可以向回开，并且只做一次买卖。例如，在上面的例子中，最好的方案是在市场4买苹果而在市场6卖出去，这样做每斤可赚7-2=5元钱。请设计一个分治算法找出市场i和j使得利润最大或亏损最小，并分析算法复杂度。解：我们设计一个在市场p到市场r之间进行买卖的最佳解，1prn,然后调用这个算法时置p=1和r=n即可。注意，题目要求ji，所以i=j是允许的。D&C-Max-Apple-Profit(B[],S[],p,r,M,i,j)ifp=r then MS[p]–B[p] //只有一个市场情形 ip jp else q(p+q)/2 D&C-Max-Apple-Profit(B[],S[],p,q,Ml,il,jl) D&C-Max-Apple-Profit(B[],S[],q+1,r,Mr,ir,jr) findleftsuchthatB[left]=min{B[u]|puq} findrightsuchthatS[right]=max{S[u]|q+1ur} McS[right]–B[left] ifMc>max{Ml,Mr} then MMc ileft jright else ifMl>Mr then MMl iil jjl else MMr iir jjr endif endifendifreturn(M,i,j)上面的算法对应的递推关系是T(n)=T(n/2)+T(n/2)+(n)=(nlgn)。注：上面的算法可改进为O(n)，我们略去讨论。假设n个学生S[i]的身高height[i]不同,1≤i≤n，并且已排序为height[1]<height[2]<…<height[n]。另外，他们的性别对应地记录在数组sex[1..n]中，sex[i]=F表示S[i]是女生，sex[i]=M表示S[i]是男生，1≤i≤n。如果sex[i]=F，sex[j]=M,并且height[i]<height[j],那么S[i]和S[j]可组成一对合格的舞伴。请用分治法设计一个复杂度为O(n)的算法来计算在这n个学生中有多少个不同的合格的配对方案。解：我们用分治法为学生序列S[p..r]设计一个计算配对方案个数的算法，然后调用这个算法时置p=1和r=n即可。这个算法在计算配对方案个数(number-pairs)时，同时算出S[p..r]中有多少个女生和多少个男生。Dancing-pairs(p,r,number-pairs,number-F,number-M) //假设rpifp=r then number-pairs0 //只有一个学生 ifsex[p]=F then number-F1 number-M0 else number-F0 number-M1 endif else q=(p+r)/2 Dancing-pairs(p,q,number-pairs-L,number-F-L,number-M-L) Dancing-pairs(q+1,r,number-pairs-R,number-F-R,number-M-R) number-pairsnumber-pairs-L+number-pairs-R+number-F-Lnumber-M-R number-Fnumber-F-L+number-F-R number-Mnumber-M-L+number-M-RendifEnd算法的复杂度为T(n)=T(n/2)+T(n)+(1)=(n)。给定序列A[1],A[2],…,A[n],请用分治法设计一个复杂度为O(nlgn)的算法来找出其中最长一段递增(不减)序列段，即找出两个序号ij,使得A[i]A[i+1]A[i+2]…A[j],并使j-i+1最大。解：我们用分治法为序列A[p..r],p<r,设计一个复杂度为O(nlgn)的算法来找出其中最长递增序列段，然后调用这个算法时置p=1和r=n即可。Longest-increasing-segment(A[],p,r,d,i,j)//假设rp,A[i]到A[j]是最长递增序列段，长为d=j-i+1。ifp=r then d1 ijp else q=(p+r)/2 Longest-increasing-segment(A[],p,q,dl,il,jl) Longest-increasing-segment(A[],q+1,r,dr,ir,jr) icq while (ic–1)pandA[ic-1]A[ic] icic–1 endwhile jcq while(jc+1)randA[jc+1]A[jc] jcjc+1 endwhile dcjc–ic+1 ifdcmax{dl,dr} then ddc iic jjc else ifdldr then ddl iil jjl else ddr iir jjr endif endifendifEnd该算法的复杂度为T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。在一条东西方向的大街上有n个人家，它们与西头的距离顺序为H[1]<H[2]<…<H[n]。另外，街上有m个学校，m<n,它们与西头的距离顺序为S[1]<S[2]<…<S[m]。假设每家都有学生，并且步行到最近的学校上学。假设某家与西头的距离是x,请用分治法设计一个复杂度为O(lgm)的算法来确定这家的学生应该去哪所学校和步行的距离有多远。请用Nearest-school(S[1..m],k,d,x)作为你的算法的名字。其中，k表示S[k]是要去的学校，d表示从x到S[k]的距离。下面是一个利用(a)中的算法而设计的分治法算法。它确定这n家中哪家学生步行的距离最远，有多远，和去哪所学校。调用这个算法时置i=1和j=n即可。请证明这个算法的复杂度是O(nlgm)。Longest-Distance(H[i..j],S[1..m],u,h,dist) //S[u],h和dist是答案,ijifi=j then xH[i] Nearest-school(S[1..m],k,d,x) //调用(a)中的算法 uk hi distd else mid(i+j)/2 Longest-Distance(H[i..mid],S[1..m],u-L,h-L,dist-L) Longest-Distance(H[mid+1..j],S[1..m],u-R,h-R,dist-R) ifdist-L>dist-R then uu-L hh-L distdist-L else uu-R hh-R distdist-R endifendifEnd调用Longest-Distance(H[1..n],S[1..m],u,h,dist)后，我们得到从家h到学校u的距离最远，该距离为dist。解：(a) 我们考虑学校序列为S[p..r]，算法如下。然后调用这个算法时置p=1和r=m即可。Nearest-school(S[p..r],k,d,x) //p≤r,S[k]和d是答案。ifp=r then kp d|S[k]–x| else mid(p+r)/2 if|S[mid]–x|≤|S[mid+1]–x| thennearest-school(S[p..mid],k,d,x) elsenearest-school(S[mid+1..r],k,d,x) endifendifEnd调用Nearest-school(S[1..m],k,d,x)后，我们得到与x最近的S[k],1km,其距离为d。时间复杂度为T(m)T(m/2)+O(1)=O(lgm).(b)根据算法，我们可得递推关系时间复杂度为T(n)=T(n/2)+T(n/2)+O(1),T(1)=O(lgm)。用求和法，设n=2k。T(n)=2T(n/2)+O(1)=22T(n/4)+O(1)+O(1)=…=2kT(1)+O(k)=O(nlgm)。*在一条东西方向的大街上有n个人家，它们与西头的距离顺序为H[1]<H[2]<…<H[n]。另外，街上有m个学校，1m<n,它们与西头的距离顺序为S[1]<S[2]<…<S[m]。另外，假设人家H(k),1kn,有U(k)个学生，并且步行到最近的学校上学。为确定起见，如果家两边的学校等距离，学生选西边的学校。请用分治法设计一个复杂度为O(nlgm)的算法来确定哪个学校会接收最多的学生。解：我们假设住家序列为H[u..v]，学校序列为S[i..j]，用分治法来确定哪个学校会接收最多的学生。然后，调用这个算法时，置u=1,v=n,i=1,j=m即可。Serve-most-students(S[i..j],H[u..v],k,p) //学校S[k]会接收最多的学生，人数为p。ifu>v //意味着没有人家，或者没有人家离S[i..j]最近 then k0 p0 returnendififi=j then ki pt=u returnendifmid-school(i+j)/2mid-line(S[mid-school]+S[mid-school+1])/2huwhile H[h]≤mid-line hh+1 //找出在mid-line东边的第一家序号endwhileServe-most-students(S[i..mid-school],H[u..h-1],k1,p1)Serve-most-students(S[mid-school+1,j],H[h..v],k2,p2)ifp1>p2 then kk1 pp1 else kk2 pp2endifEnd调用Serve-most-students(S[1..m],H[1..n],k,p)即可得到答案。算法复杂度可由如下递归关系求得：T(n,1)=O(n) T(n,m)=T(n1,m/2)+T(n2,m/2)+cn //c是常数，n1+n2=n。令m=2k，可把递推关系简化为：T(n,m)=T(n1,m/2)+T(n2,m/2)+cn我们对m用归纳法证明，存在常数d>c，使得T(n,m)≤dnlgm+d(n+m)。归纳基础：当m=1时，命题显然成立。归纳基础：当m>1时，我们有以下推导： T(n,m)=T(n1,m/2)+T(n2,m/2)+cn≤[dn1lg(m/2)+d(n1+m/2)]+[dn2lg(m/2)+d(n2+m/2)]+cn //由归纳假设=dn1(lgm-1)+d(n1+m/2)+dn2(lgm-1)+d(n2+m/2)+cn=dn1lgm+dn2lgm+dm+cn<dnlgm+d(n+m) 归纳成功。因为m<n，T(n,m)=O(nlgm)。给定序列A[1],A[2],…,A[n],请用分治法设计一个复杂度为O(nlgn)的算法来找出其中一段递增(不减)序列段，即找出两个序号ij,使得A[i]A[i+1]A[i+2]…A[j],并使它们的和，k=ij解： 我们用分治法为序列A[p..r]设计一个复杂度为O(nlgn)的算法来找出其中最长递增序列,然后调用这个算法时置p=1和r=n即可。max-value-increasing-segment(A[p..r],d,i,j)//假设rp,A[i]到A[j]是输出递增序列段，其和为d=k=ijifp=r then dA[p] ijp else q=(p+r)/2 Max-value-increasing-segment(A[p..q],dl,il,jl) Max-value-increasing-segment(A[q+1..r],dr,ir,jr) ifA[q]>0 then icq dcA[q] while(ic–1)pandA[ic-1]A[ic]andA[ic-1]>0 icic–1 dcdc+A[ic] endwhile jcq while(jc+1)randA[jc+1]A[jc] jcjc+1 dcdc+A[jc] endwhile else dc- endif ifdcMax{dl,dr} then ddc iic jjc else ifdldr then ddl iil jjl else ddr iir jjr endif endifendifEnd该算法的复杂度为T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。给定序列A[1],A[2],…,A[n],请用分治法设计一个复杂度为O(nlgn)的算法来找出其中两个序号i<j,使得A[i]A[j],并使它们的和，A[i]+A[j]，最小。如果没有这样两个数，则输出+∞。解: 这是和书中例题2.9对称的题目，伪码如下。 Min-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r then M+∞ //只有一个数 else mid (p+r)/2 Min-Sum-Two-Numbers(A[p..mid],i1,j1,M1) Min-Sum-Two-Numbers(A[mid+1..r],i2,j2,M2) findi3suchthatA[i3]=min{A[k]|p≤k≤mid} S{A[k]|mid+1≤k≤r,A[i3]≤A[k]} ifS= thenM3+∞ else findj3suchthatA[j3]=min{A[k]|A[k]S} M3A[i3]+A[j3] endif ifM3<M2andM3<M1 then MM3 ii3 jj3 else ifM2<M1 then MM2 ii2 jj2 else MM1 ifM≠+∞ then ii1 jj2 endif endif endifendifEnd当我们调用Max-Sum-Two-Numbers(A[1..n],i,j,M)时，原问题得解。算法复杂度可由下面递推关系得到：T(n)=2T(n)+O(n)=O(nlgn)。在序列A[1],A[2],…,A[n]中，一个数可能出现若干次。如果一个数出现的次数k超过一半，即k>n/2，那么我们说这个序列有一个垄断数。请用分治法设计一个复杂度为O(nlgn)的算法来判断一个给定序列是否有一个垄断数。如果有，报告这个数及其出现次数k，否则报告k=-。我们约定，该算法只能用比较序列中两数字是否相同来判断，比较的结果不报告谁大谁小，只告诉相同或不相同。当比较的两数字不是序列中数字时，可以报告大小。解: 算法的伪码如下，正确性显然。Dominating-number(A[p..r],i,k) //如果有，A[i]出现k>n/2次，否则i=nil，k=-ifp=r then ip k1 else mid (p+r)/2 Dominating-number(A[p..mid],i1,k1) Dominating-number(A[mid+1,r],i2,k2) ifk1- //只有A[i1]和A[i2]可能，检查之。 then forjmid+1tor ifA[j]=A[i1] then k1k1+1 endif endfor endif ifk2- then forjptomid ifA[j]=A[i2] then k2k2+1 endif endfor endif ifk1>(p-r+1)/2 then ii1 kk1 else ifk2>(p-r+1)/2 then ii2 kk2 else inil k- endif endifendifEnd该算法的复杂度为T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。*每个多米诺骨牌有两个正整数。假设有n个多米诺骨牌S1,S2,…,Sn水平地放成一排如下例所示。假设我们不能改变骨牌之间相对位置，但可以原地翻转每个骨牌。我们用L[i]和R[i]分别表示Si(1in)左边和右边的数。例如，在下例中L[1]=5,R[1]=8,L[2]=4,R[2]=2等。如果L[i]<R[i]，我们称Si被置为状态0并记为W[i]=0，翻转后则为状态1并记为W[i]=1。例如下例中S1为状态0而S2为状态1。如果L[i]=R[i]，Si的状态可记为W[i]=0或W[i]=1。请用分治法设计一个算法来确定每个骨牌的状态使得M=i=1n−1R[i]×L[i+1]取得最大值解: 这题的主要困难在于，如果我们用常规的办法将序列分为两半求解，那么两部分的最佳解合在一起不一定给出全局的最佳解。技巧是，我们把问题稍加修改。我们在原序列中引入两个非负整数u和v,并确定各骨牌状态以使得M=u´L[1]+i=1n−1R[i]×L[i+1]+R[n]´v取得最大值。显然，如果我们能解决这个修改后的问题，那么当我们置u=v=0的话即得出原问题的解。假设S[p,r]表示从Sp到Sr的骨牌序列，下面的分治算法确定这些骨牌的状态使M=u´L[p]+i=pr−1R[i]×L[i+1]+R[r]´v取得最大值。我们假设Si(1£i£n)中两数字存放在A[i]和B[i]中并且A[i]£BMax-Value(u,v,S[p,r],W[p,r],m)ifp>r then m¬u´v //骨牌序列为空 exitendif q¬x¬A[q]y¬B[q] //中间骨牌的两个数x和yMax-Value(u,x,S[p,q-1],W1[p,q-1],m1) //x用于左边序列Max-Value(u,y,S[p,q-1],W2[p,q-1],m2) //y用于左边序列Max-Value(x,v,S[q+1,r],W3[q+1,r],m3) //x用于右边序列Max-Value(y,v,S[q+1,r],W4[q+1,r],m4) //y用于右边序列if(m1+m4)>(m2+m3) //中间骨牌为状态0时较好 then W[p,q-1]¬W1[p,q-1] W[q+1,r]¬W4[q+1,r] W[q]¬0 m¬(m1+m4) else W[p,q-1]¬W2[p,q-1] //中间骨牌为状态1时较好 W[q+1,r]¬W3[q+1,r] W[q]¬1 m¬(m2+m3)endifEnd算法正确性显然，当我们调用Max-Value(0,0,S[1,n],W[1,n],m)时便得到结果。算法复杂度为T(n)=4T(n−12)+Q(n)=Q(n2第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的结点数最多为én2ℎ+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≤én2ℎ+1ù因为x必须是整数，故有x≤én2ℎ+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