日志与平方根的大O.

Question

一般来说,以下总是如此吗？

log(n)= O(n ^{a /(a + 1)})？st a是任何常数正整数,也许非常大.

如果没有,什么是最大的价值一个针对这一说法将举行真的吗？

Answer 1

随着函数的运行，log( n ) 的增长总是比n慢当n变大时^任何幂。请参阅https://math.stackexchange.com/questions/1663818/does-the-logarithm-function-grow-slower-than-any-polynomial以获取证明。

所以只要a是一个常数正整数，它的值是什么并不重要，因为总是有可能找到常数C和k使得 log( n ) <= | C ( n ^{a /( a + 1 )} | + k，这是 big-O 的定义。

但是，您也可以直观地理解它：n ^{a /( a + 1 )}随着a变大而接近n。自然地，log( n ) 总是 O( n )。