算法设计与分析C++语言描述陈慧南版课后答案.pdf
版权申诉
72 浏览量
2022-10-29
22:50:25
上传
评论
收藏 512KB PDF 举报
第 一 章
P
15
1-3. 最大公约数为 1。快 1414 倍。
主要考虑循环次数，程序1-2 的 while循环体做了10次，程序1-3的 while循环体做了14141次（14142-2
循环）
若考虑其他语句，则没有这么多，可能就 601 倍。
第二章
P
32
2-8.（1）画线语句的执行次数为
（2）画线语句的执行次数为
n i
logn
。
(log n)
。划线语句的执行次数应该理解为一格整体。
j
1
i1 j1 k1
n(n 1)(n 2)
3
。
(n )
。
6
（3）画线语句的执行次数为
n
。
( n )
。
（4）当 n 为奇数时画线语句的执行次数为
(n 1)(n 3)
，
4
(n 2)
2
2
当 n 为偶数时画线语句的执行次数为 。
(n )
。
4
2-10. （ 1 ） 当
n 1
时 ，
5n
2
8n 2 5n
2
， 所 以 ， 可 选
c 5
，
n
0
1
。 对 于
n n
0
，
f (n) 5n
2
8n 2 5n
2
，所以，
5n
2
8n 2 (n
2
)
。
（2） 当
n 8
时，
5n
2
8n 2 5n
2
n
2
2 4n
2
，所以，可选
c 4
，
n
0
8
。对于
n n
0
，
f (n) 5n
2
8n 2 4n
2
，所以，
5n
2
8n 2 (n
2
)
。
2 2 2
（3） 由（1）、（2）可知，取
c
1
4
，
c
2
5
，
n
0
8
，当
n n
0
时，有
c
1
n 5n 8n 2 c
2
n
，所
以
5n 8n 2 (n )
。
2-11. (1) 当
n 3
时，
log n n log n
，所以
f (n) 20n log n 21n
，
g(n) n log n 2n
。可
3 3
2 2
选
c
21
，
n
0
3
。对于
n n
0
，
f (n) cg(n)
，即
f (n) (g(n))
。注意：是
f
(
n
)和
g
(
n
)的关系。
2
剩余15页未读，继续阅读
资源评论
