《算法导论》习题
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
Chapter2 Getting Start
2.1 Insertion sort
2.1.2 将Insertion-Sort重写为按非递减顺序排序 2.1.3 计算两个n位的二进制数组之和
2.2 Analyzing algorithms
322.2.1将函数用符号表示 nnn/10001001003,,，,
2.2.2写出选择排序算法selection-sort
当前n-1个元素排好序后，第n个元素已经是最大的元素了.
2 最好时间和最坏时间均为 ,()n
2.3 Designing algorithms
22ifn ,,Tn(),,kTnnifnfork2(/2)2,1， , ,,2.3.3 计算递归方程的解 (1) 当时，，显然有 Tnnn()lg,k,1n,2
iii(2) 假设当时公式成立，即， Tnnni()lg2lg22,,,,ki,
i，1则当，即时， ki,，1n,2
iiiiiiii，，，，，，111111 TnTTiinn()(2)2(2)222(1)22lg(2)lg,,，,,，,，,,
？ ,Tnnn()lg
2.3.4 给出insertion sort的递归版本的递归式
, ,(1)1ifn, Tn(),,Tnnifn(1)()1,，, ,,
2.3-6 使用二分查找来替代insertion-sort中while循环内的
线性扫描，是否可以将算法的时间提高到, ,(lg)nn
虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但
是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂
2度依然是 ,()n
2.3-7 给出一个算法，使得其能在的时间内找出在一个n元,(lg)nn
素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间，然后再进行查找: ,(lg)nn
Search(A,n,x)
QuickSort(A,n);
i?1; j?n;
,while A[i]+A[j]x and i
4()2!()2,!(2)inininin,,？,,,？,, ,,i1
nn nnnon!,!(),？,
3.2.4与是否多项式有界 lg!nlglgn～，，，，,,,,
mmmmmmmmn2(ln1)ln1lnln,,设lgn=m，则 !2()(),,,,,,mmeemnee
?lgn～不是多项式有界的。
21m,mmmm2设，lglg!(2)22nmmm,,,,,，，,,
m,12 lglg12nmn,,,，
m,12lglg!2lglgnnn,,？ 是多项式有界的，，，，,,,,
3.2.5比较lg(lg*n)与lg*(lgn)
lg*(lgn)= lg*n-1
设lg*n=x，lgx
本文档为【《算法导论》习题答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483