[算法导论]习题答案

算法导论第二版答案

Chapter2 Getting Start

2.1 Insertion sort

2.1.2 将Insertion-Sort重写为按非递减顺序排序

2.1.3 计算两个n位的二进制数组之和

2.2 Analyzing algorithms

2.2.1将函数n3/1000100n2100n3用符号表示

2.2.2写出选择排序算法selection-sort

当前n-1个元素排好序后，第n个元素已经是最大的元素了. 最好时间和最坏时间均为(n2)

2.3 Designing algorithms

2ifn2T(n)k2T(n/2)nifn2,fork1 2.3.3 计算递归方程的解

（1） 当k1时，n2，显然有T(n)nlgn

（2） 假设当ki时公式成立，即T(n)nlgn2ilg2ii2i，

则当ki1，即n2i1时，

T(n)T(2i1)2T(2i)2i1i2i12i1(i1)2i2i1lg(2i1)nlgn T(n)nlgn

2.3.4 给出insertion sort的递归版本的递归式

(1)ifn1 T(n)T(n1)(n)ifn1

2.3-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到(nlgn)？

虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是(n2)

2.3-7 给出一个算法，使得其能在(nlgn)的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x

首先利用快速排序将数组排序，时间(nlgn)，然后再进行查找： Search(A,n,x)

QuickSort(A,n);

i←1; j←n;

while A[i]+A[j]x and i

if A[i]+A[j]

i←i+1

else

j←j-1

if A[i]+A[j]=x

return true

else

return false

时间复杂度为(n)。

或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为(nlgn)。 Chapter3 Growth of functions

3.1Asymptotic notation

3.1.2证明对于b0,(na)b(nb)

a0时，(na)b(nn)b2bnb

(na)n

bbbbbb对于c11,c22，c1n(na)c2n

a0时，(na)bnb

存在n02a，当nn0时，(na)(n/2)

bbbbbb对于c12,c21，c1n(na)c2n

3.1-4 判断2n1与22n是否等于O(2n)

3.1.6 证明如果算法的运行时间为(g(n))，如果其最坏运行时间为O(g(n))，最佳运行时间为(g(n))。

最坏时间O(g(n))，即Tc2g(n)；

最佳时间(g(n))，即Tc1g(n)

T(g(n))

3.1.7：证明o(g(n))(g(n))

定义

3.2 Standard notation and common functions

3.2.2 证明alogccloga bb

lgalogbclogbclga

lgclogbalgalgclgb lgalgclogbalgclgb

alogbcclogba

nnn!(2)andn!o(n) lg(n!)(nlgn)证明 3.2.3

lgn!lgilgnnlgn

i1i1nn

lgi[lgilg(ni)]lg[i(ni)]lg(

i1i1i1i1nn/2n/2n/2n1)nlgnnnlgn422

lg(n!)(nlgn)

当n>4时，i(ni)2，n!i(ni)2n,n!(2n) 2

i1n/2

n!nn,n!o(nn)

3.2.4是否多项式有界 lglgn！lgn!与

设lgn=m，

则m!)me2m()mem(lnm1)mlnm1nlnlnn ∴lgn！不是多项式有界的。 meme

mmmm2设lglgnm，m!m(2)222m1

lglgnm1，n22

lglgn!22m1m1 n lglgn是多项式有界的

3.2.5比较lg(lg*n)与lg*(lgn)

lg*(lgn)= lg*n-1

设lg*n=x，lgx

 lg*(lgn)较大。

Chapter4 Recurrences

4.1 The recursion-tree

4.1.1 证明T(n)T()1的解为O(lgn)

假设T()clg(b)clg(n/2b1) n-2b+2则T(n)clg(-b+1)+1=clg()+1=clg(n-2b+2)-clg2+1clg(n-b)2

T(n)O(lgn)

4.1.2 证明T(n)2T(n)n的解为O(nlgn)

设T(n)cnlgn

T(n)2cnlgnnclgnnn

c(n1)lg(n/2)ncnlgnclgncnncn(lgn1)nc(lgn2n)

lgn1lg(n1)，当c1/3,nc(lgn2n)

T(n)cnlg(n1),T(n)(nlgn)

T(n)O(nlgn)

4.1.3

将假设改为T(n) = cn lgn +b，只需要在T(1)=1的情况下成立。

4.1.6

计算T(n)2T1的解

令mlgn,T(2m)2T(2m/2)1

令T(n)=S(m),则S(m)2S(m/2)1

其解为S(m)(m),T(n)S(m)(lgn)

4.2 The recursion-tree method

4.2.1 T(n)(nlg3)

4.2.2 略

4.2.3 T(n)(n2)

4.2.5 T(n)(nlgn)

4.3 The master method

4.3.1 略

4.3.4 主方法是否适用方程T(n)4T(n/2)n2lgn，给出该方程解的一个上界

不适用

使用递归树方法可以求得其一个上界为O(n2lg2n)

4.3.5给出某常数a1,b1和函数f(n)，使得其满足主定理case3中除了af(n/b)cf(n)外的所有条件。

f(n)n(sinn2)，a1,b2，logba=0

sinn21,f(n)n,f(n)(nlogba)=(n)，0

af(n/b)f(n/2)n(sin(n/2)2)/2

若af(n/b)cf(n)

则n(sin(n/2)2)/2cn(sinn2)

sin(n/2)2c2(sinn2)

找不到这样的c1，总是满足上面的条件，如sinn

1时，sin(n/2)为/2，此时sin(n/2)21，所以af(n/b)cf(n)不满足。 2(sinn2)

算法导论第二版答案

Chapter2 Getting Start

2.1 Insertion sort

2.1.2 将Insertion-Sort重写为按非递减顺序排序

2.1.3 计算两个n位的二进制数组之和

2.2 Analyzing algorithms

2.2.1将函数n3/1000100n2100n3用符号表示

2.2.2写出选择排序算法selection-sort

当前n-1个元素排好序后，第n个元素已经是最大的元素了. 最好时间和最坏时间均为(n2)

2.3 Designing algorithms

2ifn2T(n)k2T(n/2)nifn2,fork1 2.3.3 计算递归方程的解

（1） 当k1时，n2，显然有T(n)nlgn

（2） 假设当ki时公式成立，即T(n)nlgn2ilg2ii2i，

则当ki1，即n2i1时，

T(n)T(2i1)2T(2i)2i1i2i12i1(i1)2i2i1lg(2i1)nlgn T(n)nlgn

2.3.4 给出insertion sort的递归版本的递归式

(1)ifn1 T(n)T(n1)(n)ifn1

2.3-6 使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到(nlgn)？

虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是(n2)

2.3-7 给出一个算法，使得其能在(nlgn)的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x

首先利用快速排序将数组排序，时间(nlgn)，然后再进行查找： Search(A,n,x)

QuickSort(A,n);

i←1; j←n;

while A[i]+A[j]x and i

if A[i]+A[j]

i←i+1

else

j←j-1

if A[i]+A[j]=x

return true

else

return false

时间复杂度为(n)。

或者也可以先固定一个元素然后去二分查找x减去元素的差，复杂度为(nlgn)。 Chapter3 Growth of functions

3.1Asymptotic notation

3.1.2证明对于b0,(na)b(nb)

a0时，(na)b(nn)b2bnb

(na)n

bbbbbb对于c11,c22，c1n(na)c2n

a0时，(na)bnb

存在n02a，当nn0时，(na)(n/2)

bbbbbb对于c12,c21，c1n(na)c2n

3.1-4 判断2n1与22n是否等于O(2n)

3.1.6 证明如果算法的运行时间为(g(n))，如果其最坏运行时间为O(g(n))，最佳运行时间为(g(n))。

最坏时间O(g(n))，即Tc2g(n)；

最佳时间(g(n))，即Tc1g(n)

T(g(n))

3.1.7：证明o(g(n))(g(n))

定义

3.2 Standard notation and common functions

3.2.2 证明alogccloga bb

lgalogbclogbclga

lgclogbalgalgclgb lgalgclogbalgclgb

alogbcclogba

nnn!(2)andn!o(n) lg(n!)(nlgn)证明 3.2.3

lgn!lgilgnnlgn

i1i1nn

lgi[lgilg(ni)]lg[i(ni)]lg(

i1i1i1i1nn/2n/2n/2n1)nlgnnnlgn422

lg(n!)(nlgn)

当n>4时，i(ni)2，n!i(ni)2n,n!(2n) 2

i1n/2

n!nn,n!o(nn)

3.2.4是否多项式有界 lglgn！lgn!与

设lgn=m，

则m!)me2m()mem(lnm1)mlnm1nlnlnn ∴lgn！不是多项式有界的。 meme

mmmm2设lglgnm，m!m(2)222m1

lglgnm1，n22

lglgn!22m1m1 n lglgn是多项式有界的

3.2.5比较lg(lg*n)与lg*(lgn)

lg*(lgn)= lg*n-1

设lg*n=x，lgx

 lg*(lgn)较大。

Chapter4 Recurrences

4.1 The recursion-tree

4.1.1 证明T(n)T()1的解为O(lgn)

假设T()clg(b)clg(n/2b1) n-2b+2则T(n)clg(-b+1)+1=clg()+1=clg(n-2b+2)-clg2+1clg(n-b)2

T(n)O(lgn)

4.1.2 证明T(n)2T(n)n的解为O(nlgn)

设T(n)cnlgn

T(n)2cnlgnnclgnnn

c(n1)lg(n/2)ncnlgnclgncnncn(lgn1)nc(lgn2n)

lgn1lg(n1)，当c1/3,nc(lgn2n)

T(n)cnlg(n1),T(n)(nlgn)

T(n)O(nlgn)

4.1.3

将假设改为T(n) = cn lgn +b，只需要在T(1)=1的情况下成立。

4.1.6

计算T(n)2T1的解

令mlgn,T(2m)2T(2m/2)1

令T(n)=S(m),则S(m)2S(m/2)1

其解为S(m)(m),T(n)S(m)(lgn)

4.2 The recursion-tree method

4.2.1 T(n)(nlg3)

4.2.2 略

4.2.3 T(n)(n2)

4.2.5 T(n)(nlgn)

4.3 The master method

4.3.1 略

4.3.4 主方法是否适用方程T(n)4T(n/2)n2lgn，给出该方程解的一个上界

不适用

使用递归树方法可以求得其一个上界为O(n2lg2n)

4.3.5给出某常数a1,b1和函数f(n)，使得其满足主定理case3中除了af(n/b)cf(n)外的所有条件。

f(n)n(sinn2)，a1,b2，logba=0

sinn21,f(n)n,f(n)(nlogba)=(n)，0

af(n/b)f(n/2)n(sin(n/2)2)/2

若af(n/b)cf(n)

则n(sin(n/2)2)/2cn(sinn2)

sin(n/2)2c2(sinn2)

找不到这样的c1，总是满足上面的条件，如sinn

1时，sin(n/2)为/2，此时sin(n/2)21，所以af(n/b)cf(n)不满足。 2(sinn2)


相关内容

  • 信息技术导论复习题

    • 一.单选题,答案填在括号内. 1． 冯·诺依曼的主要贡献是( ). A.发明了微型计算机 B.设计了第一台电子计算机 C.提出了存储程序的概念 D.设计了高级程序设计语言 2．微型计算机硬件系统中最核心的部件是( ). A. 主板 B. CPU C. 内存储器 D.I/O设备 3．计算机系统必须具备 ...

  • 软件工程导论(第五版)课后习题答案

    • <软件工程导论>课后习题答案 第一章 软件工程概论 1．什么是软件危机? 软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题.这些问题表现在以下几个方面: (1)用户对开发出的软件很难满意. (2)软件产品的质量往往靠不住. (3)一般软件很难维护. (4)软件生产效率很低 ...

  • 计算机导论教学大纲

    • <计算机文化基础>课程教学大纲 课程编号:030110020 课程名称:计算机导论 课程类型:基础课 总 学 时:60 讲课学时:30 实验学时:30 学 时:60 学 分:4 适用对象:计算机专业 先修课程: 一.课程性质.目的和任务 <计算机导论>是计算机专业学生必修的公 ...

  • [转]振动相关经典书籍

    • 1  传统教材及其更新 对我国振动教学的影响影响很大的国外教材当推Timoshenko等的<工程中的振动问题>(S. Timoshenko, S. H. Young, W. Weaver. Vibration Problems in Engineering (4th ed.). John ...

  • 信息安全导论试卷参考答案

    • 信息安全导论试卷 (总分108') (答案仅供参考) 一 名词解释:(18'每个3') 信息安全:是指对信息的保密性.完整性和可用性的,可控性和不可否认性的保持,保护信息系统的硬件,软件,及相关数据,使之不应为偶然或者恶意侵犯而遭受破坏更改及泄漏,保证信息系统能够连续可靠正常的运行. VPN:一般是 ...

  • 计算机科学系[计算机科学导论]复习题1

    • 一.单项选择题(每小题1分,共30分) 1.计算机科学的奠基人是(B ) A .查尔斯·巴贝奇 B .图灵 C .阿塔诺索夫 D .冯·诺依曼 2.计算机中运算器的主要功能是(C ) A .控制计算机的运行 B .分析指令并执行 C .算术运算和逻辑运算 D .负责存取存储器中的数据 3.下面关于R ...

  • 计算机导论第3章 程序设计语言(答案)

    • 第3章 程序设计语言 习 题 一.选择题 1. A 2. A 3. D 4. A 5. AB 6. C 7.D 8.C 9.D 10. D 11.ABCD 12.B 13.A 14.ABD 二.简答题 1．简述程序的概念. 答:一个程序就是能够实现特定功能的一组指令序列的集合.或者程序＝算法+数据结 ...

  • [数据结构]教学大纲

    • <数据结构>教学大纲 Data Structure 课程编号:J6110G0003 课程性质:学科基础课程 适用专业:计算机科学与技术.网络工程.数字媒体技术 先行课:计算机科学导论.离散数学.高级语言程序设计: 后续课:无 . 学分数:5 主讲教师:任燕.王命延.冯豫华.周石林.王玮立 ...

  • 集散控制系统与现场总线试题习题及答案

    • 本答案仅供参考. 第1章 绪论 1.1 什么是过程计算机控制系统?它由哪几部分组成?通过具体示例说明. 答:它是指由被控对象.测量变送装置.计算机和执行装置构成,以实现生 产过程闭环控制的系统,它综合了计算机过程控制和生产工艺过程.例如温度控制系统. 1.2 计算机控制工业生产过程有哪些种类型? 答 ...

热门内容

标签

德育工作总结   高一自我鉴定范文   工厂车间辞职信范文   大学生团员小结范文   研究方案范文   技术员工作计划范文   试验员实习总结范文   合同遗失证明范文   电大自我鉴定范文 毕业生   竞聘报告优秀范文   安全应急预案范文   婚礼上嘉宾代表讲话