1

我正在解决一个来自 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)。请帮忙！

4

1 回答 1

0

为了证明它(ceil(lg lg n))!是多项式有界的，您还可以使用斯特林近似。
斯特林说的主要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-notation。

对于您的问题（证明theta(lg n)=o(n)）： fino(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。
因此，对于一个常数，einTheta(f)有一个上限。c* f(n)c

所以你进去e是Theta(lg n)有界c * lg n和由于lim c lg n / n -> 0，e也是在o(n)。

于 2014-07-01T02:46:19.080 回答