算法导论第三版 第三章 思考题 3-6

              第三章 感想：第三章主要讲的是数学知识，跟高数差不多，找到一个算法导论答案的网址跟大家分享一下，里边答案基本上挺准的，也在豆瓣上看到一些前辈写的读书笔记，很受启发。 算导答案：http://clrs.skanev.com/

              感觉思考题3-6没有写过程，把我的解题过程写上来吧。

f(n)	c	f∗c(n)
n−1	0	Θ(n)
lgn	1	Θ(lg∗n)
n/2	1	Θ(lgn)
n/2	2	Θ(lgn)
n√	2	Θ(lglgn)
n√	1	does not converge
n1/3	2	Θ(log3lgn)
n/lgn	2	ω(lglgn),o(lgn)

1. 1 ，f（n）=n-1。每次运算都减1很容易理解界 是Θ（n）。

   2，f（n）=lgn。这个答案给的相当于没给，因为lg*n的定义就是不断计算lgn使输出小于等于1所计算的次数。

   3，f（n）=n/2. 每回都除以2。 n/ 2ⁱ <=1, 推出2ⁱ <=n，同时取对数，i=lgn 。

   4，理解过程同上。

   5，f（n）=. 每次都开根号，相当于  ((n )^1/2)^1/2….<=2,也就是n的1/2ⁱ 次方小于等于2，

      两边同时取2为底的对数得 lgn<=2ⁱ,最后得再取2为底对数，得 lg(lgn)<=i.

   6, 因为 运算无穷次才小于 一，所以次数i等于无穷，也就是不收敛。

   7，f（n）=  每次都开3，相当于((n)^1/3)^1/3….<=2,也就是n的1/3ⁱ 次方小于等于2，

   两边同时取2为底的对数得 lgn<=2ⁱ,最后得再取3为底对数，得 lg₃(lgn)<=i.

   8 ，答案给出了上界 和下界 ，上界容易理解 n很大时lgn>2,所以用的次数小于f(n)=n/2,所用的次数，下界我不知道该怎样去理解了

2.