algorithm - 关于 big-oh 的谜题，介于对数和多项式之间

Question

我们知道 log(n) 是 O(n^0.000001) 甚至 (log(n))^9999 = O(n^0.000001)。

我想找到一个函数 f(n) 使得 (log(n))^k = O(f(n)) 对于每个 k AND f(n) = O(n^e) 对于每个 e > 0. 谁能帮忙？

Answer 1

根据您的符号，让我们考虑一下 k 和 e，并注意 g(n) = log(n)^k 和 h(n) = n^e 。

给定实数 a > 1 和 1 > b > 0，考虑

f(n) = a^((log(n))^b)

我们有

log(g(n)/f(n)) = k.log(log(n)) - log(a).(log(n))^b
               ---> -Inf as n ---> +Inf because log(a) > 0 and b > 0

=> g(n)/f(n) ---> 0 as n ---> +Inf
=> g(n) = o(f(n))
=> g(n) = O(f(n))

和

log(f(n)/h(n)) = log(a).(log(n))^b - e.log(n)
               ----> -Inf as n ---> +Inf because b < 1

=> f(n)/h(n) ---> 0 as n --> +Inf
=> f(n) = o(h(n))
=> f(n) = O(h(n))

#