algorithm - 如何证明：log n = O(n^c)

Question

在一本数据结构教科书中，作者用这个来证明 O(log^c(n)) 是有效的，因为复杂度非常接近常数，我不太明白这个方程。

标签： algorithmbig-o

Answer 1

这是正确的直观原因是它log的倒数e^x。正如指数函数的增长速度比x^kany快k，它的逆函数也必须比x^(1/k)any慢k。（画图并翻转 x 和 y 轴以获得这种直觉。）

然而，直觉不会导致正式的证明。

所以首先，说服自己log(log(n)) = o(log(n))。

从此，对于任何给定的 ，对于所有的，c都有一个N这样的。现在考虑两边，你发现对于足够大的 ，。因此对于任何给定的.n > Nlog(log(n)) < c log(n)e^xnlog(n) < n^clog(n) = O(n^c)c

但那是大O。我们想要little-o。嗯，log(n) = O(n^(c/2)这意味着它log(n)实际上是在o(n^c). 现在我们完成了。