思考题
3-1 （多项式的渐近行为） 假设p(n)=∑di=0aini是一个关于n的d次多项式，其中ad>0，k是一个常量。使用渐近记号的定义来证明下面的性质。
a.若k≥d，则p(n)=O(nk)。
b.若k≤d，则p(n)=Ω(nk)。
c.若k=d，则p(n)=Θ（nk)。
d.若k>d，则p(n)=o(nk)。
e.若k<d，则p(n)=ω(nk)。
3-2 （相对渐近增长） 为下表中的每对表达式(A,B)指出A是否是B的O、o、Ω、ω或Θ。假设k≥1、ε>0且c>1均为常量。回答应该以表格的形式，将“是”或“否”写在每个空格中。
3-3 （根据渐近增长率排序）
a.根据增长的阶来排序下面的函数，即求出满足g1=Ω(g2)，g2=Ω(g3)，…，g29=Ω(g30)的函数的一种排列g1，g2，…，g30。把你的表划分成等价类，使得函数f(n)和g(n)在相同类中当且仅当f(n)=Θ（g(n))。
61
lg(lgn)2lgn（2）lgnn2n!（lgn)!
32nn3lg2nlg(n!)22nn1/lgn
lnlnnlg*nn·2nnlglgnlnn1
2lgn（lgn)lgnen4lgn(n+1)!lgn
lg*（lgn)22lgnn2nnlgn22n+1
b.给出非负函数f(n)的一个例子，使得对所有在(a)部分中的函数gi(n)，f(n)既不是O(gi(n))也不是Ω(gi(n))。
3-4 （渐近记号的性质） 假设f(n)和g(n)为渐近正函数。证明或反驳下面的每个猜测。
a.f(n)=O(g(n))蕴涵g(n)=O(f(n))。
b.f(n)+g(n)=Θ（min(f(n)，g(n)))。
c.f(n)=O(g(n))蕴涵lg(f(n))=O（lg(g(n)))，其中对所有足够大的n，有lg(g(n))≥1且f(n)≥1。
d.f(n)=O(g(n))蕴涵2f(n)=O(2g(n))。
e.f(n)=O((f(n))2)。
f.f(n)=O(g(n))蕴涵g(n)=Ω(f(n))。
g.f(n)=Θ（f(n/2))。
h.f(n)+o(f(n))=Θ（f(n))。
3-5 （O与Ω的一些变形） 某些作者用一种与我们稍微不同的方式来定义Ω；假设我们使用Ω∞（读作“Ω无穷”）来表示这种可选的定义。若存在正常量c，使得对无穷多个整数n，有f(n)≥cg(n)≥0，则称f(n)=Ω∞(g(n))。
a.证明：对渐近非负的任意两个函数f(n)和g(n)，或者f(n)=O(g(n))或者f(n)=Ω∞(g(n))或者二者均成立，然而，如果使用Ω来代替Ω∞，那么该命题并不为真。
62
b.描述用Ω∞代替Ω来刻画程序运行时间的潜在优点与缺点。
某些作者也用一种稍微不同的方式来定义O；假设使用O′来表示这种可选的定义。我们称f(n)=O′(g(n))当且仅当f(n)=O(g(n))。
c.如果使用O′代替O但仍然使用Ω，定理3.1中的“当且仅当”的每个方向将出现什么情况？
有些作者定义O（读作“软O”）来意指忽略对数因子的O：
O(g(n))={f(n)：存在正常量c，k和n0，使得对所有n≥n0，有0≤f(n)≤cg(n)lgk(n)}
d.用一种类似的方式定义Ω和Θ。证明与定理3.1相对应的类似结论。
3-6 （多重函数） 我们可以把用于函数lg中的重复操作符应用于实数集上的任意单调递增函数f(n)。对给定的常量c∈R，我们定义多重函数f*c为
f*c（n)=min{i≥0：f（i）（n)≤c}
该函数不必在所有情况下都为良定义的。换句话说，值f*c(n)是为缩小其参数到c或更小所需要函数f重复应用的数目。
对如下每个函数f(n)和常量c，给出f*c(n)的一个尽量紧确的界。
