O(n^(1/logn))实际上是常数吗？

Question

我看到了这个时间复杂度函数，据我所知，它实际上是恒定的。如果我错了，请纠正我。

n^(1/logn) => (2^m)^(1/log(2^m)) => (2^m)^(1/m) => 2 

因为任何一个n都可以写成2的幂次方，所以我可以进行上述简化并证明它是恒定的，对吗？

- Nirup Iyer

---

不需要写下证明，只需测试一些案例。是的。 - Frederik Spang

我投票关闭此问题，因为这只是一个数学问题，最好在math.stackexchange.com上提问。 - Peter O.

Answer 1

假设 log 是自然对数，则这与 e 相等，而不是 2，但无论如何都是常数。

首先，让：

k = n^(1 / log n)

然后取两边的对数：

log k = (1 / log n) * log n

因此：

log k = 1

现在将两边都提高到e的幂级数:

e^(log k) = e^(1)

因此：

k = e.

- John Feminella

Answer 2

这里提供了一种替代证明：

• 1 / (log n) = (log e) / (log n) = log_n e，根据换底公式。
• 因此，n^{log_n e} = e，根据对数作为指数的反函数的定义。

- kaya3

---

是的，log e = 1，因为exp(1) = e。 - kaya3

是的，我的错，抱歉。我想我在考虑二进制，因为问题使用了它。或者可能是因为我刚从床上起来，有点糊涂 :-) - Kelly Bundy

没问题。无论你使用什么基数，它都可以正常工作，只需用基数替换 e，然后在末尾将常量等于该基数即可。 - kaya3