算法导论答案第二版英文版资源-CSDN文库

算法导论答案

3星 · 超过75%的资源需积分: 10 112 浏览量 2013-01-06 13:19:04 上传评论收藏 266KB PDF 举报

资源推荐

资源详情

资源评论

Solutions for Introduction to algorithms

second edition

Philip Bille

The author of this document takes absolutely no responsibility for the contents. This is merely

a vague suggestion to a solution to some of the exercises posed in the book Introduction to algo-

rithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the

solutions are wrong. If you have found an error, have a better solution or wish to contribute in

some constructive way please send a message to beetle@it.dk.

It is important that you try hard to solve the exercises on your own. Use this document only as

a last resort or to check if your instructor got it all wrong.

Please note that the document is under construction and is updated only sporadically. Have

fun with your algorithms.

Best regards,

Philip Bille

Last update: December 9, 2002

3.1 − 1

Let f(n), g(n) be asymptotically nonnegative. Show that max(f(n), g(n)) = Θ(f(n) + g(n)). This

means that there exists positive constants c

, c

and n

such that,

0 6 c

(f(n) + g(n)) 6 max(f(n), g(n)) 6 c

(f(n) + g(n))

for all n > n

Selecting c

= 1 clearly shows the third inequality since the maximum must be smaller than

the sum. c

should be selected as 1/2 since the maximum is always greater than the weighted

average of f(n) and g(n). Note the signiﬁcance of the “asymptotically nonnegative” assumption.

The ﬁrst inequality could not be satisﬁed otherwise.

3.1 − 4

n+1

= O(2

) since 2

n+1

= 2 · 2

6 2 · 2

! However 2

is not O(2

): by deﬁnition we have

= (2

)

which for no constant c asymptotically may be less than or equal to c ·2

3 − 4

Let f(n) and g(n) be asymptotically positive functions.

a. No, f(n) = O(g(n)) does not imply g(n) = O(f(n)). Clearly, n = O(n

) but n

6= O(n).

b. No, f(n) + g(n) is not Θ(min(f(n), g(n))). As an example notice that n + 1 6= Θ(min(n, 1)) =

Θ(1).

c. Yes, if f(n) = O(g(n)) then lg(f(n)) = O(lg(g(n))) provided that f(n) > 1 and lg(g(n)) > 1

are greater than or equal 1. We have that:

f(n) 6 cg(n) ⇒lg f(n) 6 lg(cg(n)) = lg c + lg g(n)

To show that this is smaller than b lg g(n) for some constant b we set lg c + lg g(n) = b lg g(n).

Dividing by lg g(n) yields:

b =

lg(c) + lg g(n)

lg g(n)

lg c

lg g(n)

+ 1 6 lg c + 1

The last inequality holds since lg g(n) > 1.

d. No, f(n) = O(g(n)) does not imply 2

f(n)

= O(2

g(n)

). If f(n) = 2n and g(n) = n we have that

2n 6 2 · n but not 2

6 c2

for any constant c by exercise 3.1 − 4.

e. Yes and no, if f(n) < 1 for large n then f(n)

< f(n) and the upper bound will not hold.

Otherwise f(n) > 1 and the statement is trivially true.

f. Yes, f(n) = O(g(n)) implies g(n) = Ω(f(n)). We have f(n) 6 cg(n) for positive c and thus

1/c · f(n) 6 g(n).

g. No, clearly 2

66 c2

n/2

= c

√

for any constant c if n is sufﬁciently large.

h. By a small modiﬁcation to exercise 3.1−1 we have that f(n)+o(f(n)) = Θ(max(f(n), o(f(n)))) =

Θ(f(n)).

剩余50页未读，继续阅读

评论收藏

内容反馈

sinat_21436217

2014-10-23

答案还可以，顶

Jake443403168

粉丝: 47
资源: 395

算法导论答案 第二版 英文版

算法导论 答案 第二版 算法

《算法导论(第二版)》(中文版)课后答案.pdf

算法导论第二版答案 算法导论第二版答案 算法导论第二版答案

算法导论第二版课后答案完全版

算法导论第二版课后答案完全版（中英文）

算法导论第二版课后答案中文完全版

算法导论第二版＋习题答案 part2

算法导论及答案（第二版，英文版）

算法导论（第二版）答案

算法导论答案（第二版英文答案）

《算法导论(第二版)》(中文版)课后答案

算法导论第二版(英文原版+习题答案)

算法导论第二版答案

算法导论 第二版答案

《算法导论》第二版习题中英文答案整理版

算法导论中文版第二版（书+课后习题答案）

算法导论第二版习题答案（英文版）

算法导论第二版课后习题答案完全版中英文

算法导论(第二版)》(中文版)课后答案

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

最新资源

算法导论答案第二版英文版

算法导论答案第二版算法

算法导论第二版答案算法导论第二版答案算法导论第二版答案

算法导论第二版答案

Qt 5实现串口调试助手（源工程文件、0积分下载）