算法设计与分析-张德富-答案全

3星(超过75%的资源)
所需积分/C币:37 2018-12-12 20:14:14 1.65MB PDF
5594
收藏 收藏
举报

算法设计与分析-张德富-完整版本答案。 此版本答案诗最全的。很详细。 pdf后面带课件
4 max<4 ∑1 T(n)=CI ∑ 当数组A的第一个元素为最大时该算法达到最佳,此时t1=0 T(m)= (n-1)-(c2+c3) Ca=o(n) 当数组A是递增时该算法达到最坏,此时t=1 (n)-C1+C2*n+C3*(n-1)+4*(n-1)-(C2+c3+c4)4n+C1-C3-C4=6(n) 循环不变量:在for循坏第j个迭代执行前,max为当前数组A[1.1]中的最大值 初始步:在第一轮迭代前,产=1,当前数组中只有一个元素max=4[1],此时max确是 最大的,所以在初始化中不变量是正确的 归纳步:在for循环第j=k个迭代执行前,max是A[1,,k1]中的最大值,此后执 行笫j=k个迭代,将max与Ak进行比较并将较大的值赋给max,所以max仍然 是A[1…1]中的最大值 终止步:当产n+1时,for循环终止,此时max是A[1,n中的最人元素,即是全 数组中的最大值,所以算法是正确的。 17 1max←A[l] 3 for ie-2 to n do if maxs: A[i] then max←[i 7 return j 1.8 Exp(a, n) 2pow← hel÷nd0 pow←pow×a i+1 6 return pow 循环不变量:当执行第i次循环前,pow的值为a 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 初始步;当闩=1,即在第一轮循环前,pow为1,若n=0,则不循环,返回1,若n=1 则循环一次,pow=a,所以不变量正确 归纳步:当执行第i=k次循环前,假设pow的值为a4-1,当执行第i=k次循环后,则由 算法可知,pow=pow*=a*l=a,所以不变量仍正确 终止步:当in+1时,循环退出,此时共执行了n次循环,所以结果为a",算法是正 确的 Scarchx(a whex≠andi≤ndo t-1 ∥其中tn+1 n)=c1+c2l+c3(-1) 当第一个元素貮是指定数x时该算法达到最好情形,此时t-=1 7(n)=c1+C2=Q(1) 当该数组中不含指定数x时该算法达到最坏情形,此时t=n: T(m)=c1+C2(n+1)+c3=(m) 正确性证明: 循环不变量:当执行第i次循环前,指定数x不在当前数组A[1.1]中 初始步:当-1,即在第一轮循环前,当前数组为空,不包含指定数,所以循环不变 量成立。 归纳步:当执行第ik次循环前,指定数x不在当前数组A[1.k-1,当执行第ik 次循环后,此时表明x≠4[且还≤n,否则,找找到了指定数。因此,在执 行第i=k+1次循环前,指定数x个在当前数组A[1.k]中,所以循环不变量成 终止步:当n+1时,循环退出,此时,表明指定数x不在当前数组A1.n中。否则, 在前面任一次循环退岀,均找到了指定数,所以整个算法是正确的 1.10 要使运行时问100*n2比2快,则需要 100*n2<2 通过计算得n≥15 所以得n最小值为15 1.11 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 要使插入排序优于合并排序,则: 8n<64nlgn n /8< lgn /8 →2≤n≤43∥这两个值是通过计算得来的 实验题 1.11完成XOJ如下题目:1000,1001,1002,1003,1004 1000A+B1001宅男健身计划1002C=2+?1003Sot1004 Sort ver:2 注:100010011003必练习,1002和1004可不做 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 参考答案 要证明∫(n)=O(g(m)当且仅当存在正常数c1,C2,no,使得当n≥no吋, c1g(m)≤f(n)≤C2g(n)。取c1=3/5,c2=1代入不等式,由左不等式可得n>=2/13,右 不等式可得n>0。所以取n0=21/13所以当n≥m0,C1=3/5,C2=1时,f(mn)=((g(n) 2.2 因为f(n)≤max(f(m),g(n),g(m)≤max(f(n),g(n) 所以有f(m)+g(n)≤2max(f(n),g(n) 即(f(n)+g(n)≤max(f(n),g(n) 又因为max(f(n),g(n)=f(n)或者g(m) 所以max(f(n),g(n)≤f(n)+g(n) 对于n≥m,取c1 1,叮得 2 cI(f(n)+g(n))< max( f(n),g(n)<c,(f(n)+g(n) 故所证成立 2.3 要证(n+a)=(n)当且仅当存在正常数aLoC1C2,使 cn≤(n+a)≤c2 b 先设C=(),则由cn(m+a)(n)(m+a ◇n<n+a今一n<an>-2a 又因为n≥0,所以可取1=2,使得对于任何的a,当n≥n0时, 有(n)(n+a b 而当1n2a时,(m+a)=(n+1)5(n+)≤(n)5(2n)=2n 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 所以C2可取2 所以当c1=()C2=2,n1=20时,可证(n+a)=6mn ∥根据极限来证也可以。 2.4 要if(m)=⊙(m2)当且仅当存在正常数c1,c2,n0,使得当n≥n时 c1n2≤f(mn)≤c2n2,取C1=a/2,C2=2a,代入左不等式可得:=n2+b+c≥0,求出 b+、4ac-b 。代入右不等式可得:an-bn-c≥0,求出 h+vl-4ac-h b+4ac-b2|b+√-4ae-b2 取n0=max( 2a ,0)。当n≥n0 时,f(n)=()(n2 2.5 要证明f(m)=O(g(m)当且仅当存在正常数c,n0,使得当n≥n0时,有f(m)≤g(n),即 n2≤cn3,求解得c≥l/n≥0,所以对于所有的n≥0,有f(n)=O(g(n) 2.6 2”1=O(2")成立,因为存在正常数c≥2,使得当n≥0时,有2≤c2 2"=0(2")不成立,因为根据不等式2≤c2″计算可得c≥2”,当n无穷大时,c 不存在,所以不成立 2.7 由f(m)=O(g(m)可得存在正常数c,n0,当n≥m0时,有f(m)≤cg(n),可得 l/cf(n)≤g(m),所以存在一个正常数c1=1/c,当n≥n0时,c1f(m)≤g(n),所以 g(m)=9(f(m) 2.8 要证明n3=2(n2)当且仅当存在正常数c,no,使得当n≥m0时,有cn2≤n3,求解得 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 c≥l/n≥0,所以对于所有的n≥0,有n3=9(n 2.9 按照定义证明即可,比较简单,略(充分性,必要性) 2.10 由已知可得存在正常数n12n2,C1C2,使得当n≥n1时,有f1(n)≤Cig(mn)。当n≥n2时 有f2(m)≤C2(m)。所以f1(m)×f2(m)≤C1g(n)xC2!(m)=C1c2(g(n)xg(n),所以当 n0=max(n1,n2),C=c1c2时,f1(n)×f2(n)=O(g(n)×g(n) 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 参考答案 只雇用一次的概率是:1/n 雇佣n次的概率是:1/n! 刚好雇佣两次的概率: (n-1)!+(m-1)+1(2)+……+31(mn-4)!+2(n-3)!+1(n-2)! 3.2 最大值有可能在n个数的数组中的任一个位置出现,因此在每个位置出现的概率为1/n 假设在位置k出现,则需要比较k次,因此总的比较次数为 T(m)=∑k 3.3 对题意的理解: ①·个由n个PUSH、POP和 MULTIPUSH操作构成的序列 ②一个由n个PUSH、POP、 MULTIPOP和 MULTIPUSH操作构成的序列。 最坏情况下:一次 MULTIPUSH操作时间为Om) n个操作都为 MULTIPUSH操作 3.4 令C表示第i个运算的费用,则有 ii为2的整数幂 否则 则运算序列12345678 费用依次为12141118 故n个运算的费用为 ∑c≤n+∑2=n+(2n-1)<3n 故每次运算的分摊费用O() 3.5 给Push,Pop运算分摊费用为2,给复制栈运算的分摊费用为0。每调用一次Push或 Pop运算,均有1美元存款。因为堆栈的大小不会超过k,因此实际的复制费用也不会 超过k,它将山复制的元素的存款来支付。在进行一次复制栈运算之前要进行k次的Push 或Pop运算,因存款至少为k,所以保证每次仔款始终非负,即总的分摊费用为运 算序列实际费用的一个上界,为2n,即O(n)。 3.6 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲 令C1表示第i个运算的费用,则有 ii为2的整数幂 否则 给每个运算的分摊费用为C1=3 如果讠为2的整数幂,则用存储的钱支付 否则支付1,存款2。 运算序列 12345678 分摊费用为 实际费用依次为1214 存款为 235468105 故n个运算的总分摊费用为∑C=3n 而n个运算的实际费用为 ∑c,≤n+∑2′=n+(2n-1)<3n 因此总分摊费用是实际费用的上界 故每次运算的分摊费用O(1),n个运算的费用为O(n) 定义Φ(D,)=Φ(D)-Φ(D)(i≥1) 则(D0)=Φ(D0)-(D)=0,Φ(D)=(D)-(D0)≥0 分摊代价为: C=c1+Φ(D)-①'(D1) =c1+((D)-(D)-((D1)-(D0) +Φ(D)-①(D1) 3.8 令(D0)=0,定义 i为2的整数幂 (D)= (D-1)否则 其中i≥1。注意到对任意的i≥0,均有(D)≥0。如果i个是2的整数幂,则有 学霸助手[xuebazhushou.com-课后答案期末试卷|复习提纲

...展开详情
试读 126P 算法设计与分析-张德富-答案全
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
笨蛋程序员 嗯,资源不错。就是有些题没有答案。
2020-10-26
回复
pp_AAA 不错不错 可以的
2019-10-15
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
算法设计与分析-张德富-答案全 37积分/C币 立即下载
1/126
算法设计与分析-张德富-答案全第1页
算法设计与分析-张德富-答案全第2页
算法设计与分析-张德富-答案全第3页
算法设计与分析-张德富-答案全第4页
算法设计与分析-张德富-答案全第5页
算法设计与分析-张德富-答案全第6页
算法设计与分析-张德富-答案全第7页
算法设计与分析-张德富-答案全第8页
算法设计与分析-张德富-答案全第9页
算法设计与分析-张德富-答案全第10页
算法设计与分析-张德富-答案全第11页
算法设计与分析-张德富-答案全第12页
算法设计与分析-张德富-答案全第13页
算法设计与分析-张德富-答案全第14页
算法设计与分析-张德富-答案全第15页
算法设计与分析-张德富-答案全第16页
算法设计与分析-张德富-答案全第17页
算法设计与分析-张德富-答案全第18页
算法设计与分析-张德富-答案全第19页
算法设计与分析-张德富-答案全第20页

试读结束, 可继续阅读

37积分/C币 立即下载 >