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表記を使用せずに。

あなたの質問に（証明する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)ます。

于 2014-07-01T02:46:19.080 に答える