算法导论习题答案Solutions.for.Introduction.to.algorithms

算法导论

需积分: 32 155 浏览量更新于2023-03-16 评论收藏 257KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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页未读，继续阅读

YZYLOVEYZY

粉丝: 0
资源: 6

会员权益专享

算法导论习题答案Solutions.for.Introduction.to.algorithms

评论0

会员权益专享

最新资源

算法导论习题答案Solutions.for.Introduction.to.algorithms

评论0

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

算法导论中文版

算法导论第四版 英文

introduction to algorithms. mit press, 2001.

introduction to algorithms 3rd

clrs算法导论pdf

introduction to algorithms pdf

introduction to algorithms - hardcover edition

报错：ModuleNotFoundError: No module named 'pymoo.algorithms.moo.sms'

ModuleNotFoundError: No module named 'torch.distributed.algorithms.join

module 'ray.rllib.algorithms.ppo' has no attribute 'DEFAULT_CONFIG'

最短路径dijkstra算法参考文献

ModuleNotFoundError: No module named 'torch.distributed.algorithms.join'

introduction to algorithms 4th

AttributeError: module 'networkx.algorithms.community' has no attribute 'infomap'

introduction to algorithms, 3rd edition, the mit press 2009 pdf

introduction to the design and analysis of algorithms答案

算法书值得推荐的有哪些

数据结构和算法的推荐书籍和视频

No module named 'pymoo.algorithms.nsga2'

会员权益专享

最新资源

算法导论第四版英文