第三章 函數的增長 3.1 漸進記号

3.1-1 假設f（n）與g(n)都是漸進非負函數。使用θ記号的基本定義來證明max（f(n),g(n)）=θ(f(n)+g(n))。

解： c1(f(n)+g(n))<max(f(n),g(n))<c2(f(n)+g(n))

c1=1/2,c2=2 時，恒成立。

3.1-2 證明：對任意實常量a和b，其中b>0,有

(n+a)b=θ(nb)

解： c1nb≤(n+a)b≤c2nb

c1≤(1+an)≤c2

c1=1,c2=2 時，恒成立。

3.1-3 解釋為什麼“算法A的運作時間至少是 O(n2) ”這一表述是無意義的。

O:表示一個函數的漸進上界。

既然是上界，用“至少來形容”，就不恰當了吧。

3.1-4 2n+1=O(2n)成立嗎？22n=O(2n)成立嗎？

O:表示一個函數的漸進上界。

1）證明， 2n+1=O(2n) 是否成立

2n+1≤c22n,c2=2 時成立

是以，成立。

2）證明， 22n=O(2n) 是否成立

22n≤c22n,c2 為正無窮

是以，不成立。

3.1-5 證明定理3.1

定理3.1：對于任意兩個函數f(n)和g(n),我們有f(n)=θ(g(n)),當且僅當f(n)=O(g(n))且f(n)=Ω(g(n))

b<f<a,當且僅當f<a,f>b 。

3.1-6 證明：一個算法的運作時間為θ（g(n)）當且僅當其最壞情況運作時間為O(g(n)),且其最好情況運作時間為Ω（g(n)）

同上

3.1-7 證明： o(g(n))⋂w(g(n)) 為空集

因為這兩個是緊确上界和下界。

3.1-8 可以擴充我們的記号到有兩個參數n和m的情形，其中的n和m可以按不同速率獨立地趨于無窮。對于給定的函數g(n,m),用O（g（n,m））來表示一下函數集：

O(g(n,m))={f(n,m):存在正常量c,n0和m0,使得對所有n≥n0或m≥m0,有0≤f(n,m)≤cg(n,m)}

定義如下：

Ω(g(n,m))={f(n,m):存在正常量c,n0和m0,使得對所有n≥n0或m≥m0,有0≤cg(n,m)≤f(n,m)}