algorithm design 的课后答案.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.43M 资料格式：pdf 举报版权申诉

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第1页.png

第1页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第2页.png

第2页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第3页.png

第3页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第4页.png

第4页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第5页.png

第5页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第6页.png

第6页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第7页.png

第7页 / 共111页

e4eb7d24-3d4d-4c52-9160-40f1a08951d0.pdf-第8页.png

第8页 / 共111页

文本预览

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.7 The numbers in the ﬁrst row are quite large. The table below calculates it approxi- mately in powers of 10. People might also choose to use powers of 2. Being close to the answer is enough for the big numbers (within a few factors of 10 from the answers shown). 2106 1 Second ≈ 10300000 ≈ 1012 106 ≈ 105 1000 100 19 9 log n √n n n logn n2 n3 2n n! 1 Hour 23.6×109 ≈ 10109 ≈ 1.3× 1019 3.6× 109 ≈ 109 6× 104 ≈ 1500 31 22.6×1012 1 Month ≈ 100.8×1012 ≈ 6.8× 1024 ≈ 2.6× 1012 ≈ 1011 ≈ 1.6× 106 ≈ 14000 41 1 Century 23.1×1015 ≈ 101015 ≈ 9.7× 1030 ≈ 3.12× 1015 ≈ 1014 ≈ 5.6× 107 ≈ 1500000 51 12 15 17

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.10 The Loop1 method runs in O(n) time.

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.11 The Loop2 method runs in O(n) time.

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.12 The Loop3 method runs in O(n2) time.

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.13 The Loop4 method runs in O(n2) time.

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.19 By the deﬁnition of big-Oh, we need to ﬁnd a real constant c > 0 and an integer constant n0 ≥ 1 such that (n + 1)5 ≤ c(n5) for every integer n ≥ n0. Since (n + 1)5 = n5 +5n4 +10n3 +10n2 +5n +1, (n +1)5 ≤ c(n5) for c = 8 and n ≥ n0 = 2.

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise R-1.23 By the deﬁnition of big-Omega, we need to ﬁnd a real constant c > 0 and an integer constant n0 ≥ 1 such that n3 logn ≥ cn3 for n ≥ n0. Choosing c = 1 and n0 = 2, shows n3 logn ≥ cn3 for n ≥ n0, since logn >≥ 1 in this range.

Algorithm Design M. T. Goodrich and R. Tamassia John Wiley & Sons Solution of Exercise C-1.7 To say that Al’s algorithm is “big-oh” of Bill’s algorithm implies that Al’s algo- rithm will run faster than Bill’s for all input greater than somenon-zero positive integer n0. In this case, n0 = 100.

分享到：

赞收藏

资料库

algorithm design 的课后答案.pdf

相关推荐

课程资源

热门标签

最新资料