难易

# 笔记

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-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) >= 1/2 * f(n) + 1/2 * g(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)
``````

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

## 3.1-2

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

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

## 3.1-3

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

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

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

## 3.1-4

Is 2^(n+1) = O(2^n)? is 2^2n = O(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-1)..2*1 > 2...2 (n个2）
``````

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

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

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

``````n! < n^n
n(n-1)...2*1 < n...n
n! = o(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
``````

``````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
``````

``````「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
``````

## 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的情况下)
``````

# 问题答案

## 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
``````

## 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))

``````

``````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)

``````

####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!)
``````

``````lg(n!) = nlgn
``````

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

####太长了重新抄一遍

``````指数之指数	2^2^n,2^(2^(n+1))

----		2^(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)
``````

####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足够大)

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

``````

####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

``````

####12. 2^(√(2lgn))

``````2^(√(2lgn)) = (2^lgn)^(√(2/lgn)) = n^(√(2/lgn))

``````

``````指数之指数
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)
``````

``````lg(n^3) = 3lgn
``````

``````lgn * lglg(n)  vs  3lgn
``````

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)).

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

## 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)).

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

``````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.

``````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. f(n) = O(g(n)) implies g(n) = Ω(g(n))

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

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

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 Ω∞ **

``````存在c1, f(n) <= c1 g(n), n > n0

``````

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

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)).
``````

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(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     |
``````

### 评论(5)

#### 引用来自“foy”的评论

d

2014/12/10
377
0

mindlook
2018/03/28
0
0

AI这个词相信大家都非常熟悉，近几年来人工智能圈子格外热闹，光是AlphoGo就让大家对它刮目相看。今天小天就来跟大家唠一唠如何进军人工智能的第一步——机器学习。 在机器学习领域，Python已...

ufv59to8
2018/05/12
0
0

memristor
2014/06/23
996
0

xxjbs001
2015/03/11
246
0

Spring Boot + Mybatis-Plus 集成与使用（二）

7
0

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

6
0
Flutter系列之在 macOS 上安装和配置 Flutter 开发环境

6
0
OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @凉小生 ：#今日歌曲推荐# 少点戾气，愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

2.5K
16
Excption与Error包结构，OOM 你遇到过哪些情况，SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类，Throwable 包含两个子类，Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常（checked Exc...

Garphy

42
0