算法導論（第三版） 第三章練習題

http://www.cnblogs.com/Jiajun/archive/2013/05/06/3063574.html

3.1-1

分情況讨論

當 f(n)≥g(n) 時， max(f(n),g(n))=f(n) ，存在 c1=12,c2=1,n0>0 使得

0<c1(f(n)+g(n))≤f(n)≤c2(f(n)+g(n))對于所有n≥n0 同理可證當 g(n)>f(n) 的情況

3.1-2

(n+a)b=nb+c1nb−1+c2nb−2+⋯+ab=θ(nb)

3.1-3

大O表示法用來表示一個算法複雜度的上界，而“至少”一詞用來形容下界，是以這句話的意思是該算法複雜度的上界隻要不小于 O(n2) 即可，相當于沒有說明算法的複雜度的界限，沒有意義。

3.1-4

2n+1=O(2n)

證明：存在 c=2,n0>0 使得

0≤2n+1≤c2n對于所有n≥n0 22n≠O(2n)

證明：假設存在 c,n0 使得 0≤22n≤c2n對于所有n≥n0⇒2n∗2n≤c2n⇒2n≤c 由于不存在常數c使得等式成立，故産生沖突，得證。

3.1-5

利用定義就可以直接證明

3.1-6

最壞情況下複雜度為 O(g(n)) 說明所有情況時間複雜度為 O(g(n)) ，最好情況下時間複雜度為 Θ(g(n)) 說明所有情況時間複雜度為 Ω(g(n)) ，根據定理3.1得算法時間複雜度為 Θ(g(n))

3.1-7

f(n)=o(g(n)) 說明對于任意正常數 c,n0 ，對于所有的 n≥n0 都有

0≤f(n)<cg(n)對于所有n≥n0 這時假設 f(n)=ω(g(n)) ，說明對于任意正常數 c,n0 ，對于所有的 n≥n0 都有 0≤cg(n)<f(n) 然而這樣的常數c是存在的，故産生沖突，可得 o(g(n))∩ω(g(n))=Φ 。

3.1-8

Ω(g(m,n))={f(m,n):存在大于零的常數c,n0,m0使得0≤cg(n,m)≤f(n,m)對于所有n≥n0或m≥m0} Θ(g(m,n))={f(m,n):存在大于零的常數c1,c2,n0,m0使得0≤c1g(n,m)≤f(n,m)≤c2g(n,m)對于所有n≥n0或m≥m0}

3.2-1

由于f(n)和g(n)單調遞增，是以對于任意 x1<x2 ，都有

f(x1)<f(x2) g(x1)<g(x2) 是以 f(x1)+g(x1)<f(x2)+g(x2) f(g(x1))<f(g(x2)) 如果當f(x)和g(x)都非負時顯然有 f(x1)∗g(x1)<f(x2)∗g(x2)

3.2-2

lgalogbc=logbclga=lgalgclgb lgclogba=logbalgc=lgalgclgb ⇒alogbc=clogba

3.2-3

證明 lg(n!)=Θ(nlgn) ：

lgn!=∑i=1nlgi<∑i=1nlgn=nlgn ∑i=1nlgi=∑i=1n/2[lgi+lg(n−i)]=∑i=1n/2[lgi(n−i)]>∑i=1n/2lgn24=nlgn−n=12nlgn ⇒lg(n!)=Θ(nlgn) 證明 n!=ω(2n) ： ∵當n>4時，i(n−i)>22 ∴n!=∏i=1n/2i(n−i)>∏i=1n/222=2n ∴n!=ω(2n) 證明 n!=o(nn) ： ∵當n>1時，n!=∏i=1ni<∏i=1nn=nn ∴n!=o(nn)

3.2-4

證明 f(n) 是否多項式有界等價于證明 lgf(n)=O(lgn) ，這是因為如果 f(n) 多項式有界，則存在正常數 c,k,n0 使得對于所有的 n>n0 都有 f(n)<cnk ，即 lgf(n)<kclgn ，是以 lgf(n)=Olgn ，反之亦然。

對于 ⌈lgn⌉! 我們有

lg(⌈lgn⌉!)=Θ(⌈lgn⌉lg⌈lgn⌉)=Θ(lgnlglgn)=ω(lgn) ⌈lgn⌉!  非多項式有界

對于  ⌈lglgn⌉!  我們有 lg(⌈lglgn⌉!)=Θ(⌈lglgn⌉lg⌈lglgn⌉)=Θ(lglgnlglglgn)=o((lglgn)2)=o(lgn) ⌈lglgn⌉!  多項式有界

3.2-5

lg∗lgn=lg∗n−1>lglg∗n,當lg∗n>2時

3.2-6

ϕ2=(1+5√2)2=3+5√2=ϕ+1 ϕ^2=(1−5√2)2=3−5√2=ϕ^+1

3.2-7

證明：

當i = 0時，

ϕ0−ϕ^05√=0=F0 當i = 1時， ϕ1−ϕ^15√=1=F1 假設當i = k-1和i = k時都滿足公式，則當i = k+1時 Fk+1=Fk+Fk−1=(ϕk+ϕk−1)−(ϕ^k+ϕ^k−1)5√=ϕk−1(ϕ+1)−ϕ^k−1(ϕ^+1)5√=ϕk+1−ϕ^k+15√

3.2-8

這題要用到性質 g(n)=Θ(f(n))⇔f(n)=Θ(g(n)) ，是以 klnk=Θ(n)⇔n=Θ(klnk) ， 要證 k=Θ(n/lnn) 等價于證 n/lnn=Θ(k) ，代入條件得

nlnn=Θ(klnkln(klnk))=Θ(klnklnk)=Θ(k)