对数的大O符号与平方根的大O符号比较

Question

一般来说，以下内容是否总是正确的？

log(n) = O(n^a/(a+1))？其中a是任何正整数常数，或许非常大。

如果不是，那么最大的a值是多少才能使此语句成立？

- CaptainForge

Answer 1

作为函数，当n变大时，log(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，这就是大O符号的定义。

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

- pymaxion

---

"实际上a的值是无关紧要的。" 但是稍微有点重要：当a在区间[-1,0]中时，它是否仍然成立？ - trincot

你误解了。他在询问当N变得任意大时，函数log(N)的复杂度是多少。 - Malcolm McLean

@trincot，OP指定a是“任意正整数常数”。a不能在区间[-1，0]中。 - pymaxion

@MalcolmMcLean 我不理解你的评论和我回答的问题之间的区别。 - pymaxion

@pymaxion，那确实很重要。你的陈述可能被理解为OP对变量a设置的限制不相关。 - trincot

Answer 2

基本事实是，由于对数的凹性，它始终低于其切线。因此，

log(x) <= log(e) + 1/e * (x-e) = x/e

因此

log(n) = O(n).

现在只需要应用对数定律来找到答案。

log(n) = 1/c * log(n^c) <= 1/(ce) * n^c

因此，对于任何正数C，都有log(n)=O(n^c)。

- Lutz Lehmann

Answer 3

如果您的意思是log(n)∈O(n^(a/(a+1)))，对于所有正整数a而言都是正确的，因为a/a+1 < 1 => n^(a/(a+1)) ∈ O(n)并且因为log(n) ∈ O(n) => log(n) ∈ O(n^(a/(a+1)))。

- Exagon