对数大 O 与平方根
Big-O of log versus square root
一般来说，下列情况总是正确的吗？
log(n) = O(na/(a+1))？ s.t。 a 是任何常量正整数，可能非常大。
如果不是，那么此陈述成立的 a 的最大值是多少？
随着函数的运行，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( na/(a+1)| + k,也就是big-O的定义.
不过你也可以直观的理解：na/(a+1) 接近 n 随着 a 变大。自然地，log(n) 总是 O(n).
如果你的意思是 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))
基本事实是，由于对数的凹性，它总是在切线以下。所以
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
因此 log(n)=O(n^c) 对于任何正 C.
一般来说，下列情况总是正确的吗？
log(n) = O(na/(a+1))？ s.t。 a 是任何常量正整数，可能非常大。
如果不是，那么此陈述成立的 a 的最大值是多少？
随着函数的运行，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( na/(a+1)| + k,也就是big-O的定义.
不过你也可以直观的理解：na/(a+1) 接近 n 随着 a 变大。自然地，log(n) 总是 O(n).
如果你的意思是 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))
基本事实是，由于对数的凹性，它总是在切线以下。所以
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
因此 log(n)=O(n^c) 对于任何正 C.