实例介绍
【实例简介】
算法设计与分析-张德富-完整版本答案。 此版本答案诗最全的。很详细。 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-课后答案期末试卷|复习提纲 【实例截图】
【核心代码】
算法设计与分析-张德富-完整版本答案。 此版本答案诗最全的。很详细。 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-课后答案期末试卷|复习提纲 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论