证明logn是O(2^sqrt(logn))

Question

我从 log n <= c.2^sqrt(log n) 开始，但无法得出所需的解决方案。

Answer 1

log n / 2^sqrt(log n) 的 n -> inf 的限制必须是 != inf 才能使它成立。

申请乐和医院可获得：

                             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 接近无穷大时的极限 u / 2^u 是 0，这证明了我们所追求的。

Wolfram confirms it.

Answer 2

lg(x) < sqrt(x) 对于大 x。因此，lg(log n) < sqrt(log n) 对于大 n（用 log n 代替 x）。

对 2 求双方的幂得到结果：对于大 n，log n < 2^sqrt(log n)。

Answer 3

使用变量替换，会很简单。

设m=lg(n)，我们需要显示m=O(2^sqrt(m))。
再次让N=sqrt(m)，现在归结为显示N^2=O(2^N)。
显示最后一个很容易，因为 polynomials 在增长率方面受 exponential 函数的约束。

我们上面使用的所有函数都是严格单调递增的。

证明logn是O(2^sqrt(logn))

Prove that logn is O(2^ sqrt(logn))

algorithm

big-o

asymptotic-complexity

logarithm