资源描述：
《算法设计与分析（王多强）作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第二章递归习题导论4.1-17(/?)=27(b/2)+1=>M=2T5/2)+1%)习题导论4.1-6Tin)=2T(0)+1做代换：m=log2n7X2")27(2"/彳)+另S(m)=T(2m)则有：S(/z?)=2S(zz?/2)+1化简有:S(m)=O(m)所以T(n)=O(logn)习题4.2-27(/7)=T(n/3)+7(2/7/3)+劲注意最长分支2n/3-*(2n/3)2-*(2n/3)3...-*(2n^)log3/2n情况40(n2)情况2,©(n2logn)习题4.3-1a)T(n)=4T(n/2)+nb)T(n)=4T(n/2)+n2c)T(
2、n)=4T(n/2)+n3情况3,◎(r?).验证4f(n/2)=4(n/2)3=n3/2^cn3,这里c取大于1/2小于1的数即可,如珈习题4.3-4f(n)/nlogba=n2logn/n'°g"二lognvn所以不满足规则3直接化简即可，T(n)=O(n2log2n)第三章习题4.5注意三分Z—和三分Z二分割点的计算ml=(2low+high)^m2=(low+2high)/3习题4.20主要是验证T(n/r)+T(0)＞
3、«n/r+O的数量级是否小于n的1次方(线性)利用关系式：/r」n(/7-r-1)//进行化简r=3：r/2~
4、~
5、_/2//_]/2~
6、
7、＞2z?/r/2=n/r」＞(/?一2)/3则，刀一卜/2北刀/厂」/2]＜/?-(/?-2)/3=2/7/3+2/3则，n〃+羊n+厉超线性了r=7：r/2]/r/2〕＞/7」/2=2山/7」＞2(刀一6)/7则，n-r/i//」/2〕v刀一2(刀一6)/7=5刀/7+12/7可证,当n＞48的时候，上式小于3伙则，n/7+3nA=25n/28＜n成立r=9：r/2][n/厂」/2〕＞5[刀/9」/2=(5/2)^/9」＞5(刀-8)/18n一r/2[n//」/2〕＜13/?/18+40/18可证，当n>20的时候，上式小于7n/8则，n/9+
8、7n/8=71n/729、做权值累加，取得权值V2分割点才可以。C）改造SELECT2算法即可。需要注意的是，在求得mm后，应该从整个序列开始Z处（下标为1）累加权值直至mm,这个累加范围是相对全部n个元素整体，不是仅相对于当前划分区间。如果mm前而的元素权值累加和＞1/2,则在前半区间继续处理；否则mm前面的元素权值累加和＜1/2，则在前半区间继续处理；再否则，mm前面的元素权值累加和二1/2,则mm就是带权中位数。再需要注意的是，每次计算权值Z和，为了避免每次都从1开始累加，可以设置一个数组记录曾经计算过权值之和的位置，以后的权值基于以前的部分和增量式地累加，会进一步改进算法。D）一维邮局问
10、题，E）二维邮局问题，参见课件上的证明即可第五章贪心策略习题5.2(1)FO(I)=16^5⑵FG(I)=47FO(I)/FG(I)=160141⑶FG(I)=54FO(I)/FG(I)=160162习题5.4集合覆盖(1)procedureSetCover(S,m,T)intd[l..m],q,k;一mLetS=US-/=!LetT=(/)k=0;whileT=SdoLetAS=S-TfindiwhereSjisthesetofmaxAsQS■11、Sj[i]=O。用逻辑运算实现集合的交、并、差。时间：O(mn2),S-0(刀)，AsAS’=0{mn),最坏的情况S’二{/},循环重复n次空间：0(n),S=0(/7),T=0(刀)，T=0(刀),AS*=0{ii)(2)举例说明Sl={3/5},S2={l/3,4}/S3={l,2,4}上述算法：T={S2,S1,S3}最优解:V={S1,S3}习题5.8作业按效益值排序p7,p3,p4,p6,p2,pl,p5J己分配的时间片正被考虑的作业动作①无7分配[2,2]{7}[1,2]3分配[3,4]{7,3}[1,2],⑶4]4分'配[
