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

Question

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

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

既然任意n都可以写成2的幂，我可以做上面的化简，证明它是常数，对吧？

Answer 1

假设 log 是自然对数，那么这相当于 e，而不是 2，但无论哪种方式它都是一个常数。

首先，让:

k = n^(1 / log n)

然后取两边的log:

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

所以:

log k = 1

现在对两边求 e 的幂得到:

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

因此:

k = e.