复杂度阶数 f(x) = x vs g(x) = log (x)^(log (x))

Question

什么是大 O 复杂度顺序：f(x) = x vs g(x) = log (x)^(log (x))？

Answer 1

通过示例可能更容易理解。考虑 log 表示基于 2 的对数。我们可以忽略常量，因为我们想要渐近线的行为。运行时间 f(x) vs g(x) 如下 x:

x=2^1: f(x) = 2^1 = 2    ; g(x) = log(2^1)^log(2^1) = 1^1 = 1     ;f(x) > g(x)
x=2^2: f(x) = 2^2 = 4    ; g(x) = log(2^2)^log(2^2) = 2^2 = 4     ;f(x) = g(x)
x=2^3: f(x) = 2^3 = 8    ; g(x) = log(2^3)^log(2^3) = 3^3 = 27    ;f(x) < g(x)
x=2^4: f(x) = 2^4 = 16   ; g(x) = log(2^4)^log(2^4) = 4^4 = 256   ;f(x) < g(x)
...
x=2^100: f(x) = 2^100    ; g(x) = log(2^100)^log(2^100) = 100^100 ;f(x) << g(x)

所以当 x 接近无穷大时运行 f(x) 的时间远远少于 g(x)。

Answer 2

假设 x > 0，因为 g(x) 仅适用于那些 x。这意味着我们可以进行替换 x = e^t，这给了我们

 f(x) = e^t
 g(x) = t^t

并且立即清楚 g(x) > f(x) 对所有 t > e，即对所有 x > e^e。特别地，这意味着 f(x) = O(g(x))，实际上很容易证明 f(x) = o(g(x))。

复杂度阶数 f(x) = x vs g(x) = log (x)^(log (x))

Complexity order f(x) = x vs g(x) = log (x)^(log (x))

math

computer-science

time-complexity