Problem 1 (教材习题 3.2-2)
证明:alogbc=clogba 。
Solution
证明:因为
lnalogbc=logbclna=lnblnclna=lnblnalnc=logbalnc=lnclogba
所以 alogbc=clogba 。
Problem 2 (教材习题 3.2-3)
证明 log(n!)=Θ(nlogn) ,并证明 n!=ω(2n) 且 n!=o(nn) 。
Solution
证明:根据斯特林近似公式(见第2讲PPT第10页,教材3.2节),有:
log(n!)=log(2πn(en)n(1+Θ(n1)))=21log(2πn)+nlogn−nloge+log(1+Θ(n1))
其中最高阶项是 nlogn ,所以 log(n!)=Θ(nlogn) 。
n→∞limn!2n=n→∞lim2πn(1+Θ(n1))1(n2e)n≤n→∞lim(n2e)n≤n→∞lim(21)n,n≥4e=0
于是 n→∞limn!2n=0 ,则 n!=ω(2n) 。
n→∞limn!nn=n→∞lim2πn(1+Θ(n1))1en≥n→∞limc⋅nen,c is a constant=∞
于是 n→∞limn!nn=∞ ,则 n!=o(nn) 。
Problem 3 (教材习题 3.2-4)
函数 ⌈logn⌉! 多项式有界吗?函数 ⌈loglogn⌉! 多项式有界吗?
Solution
- 函数 ⌈logn⌉! 不是多项式有界的。
证明:反证法。假设 ⌈logn⌉! 是多项式有界的,则存在常数 c,a,n0 ,使得当 n≥n0 时, ⌈logn⌉!≤cna 恒成立。特别地,考虑 n=2k,k∈N 的情况,有 ⌈k⌉!≤c(2a)k ,这与阶乘并不是指数有界是矛盾的。
阶乘不是指数有界的这件事情可以通过问题2中类似的方式证明: n!=ω(an) 。
- 函数 ⌈loglogn⌉! 是多项式有界的。
证明:不失一般性,令 n=22k ,则有
⌈loglogn⌉!=k!=i=1∏ki≤i=1∏k22i−1=2i=1∑k2i−1=22k−1≤22k=n
于是, ⌈loglogn⌉! 是多项式有界的。
Problem 4 (教材习题 3.2-5)
如下两个函数中,哪一个渐近更大些:log(log∗n) 还是 log∗(logn) ?
Solution
注意到 log∗(2n)=1+log∗n ,则:
n→∞limlog∗(logn)log(log∗n)=n→∞limlog∗(log(2n))log(log∗(2n))(换元:n→2n)=n→∞limlog∗nlog(log∗n+1)=n→∞limnlog(n+1)(换元:log∗n→n)=0=n→∞limn+11(洛必达法则)
从而 log(log∗n)=o(log∗(logn)) , log∗(logn) 渐近更大些。
Problem 5 (教材习题 3.2-8)
证明: klnk=Θ(n)⇒k=Θ(n/lnn) 。
Solution
证明:下面的讨论都是在 n 和 k 充分大的情况下。
由 klnk=Θ(n) 有 c1n≤klnk≤c2n 。
于是 c2klnk≤n≤c1klnk ,
从而 lnk+ln(2)k−lnc2≤lnn≤lnk+ln(2)k−lnc1 。
不难发现 lnn=Θ(lnk) ,不妨设 c3lnk≤lnn≤c4lnk ,于是
c4lnkc2klnk≤lnnn≤c3lnkc1klnk
即 c2c4k≤n/lnn≤c1c3k ,简单变形有:
c1c3(n/lnn)≤k≤c2c4(n/lnn)
因此 k=Θ(n/lnn) 。