algorithm - 如何证明 theta(log n)=o(log n)？

Question

我正在解决来自 CLRS 的问题，我们需要证明 (ceil(lg lg n))!是多项式有界的。

Let g(n)=(ceil(lg lg n))!

lg(g(n))=lg((ceil(lg lg n))!)
        =theta(ceil(lg lg n) * lg (ceil(lg lg n))) [since lg(n!)=theta(n * lg n)
                                                    and replacing n by ceil(lg lg n) here.]
        =theta((lg lg n) * (lg lg lg n))  ----(1)  [since ceil(n)=theta(n)
                                                    and replacing n by (lg lg n) here.]

现在如果我能证明 theta(lg n)=o(n)

=>theta(lg lg lg n)=o(lg lg n)
=>theta((lg lg n) * (lg lg lg n))=o((lg lg n) * (lg lg n))
                                 =o((lg lg n)^2)
                                 =o(lg^2(lg n))
                                 =o(lg n)  ----(2) [Polylogarithmic functions grow slower than 
                                                    polynomial functions.
                                                    =>log^b(n)=o(n^a)
                                                    =>log^2(log n)=o(logn^1)
                                                    =>log^2(log n)=o(log n)]

From (1) and (2) we have log(g(n))=o(log n)
=>g(n)=o(n^a) that is g(n) is polynomially bounded.

我面临的唯一问题是证明 theta(lg n)=o(n)。请帮忙!

Answer 1

证明(ceil(lg lg n))!是多项式有界的，你也可以使用 Stirling's approximation .
斯特林主要说n!近似于 n^n .所以以下内容成立:

ceil(lg lg n)! < (1 + lg lg n)! 
               < (1 + lg lg n)^(1 + lg lg n) 
               = (1 + lg lg n) * (1 + lg lg n)^(lg lg n)
               < (1 + lg lg n) * (2 * lg lg n)^(lg lg n)
               < (1 + lg lg n) * (lg n) * (lg lg n)^(lg lg n)

现在只剩下显示(lg lg n) ^ (lg lg n)了是多项式有界的:

             (lg lg n)^(lg lg n) < n
<=>   lg ( (lg lg n)^(lg lg n) ) < lg n
 =>   lg ( (lg lg n)^(lg lg n) ) = (lg lg n) * (lg lg lg n) 
                                 < sqrt(lg n) * sqrt(lg n)
                                 = lg n

总而言之

ceil(lg lg n)! < (1 + lg lg n) * (lg n) * n

不使用 landau 符号。

针对您的问题(证明 theta(lg n)=o(n) ): f在 o(g)表示 lim f(n)/g(n) -> 0对于 n ->无限。由于 lim (lg n)/n -> 0 , lg n在o(n) . e in Theta(f)表示 0 < liminf e(n)/f(n) <= limsup e(n)/f(n) < infinity .
所以e在 Theta(f)上限为 c* f(n) , 对于常数 c .

所以你得到 e在 Theta(lg n)以 c * lg n 为界由于lim c lg n / n -> 0 , e也在o(n) .