3.1-1
分情况讨论
当
f(n)≥g(n)
f(n)≥g(n)时,
max(f(n),g(n))=f(n)
max(f(n),g(n))=f(n),存在
c1=12,c2=1,n0>0
c1=12,c2=1,n0>0使得
0<c1(f(n)+g(n))≤f(n)≤c2(f(n)+g(n))对于所有n≥n0
0<c1(f(n)+g(n))≤f(n)≤c2(f(n)+g(n))对于所有n≥n0同理可证当
g(n)>f(n)
g(n)>f(n)的情况
3.1-2
(n+a)b=nb+c1nb−1+c2nb−2+⋯+ab=θ(nb)
(n+a)b=nb+c1nb−1+c2nb−2+⋯+ab=θ(nb)
3.1-3
大O表示法用来表示一个算法复杂度的上界,而“至少”一词用来形容下界,所以这句话的意思是该算法复杂度的上界只要不小于
O(n2)
O(n2)即可,相当于没有说明算法的复杂度的界限,没有意义。
3.1-4
2n+1=O(2n)
2n+1=O(2n)
证明:存在
c=2,n0>0
c=2,n0>0使得
0≤2n+1≤c2n对于所有n≥n0
0≤2n+1≤c2n对于所有n≥n0
22n≠O(2n)
22n≠O(2n)
证明:假设存在
c,n0
c,n0使得
0≤22n≤c2n对于所有n≥n0⇒2n∗2n≤c2n⇒2n≤c
0≤22n≤c2n对于所有n≥n0⇒2n∗2n≤c2n⇒2n≤c由于不存在常数c使得等式成立,故产生矛盾,得证。
3.1-5
利用定义就可以直接证明
3.1-6
最坏情况下复杂度为
O(g(n))
O(g(n))说明所有情况时间复杂度为
O(g(n))
O(g(n)),最好情况下时间复杂度为
Θ(g(n))
Θ(g(n))说明所有情况时间复杂度为
Ω(g(n))
Ω(g(n)),根据定理3.1得算法时间复杂度为
Θ(g(n))
Θ(g(n))
3.1-7
f(n)=o(g(n))
f(n)=o(g(n))说明对于任意正常数
c,n0
c,n0,对于所有的
n≥n0
n≥n0都有
0≤f(n)<cg(n)对于所有n≥n0
0≤f(n)<cg(n)对于所有n≥n0这时假设
f(n)=ω(g(n))
f(n)=ω(g(n)),说明对于任意正常数
c,n0
c,n0,对于所有的
n≥n0
n≥n0都有
0≤cg(n)<f(n)
0≤cg(n)<f(n)然而这样的常数c是存在的,故产生矛盾,可得
o(g(n))∩ω(g(n))=Φ
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):存在大于零的常数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}
Θ(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
x1<x2,都有
f(x1)<f(x2)
f(x1)<f(x2)
g(x1)<g(x2)
g(x1)<g(x2)所以
f(x1)+g(x1)<f(x2)+g(x2)
f(x1)+g(x1)<f(x2)+g(x2)
f(g(x1))<f(g(x2))
f(g(x1))<f(g(x2))如果当f(x)和g(x)都非负时显然有
f(x1)∗g(x1)<f(x2)∗g(x2)
f(x1)∗g(x1)<f(x2)∗g(x2)
3.2-2
lgalogbc=logbclga=lgalgclgb
lgalogbc=logbclga=lgalgclgb
lgclogba=logbalgc=lgalgclgb
lgclogba=logbalgc=lgalgclgb
⇒alogbc=clogba
⇒alogbc=clogba
3.2-3
证明
lg(n!)=Θ(nlgn)
lg(n!)=Θ(nlgn):
lgn!=∑i=1nlgi<∑i=1nlgn=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
∑i=1nlgi=∑i=1n/2[lgi+lg(n−i)]=∑i=1n/2[lgi(n−i)]>∑i=1n/2lgn24=nlgn−n=12nlgn
⇒lg(n!)=Θ(nlgn)
⇒lg(n!)=Θ(nlgn)证明
n!=ω(2n)
n!=ω(2n):
∵当n>4时,i(n−i)>22
∵当n>4时,i(n−i)>22
∴n!=∏i=1n/2i(n−i)>∏i=1n/222=2n
∴n!=∏i=1n/2i(n−i)>∏i=1n/222=2n
∴n!=ω(2n)
∴n!=ω(2n)证明
n!=o(nn)
n!=o(nn):
∵当n>1时,n!=∏i=1ni<∏i=1nn=nn
∵当n>1时,n!=∏i=1ni<∏i=1nn=nn
∴n!=o(nn)
∴n!=o(nn)
3.2-4
证明
f(n)
f(n)是否多项式有界等价于证明
lgf(n)=O(lgn)
lgf(n)=O(lgn),这是因为如果
f(n)
f(n)多项式有界,则存在正常数
c,k,n0
c,k,n0使得对于所有的
n>n0
n>n0都有
f(n)<cnk
f(n)<cnk,即
lgf(n)<kclgn
lgf(n)<kclgn,所以
lgf(n)=Olgn
lgf(n)=Olgn,反之亦然。
对于
⌈lgn⌉!
⌈lgn⌉!我们有
lg(⌈lgn⌉!)=Θ(⌈lgn⌉lg⌈lgn⌉)=Θ(lgnlglgn)=ω(lgn)
lg(⌈lgn⌉!)=Θ(⌈lgn⌉lg⌈lgn⌉)=Θ(lgnlglgn)=ω(lgn)
⌈lgn⌉!
⌈lgn⌉! 非多项式有界
对于
⌈lglgn⌉!
⌈lglgn⌉! 我们有
lg(⌈lglgn⌉!)=Θ(⌈lglgn⌉lg⌈lglgn⌉)=Θ(lglgnlglglgn)=o((lglgn)2)=o(lgn)
lg(⌈lglgn⌉!)=Θ(⌈lglgn⌉lg⌈lglgn⌉)=Θ(lglgnlglglgn)=o((lglgn)2)=o(lgn)
⌈lglgn⌉!
⌈lglgn⌉! 多项式有界
3.2-5
lg∗lgn=lg∗n−1>lglg∗n,当lg∗n>2时
lg∗lgn=lg∗n−1>lglg∗n,当lg∗n>2时
3.2-6
ϕ2=(1+5√2)2=3+5√2=ϕ+1
ϕ2=(1+52)2=3+52=ϕ+1
ϕ^2=(1−5√2)2=3−5√2=ϕ^+1
ϕ^2=(1−52)2=3−52=ϕ^+1
3.2-7
证明:
当i = 0时,
ϕ0−ϕ^05√=0=F0
ϕ0−ϕ^05=0=F0当i = 1时,
ϕ1−ϕ^15√=1=F1
ϕ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√
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))
g(n)=Θ(f(n))⇔f(n)=Θ(g(n)),所以
klnk=Θ(n)⇔n=Θ(klnk)
klnk=Θ(n)⇔n=Θ(klnk), 要证
k=Θ(n/lnn)
k=Θ(n/lnn)等价于证
n/lnn=Θ(k)
n/lnn=Θ(k),代入条件得
nlnn=Θ(klnkln(klnk))=Θ(klnklnk)=Θ(k)
nlnn=Θ(klnkln(klnk))=Θ(klnklnk)=Θ(k)
3-1
a.
P(n)=∑i=0daini=nd∑i=0daini−d≤nd∑i=0dai≤cnk
P(n)=∑i=0daini=nd∑i=0daini−d≤nd∑i=0dai≤cnkb.
P(n)=∑i=0daini≥nd≥cnd
P(n)=∑i=0daini≥nd≥cndc. 由前两问可证。
d. 同a
e. 同b
3-2
A |
B |
O
O
|
o
o
|
Ω
Ω
|
ω
ω
|
Θ
Θ
|
lgkn
lgkn
|
nϵ
nϵ
|
yes |
yes |
no |
no |
no |
nk
nk
|
cn
cn
|
no |
no |
yes |
yes |
no |
n√
n
|
nsinn
nsinn
|
no |
no |
no |
no |
no |
2n
2n
|
2n/2
2n/2
|
no |
no |
yes |
yes |
no |
nlgc
nlgc
|
clgn
clgn
|
yes |
no |
yes |
no |
yes |
lg(n!)
lg(n!)
|
lg(nn)
lg(nn)
|
yes |
no |
yes |
no |
yes |
3-3
a.
22n+1>22n>(n+1)!>n!>en>n2n>2n>(3/2)n>(lgn)lgn=nlglgn>(lgn)!
22n+1>22n>(n+1)!>n!>en>n2n>2n>(3/2)n>(lgn)lgn=nlglgn>(lgn)!
>n3>n2=4lgn>nlgn=lg(n!)>n=2lgn>(2√)lgn=n√>22lgn√>lg2n>lnn
>n3>n2=4lgn>nlgn=lg(n!)>n=2lgn>(2)lgn=n>22lgn>lg2n>lnn
>lgn−−−√>lnlnn>2lg∗n>lg∗n=lg∗(lgn)>lg(lg∗n)>n1/lgn=2=1
>lgn>lnlnn>2lg∗n>lg∗n=lg∗(lgn)>lg(lg∗n)>n1/lgn=2=1b. 非连续性函数或者震荡函数就能满足要求,比如
f(n)={n,0, −1n>0 −1n<0
f(n)={n, −1n>0 0, −1n<0
3-4
a. 错误,举个反例
n=O(n2)
n=O(n2),而
n2≠O(n)
n2≠O(n)
b. 错误,举个反例
n+n2=O(n2)≠O(min(n,n2))=O(n)
n+n2=O(n2)≠O(min(n,n2))=O(n)
c. 正确,
f(n)=O(g(n))
f(n)=O(g(n))表明存在正常数
c,n0
c,n0对所有
n≥n0
n≥n0都有
f(n)≤cg(n)
f(n)≤cg(n),所以也有
lgf(n)≤lg(cg(n))
lgf(n)≤lg(cg(n)),得证
d. 正确,
f(n)=O(g(n))
f(n)=O(g(n))表明存在正常数
c,n0
c,n0对所有
n≥n0
n≥n0都有
f(n)≤cg(n)
f(n)≤cg(n),所以也有
2f(n)≤2cg(n)
2f(n)≤2cg(n),得证
e. 正确,同理可证。
f. 正确,定义直接证明。
g. 错误,举个反例
2n=Θ(2n)=ω(2n/2)
2n=Θ(2n)=ω(2n/2)
h. 正确,
g(n)=o(f(n))
g(n)=o(f(n))表明存在正常数
n0
n0对于任意正常数
c
c,对所有
n≥n0
n≥n0都有
g(n)<f(n)
g(n)<f(n),所以对于所有
n≥n0
n≥n0都有
f(n)+o(f(n)))<f(n)+f(n)=2f(n)
f(n)+o(f(n)))<f(n)+f(n)=2f(n),得证。
3-5
a. 只要证明
f(n)=O(g(n))
f(n)=O(g(n))的补集包含于
f(n)=Ω∞(g(n))
f(n)=Ω∞(g(n))中即可。
f(n)=O(g(n))
f(n)=O(g(n))表示存在正常数
c,n0
c,n0对所有
n≥n0
n≥n0都有
f(n)≤cg(n)
f(n)≤cg(n),那么他的补集是不存在常数
c,n0
c,n0对所有
n≥n0
n≥n0都有
f(n)≤cg(n)
f(n)≤cg(n),显然包含于
f(n)=Ω∞(g(n))
f(n)=Ω∞(g(n))中,因为如果存在正常数c对有限个n的话成立的话,就能找到一个
n0
n0大于有限个n中最大的那个,使得
f(n)≤cg(n)
f(n)≤cg(n)成立。但是如果换成
Ω(g(n))
Ω(g(n))的话,3-3b中的例子就是个反例。
b. 用符号
Ω(f(n))
Ω(f(n))可以保证在n足够大的情况下算法复杂度都不低于
f(n)
f(n),即最好的情况下也不低于
f(n)
f(n)。而使用符号
Ω∞(f(n))
Ω∞(f(n))则表示该算法在很多时候复杂度都不低于
f(n)
f(n),但在某些比较好的情况下有可能会低于
f(n)
f(n)。
c. 没有变化?求指教
d.
Ω~(g(n))={f(n):∃c,k,n0>0对∀n≥n0有0≤cg(n)lgk(n)≤f(n)}
Ω~(g(n))={f(n):∃c,k,n0>0对∀n≥n0有0≤cg(n)lgk(n)≤f(n)}
Θ~(g(n))={f(n):∃c1,c2,k,n0>0对∀n≥n0有0≤c1g(n)lgk(n)≤f(n)≤c2g(n)lgk(n)}
Θ~(g(n))={f(n):∃c1,c2,k,n0>0对∀n≥n0有0≤c1g(n)lgk(n)≤f(n)≤c2g(n)lgk(n)}定理3.1由定义可知。
3-6
a.
Θ(n)
Θ(n)
b.
Θ(lg∗n)
Θ(lg∗n)
c.
Θ(lgn)
Θ(lgn)
d.
Θ(lgn)
Θ(lgn)
e.
Θ(lglgn)
Θ(lglgn)
f.
∞
∞
g.
Θ(lglgn)
Θ(lglgn)
h. 不会,求指教