【每日一博】算法小论——第三章 又把新桃换旧符

笔记

这一章主要是渐进记号和高中数学的回忆。

几个标记：

1. Θ – 上界和下界，绑定值，相当于f(n) ∈ [c1 * g(n), c2 * g(n)]
2. Ω – 闭区间下界，最好运行时间，相当于 f(n) ∈ [c * g(n), ∞)
3. ω – 开区间下界，最好运行时间，相当于 f(n) ∈ (c * g(n), ∞)
4. Ο – 闭区间上界，最差运行时间，相当于 f(n) ∈ [0, c * g(n)]
5. ο – 开区间上界，最差运行时间，相当于 f(n) ∈ [0, c * g(n))

其余部分，高中数学的内容都有，就不抄啦。

那么，数学对于算法导论的意义是什么？大家都怕数学，我也怕数学，觉得这个东西简直是摧残我智商方面的自信……不过呢，想要在理工科这个领域里面混，数学又是必须面对的。

陈皓(微博 @左耳朵耗子)有一篇博文， 软件开发的“三重门” ，里面讲程序员的3个阶段，业务功能、业务性能、业务智能，目前我还是停留在第1,2个阶段，如果我们想往第3个阶段前行，数学是个基本功。

当年我在学习物理的时候，老师在上课的时候教导我们，物理学家不需要像数学家那样严谨的学习推导数学，而是要把数学学活，创造性的用在物理领域。目标在于培养一种对于数学公式和自然现象相关性的直觉，由此洞察世界真相，变身高富帅，赢取白富美……就像杨振宁那样82还能娶28……哈哈哈，后面半句是我瞎编的。算法中的数学，也是这样吧。

习题答案

3.1-1

Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Θ-notation, prove that max(f(n), g(n)) = Θ(f(n) + g(n)).

一开始，我觉得这是显而易见的简单证明，结果看起来有点麻烦……

for n > n1, c1 * k(n) <= f(n) <= c2 * k(n), f(n) = Θ(k(n)) for n > n2, c3 * l(n) <= g(n) <= c4 * l(n), g(n) = Θ(l(n))  for n > max(n1, n2), max(f(n), g(n)) <= f(n) + g(n) <= c2 * k(n) + c4 * l(n) 

到这里，证明 max(f(n),g(n)) = O(f(n) + g(n)) 好像已经差不多了，但是对于证明Ω(下界)还不够。不过，也是可以变通的。

max(f(n),g(n) >= 1/2 * f(n) + 1/2 * g(n) 

这个不等式的好处在于，在任何一点n上，如果

f(n) > g(n)  

则

max(f(n),g(n)) = f(n) = 1/2 * f(n) + 1/2 f(n) > 1/2 * f(n) + 1/2 * g(n)  

由于对称性，上面的不等式在 g(n) > f(n) 的时候也成立，于是，哈哈哈，Ω(下界)也证明了。

for n > max(n1, n2), max(f(n), g(n)) > 1/2(c1 * k(n) + c3 * l(n)) 

充分利用max的性质，是我解决这个小问题的关键……智商不足时间补啊……

3.1-2

Show that for any real constants a and b, where b > 0,

(n + a)^b = Θ(n^b) 

额，这个证明么。。其实挺无聊的。。二项式展开，然后用最高次方才有用的性质来走。。就把问题平推了吧。。

哦，这里a和b是实数，不过我猜有理数和实数不影响这个结论，没办法，哈哈，作为物理学家，我们只有在有力气的时候才去追求数学上严谨性，能偷懒就偷懒了。

3.1-3

Explain why the statement, “The running time of algorithm A is at least O(n^2)” is meaningless.

这其实是一道GRE阅读理解题。

at least，意思就是最小，最少， >=

O(n^2), 意思就是<=，最大，最多

两者自相矛盾，所以是胡扯。这句话的意思堪比：

据我一位不愿意透露姓名的朋友唐马儒先生说，他是一个鉴黄师……

3.1-4

Is 2 ^{(n+1) = O(2} n)? is 2 ^{2n = O(2} n)?

前一个， 2^(n+1) = 2 * 2^n = O(2^n) ，所以成立

后一个，n是变量， 2^2n = 2^n * 2^n ，所以不成立

3.1-5

Prove Theorem 3.1.

Theorem 3.1

For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

这个就是拿着定义凑一下的事儿，不干，嘿嘿。

3.1-7

Prove that o(g(n)) and ω(g(n)) is the empty set.

同上，不干。

3.1-8

We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n,m), we denote by O(g(n,m) the set of functions

O(g(n,m)) = { f(n,m) :  there exist positive constants c, n0, and m0  such that  0 <= f(n,m) <= cg(n,m)  for all n >= n0 or m >= m0 } 

Give corresponding definitions for Ω(g(n,m)) and Θ(g(n, m)).

继续同上，没意思的活儿不干。也许在某些情况下需要双自变量的情况下用的上。

3.2-1

Show that if f(n) and g(n) are monotonically increasing functions, then so are the functions f(n) +(g(n) and f(g(n)) ,and if f(n) and g(n) are in addition nonnegative, then f(n)·g(n) is monotonically increasing.

高中数学题，或许是初中数学题？

3.2-2

Prove equation (3.16).

a^logb(c) = c^ logb(a)          3.16 

go on

3.2-3

Prove equation (3.19). Also prove that n! = ω(2^n) and n! = o(n^n)

lg(n!) = Θ(nlgn)                3.19 

这个式子对我来说有难度

lg(n!) < lg(n^n) = nlgn 

上界好证，那么下界呢？

lg(n!) = lg(n*(n-1)...1) = lgn + lg(n-1) + lg(n-2) ... lg1 

哦，提示里面说要用那个什么斯特林近似。

n! = √(2πn) (n/e)^n (1 + Θ(1/n)) lg(n!) = lg√(2πn) + nlg(n/e) + lg(1+Θ(1/n))        = (1/2)lg(2πn) + n(lgn - lge) + lg(1+c/n))        = Θ(lgn) + Θ(nlgn) + lg(n+c) - lgn        = Θ(nlgn) 

好吧，靠着斯特林大神的庇佑，终于很容易的证明了这个式子，不过斯特林是怎么想到这个近似的呢？暂时不去想了……数学真神奇啊。

OK，继续证明另外两个式子.

n! = n(n-1)...2*1 

当 n > 某个数字时，我猜

n(n-1)..2*1 > 2...2 (n个2） 

因为双方的数目都是n个，对于前面n项左边都大于右边，只有最后一项1<2，所以，找一项对冲一下

(n-1)...2 > 2..2 (n-2个2) n*1 > 2*2 (剩下2个2) 

也就是说当 n > 4的时候上面两个不等式都成立，此时

n! > 2^n n! = ω(2^n) 

OK，继续证明最后一个式子

n! < n^n n(n-1)...2*1 < n...n n! = o(n^n) 

两边都是n个，左边小于右边，得证。

3.2-4 *

Is the function 「lgn]! polynomially bounded? Is the function 「lg lgn]! polynomially bounded?

对于第一个问题，我先试探一下，假设

n = 32, lgn = 5, 5! = 120 n = 16, lgn = 4, 4! = 30 n = 8,  lgn = 3, 3! = 6 

这里n以2^k的速度变大时，「lgn]!以k!的速度变大，那么哪一个变得更快？这两者之间的差值是多少？

由上面那个习题3.2-3可以知道， k! = ω(2^k) ，k!增长的更快，这也从我上面的试探中可以看出来，同时，k!比2^k大了不止一个多项式的差距，所以我大胆猜测，「lgn]!不是多项式增长的。具体的证明留给数学家，wahaha。

那么问题更推一步 「lg lgn]!呢，就是2 ² k和k!之间的比较。

k = 1, 2^2^k = 4,   k! = 1 k = 2, 2^2^k = 16,  k! = 2 k = 3, 2^2^k = 256, k! = 6 k = 4, 2^2^k = 65536, k! = 24 

也就是说，2 ² k的增长速度远远大于k!的增长速度，反过来说，对「lg lgn]! 而言，n以线性增加时，「lg lgn]! 在数轴上会小于n，最后趋向于0，所以我猜测

「lg lgn]! = Θ(1) 

3.2-5 *

Which is asymptotically larger: lg(lg * n) or lg * (lgn) ?

其实，我不懂这个*号到底是谁神马意思？先空着。哦，回头去看课本，这个高中没教过。

n = 16 lg * n = 3 lg(lg * n) = lg3 lg * (lg 16) = lg * 4  = 2 lg 3 < 2, 所以看起来后面那个大一点，换个数字 n = 65536 lg * n = 4 lg(lg * n) = 2 lg * (lg 65536) = lg * (16)     = 3  

好了，经过两次的猜测，基本就能看出来后面那个大了。

3.2-6

Show that the golden ratio φ and its conjugate φ' both satisfy the equation

x^2 = x + 1 

黄金分割比的定义吧，二次方程的解法，初中数学跳过。

3.2-7

Prove by induction that the ith Fibonacci number satisfies the equality

F[i] = (φ^i -  φ'^i) / √5 

where φ is the golden ratio and φ' is its conjugate.

好吧，继续归纳法，显然

F[0] = 0 F[1] = 1 

假设

F[i-1] = (φ^(i-1) - φ'^(i-1)) / √5 F[i-2] = (φ^(i-2) - φ'^(i-2)) / √5 

则

F[i] = F[i-1] + F[i-2]      = (φ^(i-1) + φ^(i-2) - φ'^(i-1) - φ'^(i-2)) / √5      = (φ^(i-2)(φ + 1) - φ'^(i-2)(φ' + 1)) / √5 

凑一下

φ + 1 = (3 + √5) / 2 φ^2   = (1 + 2√5 + 5) / 4 = (3 + √5) / 2 φ + 1 = φ^2  φ'+ 1 = φ'^2 //同理 

代入后，得到

F[i] = (φ^i -  φ'^i) / √5 

得证。

关于斐波那契数列，在TED上有一个精彩的演讲，抨击教育制度的，不妨一看

神奇的斐波那契数列

我一直没搞明白为什么这个数列和黄金分割有关，至少没看出深刻的联系，由公式能看出不少东西，但还是缺乏直观的理解。

3.2-8

Show that klnk = Θ(n) implies k = Θ(n/lnn).

klnk = Θ(n) = n n / lnn = klnk /(ln(klnk))         = klnk / (lnk + lnlnk)         < klnk / lnk (当k足够大之后，lnlnk > 0的情况下) 

这样，大致就可以看出k的渐进时间了，当然是很粗糙的证明，中间还有常数不等式都没考虑。这个题目的意义在于，对于渐进时间，不但有函数的上界、下界、传导性、交换律、对称性这些特性，还有反函数的特性，在某些领域可能用的上。

问题答案

3-1 Asymptotic behavior of polynomials

Let

p(n) = ∑a[i]n^i (i = 0 to d) 

where a[d] > 0, be a degree-dpolynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.

a. if k >= d, then p(n) = O(n^k). b. if k <= d, then p(n) = Ω(n^k). c. if k  = d, then p(n) = Θ(n^k). d. if k  > d, then p(n) = ο(n^k). f. if k  < d, then p(n) = ω(n^k). 

哈哈哈无聊的问题我就不证了吧

3-2 Relative asymptotic growths

Indicate, for each pair of expressions（A, B) in the table below, whether A is O, o, Ω, ω or Θ of B. Assume that k >= 1, ∈ > 0, and c > 1 are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.

    A           B           O   o   Ω   ω   Θ a.  (lgn)^k     n^∈         √   √   ×   ×   × b.  n^k         c^n         √   √   ×   ×   × c.  √n          n^(sin n)   ×   ×   √   √   × d.  2^n         2^(n/2)     ×   ×   √   √   × e.  n^(lgc)     c^(lgn)     ×   ×   ×   ×   √ f.  lg(n!)      lg(n^n)     ×   ×   ×   ×   √ 

a. 如果k=2，∈=1，我测算了一下是(lgn)^2=o(n)，回头继续看课本（课本就是用来回头的哈哈哈），书上有这样的式子：

(lgn)^b = o(n^a) 

b.同样的

n^b = o(a^n) 

c. sin n <= 1, >= -1 , 而 √n 可以一直增长，所以 √n 是赢家。

d. 2^n = 2^(n/2) * 2^(n/2) ，2^n要大很多，比较牛逼。

e. 这两个式子其实是一样的！只是伪造不在场证明而已！真相只有一个！哈哈哈……

f. 这其实也是个改头换面， lg(n^n) = nlgn ，

lg(n!) = Θ(nlgn)                3.19 

所以两者还是一样地，就是拐了个弯的一样。

这题其实有助于帮我们建立一些直觉，例如指数函数比幂函数快，对数的n次方还是没有幂函数快，等等

3-3 Ordering by asymptotic growth rates

a. Rank the following functions by order of growth; that is, find an arrangement g1, g2,…,g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), …, g29 = Ω(g30). Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).

lg(lg*n)    2^(lg*n)    (√2)^(lgn)  n^2         n!      (lgn)! (3/2)^n     n^3         (lgn)^2     lg(n!)      2^2^n   n^(1/lgn) lnlnn       lg*n        n*2^n       n^lglgn     lnn     1 2^lgn       (lgn)^lgn   e^n         4^lgn       (n+1)!  (√lgn) lg*(lgn)    2^(√2lgn)   n           2^n         nlgn    2^(2^(n+1)) 

这里继续是苦力活啊……抄了半天题目，好像对齐还成问题？不多说，这种题目的解决方案是先立标杆，分类，从高阶到低阶的直接分类为：

指数之指数   2^2^n,2^(2^(n+1)) 阶乘      n!,(n+1)! 指数函数    (3/2)^n,2^n,e^n 幂函数     n,n^2,n^3 对数函数    lnn,(lgn)^2 多重对数    lg(lg*n),lg*(lgn) == lg*n 常数      1 

注，根据定义，多重对数少取一次的意思在于

lg*(lgn) = (lg*n) - 1 => lg*(lgn) = Θ(lg*n) //这些符号太啰嗦，后面我就用等号大于号小于号之类了的:-) 

接下来的工作就是把剩下的这些插进去，看位于哪里合适，一个一个看

1. 2^(lg*n)

2^(lg*n) < 2^(lgn) = n^(lg2) = n 

那么这个比幂函数小，那么是否比对数函数也小呢？

n = 16 lg * n = 3 2^3 = 8 lg n = lg16 = 4 

所以，合理的推测是，比一般的多重对数大，但是小于对数函数

对数函数    lnn,(lgn)^2 ----        2^(lg*n) 多重对数    lg(lg*n),lg*(lgn),lg*n 

2. (√2)^(lgn)

(√2)^(lgn) = n ^ lg(√2) = n ^ (1/2) = √n 

插入幂函数最小的档次

幂函数     (√2)^(lgn),n,n^2,n^3 

3. (lgn)!

(lgn)! < n!  n = 16 (lgn)! = 4! = 24 2^16 >> 24 (lgn)! < 2^n 16^2 = 256 >>24 (lgn)! < n^2  n = 32 (lgn)! = 5! = 120 n^2 = 1024 而显然 (lgn)! > (lgn)^2 

插入对数函数的最后

对数函数    lnn,(lgn)^2,(lgn)! 

4. lg(n!)

lg(n!) 

根据习题3.2-3

lg(n!) = nlgn 

位于幂函数中间

幂函数     (√2)^(lgn),n,nlgn == lg(n!),n^2,n^3 

太长了重新抄一遍

指数之指数   2^2^n,2^(2^(n+1)) 阶乘      n!,(n+1)! 指数函数    (3/2)^n,2^n,e^n 幂函数     (√2)^(lgn) == √n 见【2】,n,nlgn == lg(n!) 见【4】,n^2,n^3 对数函数    lnn,(lgn)^2,(lgn)! 见【3】 ----        2^(lg*n) 见【1】 多重对数    lg(lg*n),lg*(lgn) == lg*n 常数      1 

剩下需要插入的有

n^(1/lgn), lnlnn, n*2^n, n^lglgn, 2^lgn,  (lgn)^lgn, 4^lgn, (√lgn), 2^(√2lgn) 

5. n^(1/lgn)

继续

常数      1 < n^(1/2) (当 n > 4时) n = 16 n^(1/lgn) = 16^(1/4) = 2 lg16 = 4 n^(1/lgn) < lgn n = 64 n^(1/lgn) = 64^(1/6) = 2 

猜测

n^(1/lgn) = 2 n^(1/lgn) = n^(logn 2) = 2 

所以

常数      1, n^(1/lgn) == 2 

6. lnlnn

lnlnn < lnn 但猜测 lnlnn > 2^(lg*n) 对数函数    lnn,(lgn)^2,(lgn)! ----        lnlnn ----        2^(lg*n) 

7. n*2^n

n*2^n > 2^n e^n = (2.71)^n = 2^n * (1.x)^n > 2^n * n 

插入

指数函数    (3/2)^n,2^n,n*2^n,e^n 

8. n^lglgn

n^lglgn < n^(lgn) n^lglgn > n^3 (当n足够大) 那么和2^n比较呢？  n = 8 n^(lglgn) = 8^lg3 = (2^3)lg3 = (2^lg3)^3 = 3^3 = 81 2^8 = 256 

猜测

指数函数    (3/2)^n,2^n,e^n ----        n^lglgn 幂函数     (√2)^(lgn) == √n,n,nlgn == lg(n!),n^2,n^3 

9. 2 ^{lgn, 4} lgn

2^lgn = n 4^lgn = n^2 幂函数     (√2)^(lgn) == √n,2^lgn == n,nlgn == lg(n!),n^2 == 4^lgn,n^3 

10. (lgn)^lgn

(lgn)^lgn = n^(lglgn) 

11. (√lgn)

(√lgn) < lnn 对数函数    (√lgn),lnn,(lgn)^2,(lgn)! 

12. 2^(√(2lgn))

2^(√(2lgn)) = (2^lgn)^(√(2/lgn)) = n^(√(2/lgn)) 当n变大时，指数其实无限趋向于0，总之比0.5要小，所以排名在幂函数里面最小 幂函数     2^(√2lgn),(√2)^(lgn) == √n,n,nlgn == lg(n!),n^2,n^3 

所以，最后的总排名是！

指数之指数 2^(2^(n+1)) 2^2^n  阶乘 (n+1)! n!  指数函数 e^n n*2^n                   见【7】 2^n (3/2)^n  --无名函数-- n^lglgn == (lgn)^lgn    见【8】 见【10】  幂函数 n^3 n^2 == 4^lgn            见【9】 nlgn == lg(n!)          见【4】 2^lgn == n              见【9】 (√2)^(lgn) == √n        见【2】 2^(√2lgn)               见【12】  对数函数 (lgn)!                  见【3】【错，详见后】 (lgn)^2 lnn (√lgn)                  见【11】  --无名函数-- lnlnn                   见【6】 2^(lg*n)                见【1】  多重对数 lg*(lgn) == lg*n lg(lg*n)  常数 n^(1/lgn) == 2          见【5】 1 

累死，一个晚上就这么一题搞完了，回头再去对答案～～

经过对答案后，我发现有个小小的问题，就是对于

(lgn)! 

我判断错了，答案中的说法是

(lgn)! > n^3 

理由是对双方一起取对数

lg(x!) = xlgx (习题3.2-3) lg((lgn)!) = lgn * lg(lgn) 

然后试着对n^3取对数

lg(n^3) = 3lgn 

于是，这下就是

lgn * lglg(n)  vs  3lgn 

可以看出双方都有lgn的因子，但是lglg(n) » 3，于是左方胜利！可以说，这是出乎我的意料的，我前面通过手工穷举法做了错误的判断，在这里用精妙的数学做了无懈可击的推到 -_- ，那么，我能从中学到什么呢？在真实的情况下我能依赖于手工的穷举吗？对于一个数学笨蛋来说，只有2种方法可以搞定

1. 用计算机模拟，把这2个函数真的画图搞出来
2. 找个数学专家，把我不确定的地方和他聊，请他帮我解决

b. Give an example of a single nonnegative function f(n) such that for all functions gi(n) in part (a), f(n) is neither O(g(n)) nor Ω(g(n)).

上面的这些函数基本上填满了数轴，如果要找出一个函数既不是O也不是Ω，就需要找一个震荡的很厉害的函数，例如

2^(2^(2^n)) * | sin n | 

首先这个函数在最大的时候比指数之指数还要大，但是最小的时候可以是0。

3-4 Asymptotic notation properties

Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

a. f(n) = O(g(n)) implies g(n) = O(f(n)).

错，f(n) <= g(n) 不代表 g(n) <= f(n)

b. f(n) + g(n) = Θ(min(f(n),g(n)))

粗一看这题好像和3.1-1差不多，但max和min的性质不一样，我套了一下max的证明发现不成立。反过来想，假设

g(n) = n^2, f(n) = n 则 f(n) + g(n) = n^2 + n = Θ(n^2) min(f(n), g(n)) = n = Θ(n） 

于是，不成立

c. f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), where lg(g(n)) >= 1 and f(n) >= 1 for all sufficiently large n.

成立，因为lg是个单调递增函数，a

f(n) <= g(n) (当n大于某一常数时) 则 lg(f(n)) <= f(g(n)) f(n) > 1保证了lg(f(n)) > 0 ，满足了本章所有函数都非负的初始条件。 

d. f(n) = O(g(n)) implies 2 ^{(f(n)) = O(2} g(n)).

同上也成立，由于指数函数都是正的，所以不需要额外的条件

e. f(n) = O((f(n))^2).

不成立，如果f(n) < 1，约平方越小，所以不能这么写。

f. f(n) = O(g(n)) implies g(n) = Ω(g(n))

按照定义成立

g. f(n) = Θ(f(n/2))

不成立，f(n/2)就是把f(n)在x轴上横向拉长一倍，对于多项式函数来说是成立的，n/2不影响最高次方的数，但对于指数函数例如2^n这样的，就不行。

f(n) = 2^n f(n/2) = 2^(n/2) 

显然f(n/2)和f(n)不在同一个班次上啊

h. f(n) + o(f(n)) = Θ(f(n))

成立，

f(n) + o(f(n)) >= f(n) f(n) + o(f(n)) <= 2f(n) 

得证

3-5 Variations on O and Ω

Some authors define in a slightly different way than we do; let’s use Ω∞ (read “omega infinity”) for this alternative definition. We say that f(n) = Ω∞( g(n) ) if there exists a positive constant c such that f(n) > cg(n) for infinitely many integers n.

* a. Show that for any two functions f(n) and g(n) that are asymptotically nonnegative, either f(n) = O(g(n)) or f(n) == Ω∞( g(n) ) or both, where as this is not true if we use Ω in place of Ω∞ *

首先O和Ω是互相排斥的，不可能both。其次这个Ω∞有啥好处能够兼容呢？对于both这种情况我很难想象

存在c1, f(n) <= c1 g(n), n > n0 存在c2, f(n) > c2 g(n), n 有无穷个 

b. Describe the potential advantages and disadvantages of using Ω∞ instead of Ω∞ to characterize the running times of programs.

目前还没看出有无穷个n的好处，因为无穷个不等于所有大于n0的，这样不能保证f(n)的性质，例如 sin(n) + 1 = Ω∞(1), 因为sin(n)在1和-1间波动，这题看不出妙处，先跳过。

Some authors also define O in a slightly different manner; let’s use O’ for the alternative definition. We say that f(n) = O’(g(n)) if and only if |f(n)| = O(g(n))

c. What happens to each direction of the “if and only if” in Theorem 3.1 if we substitute O’ for O but still use Ω ?

Theorem 3.1 For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) =  O(g(n)) and f(n) =  Ω(g(n)). 

这题我就更加看不懂了，出来了绝对值，而本章讨论的都是大于0的函数。。。继续跳过

d问题不抄也罢，另一个脱离前提的设定

3-6 Iterated functions

* We can apply the iteration operator * used in the lg * function to any monotonically increasing function f(n) over the reals. For a given constant c ∈ R, we define the iterated function f.c. by**

f.c.*(n) =  min{ i >=0,   f(i)(n) <= c } 

* which need not be well defined in all cases. In other words, the quantity f.c. is the number of iterated applications of the function f required to reduce its argument down to c or less.**

For each of the following functions f(n) and constants c, give as tight a bound as possible on f.c.

首先题目中的f.c.*(n)也是一个n的函数，所以需要一个tight bound来表示

   f(n)    |    c     |   f.c.*(n) a. n - 1   |    0     |   n 

a是显然的

b. lgn     |    1     |   lg * n   

b就有点困难了，你用什么函数来表示需要递归lg几次到1呢？这个无法直接表达,只能用书里面的lg * n

c. n/2     |    1     |   lgn 

c还是比较明确的，需要除几次2, 也就是2的几次方能到n，验证下n = 2, i = 1，符合搞定

d. n/2     |    2     |   lgn - 1 

少除一次，继续通过验证得出

e.√n       |    2     | 

这个不会，开方开几次小于2？好像没什么规律，后面的也无法做出来，就放一放吧……