lognがO（2^sqrt（logn））であることを証明してください。

Question

log nで始まり、< = c.2^sqrt（log n）ですが、目的の解に到達できませんでした。

Answer 1

lg（x）<大きなxの場合はsqrt（x）。したがって、大きなn（xの代わりにlog n）に対してlg（log n）< sqrt（log n）。

両側の力を2にすると、結果は次のようになります。log n < 2 n sqrt（log n）

Answer 2

n -> infの値がlog n/2^sqrt(log n)であることは、それが真であるためには!= infでなければなりません。

取得するL'病院を適用します。

       1 
          - 
          n 
     -----------------------------------------   = 
2^sqrt(log n) * log 2 * 0.5 * (1/sqrt(log n)) * (1/n) 

         1 
=  --------------------------------   = 
    2^(sqrt(log n)) * log 2 * 0.5 * (1/sqrt(log n)) 


= let u = sqrt(log n) = 

= u/[2^u * log 2 * 0.5] 

を制限uはの無限大に近づくにつれて、我々は後にしているものを証明している、0です。

Wolfram confirms it。

Answer 3

可変置換を使用すると、簡単になります。

1. m=lg(n)とすると、m=O(2^sqrt(m))と表示する必要があります。

2. もう一度N=sqrt(m)とすると、N^2=O(2^N)と表示されます。

3. polynomialsは、成長速度の点でexponential関数によって上から境界付けられているため、最後のものを表示するのは簡単です。

また、上記で使用したすべての関数は厳密に単調増加しています。