math - 逆因子的增长

Question

考虑逆阶乘函数 f(n) = k 其中 k! 是最大的阶乘 <= n。我被告知逆阶乘函数是 O(log n / log log n)。这是真的吗？或者它只是对渐近增长的一个非常好的近似？我尝试的方法都给出了非常接近 log(n)/log log(n) 的东西（分母中的一个小因素或一个小项），但不完全是。

Answer 1

请记住，当我们使用 O(...) 时，常数因素无关紧要，任何增长速度比另一个术语慢的术语都可以删除。~意思是“成正比”。

如果k很大，那么n = k! ~ k^k。所以log n ~ k log k，或k ~ log n / log k或k ~ log n / log(log n / log k) = log n / (log log n - log log k)。因为n >> k我们可以把分母中的项去掉，我们得到k ~ log n / log log n了k = O(log n / log log n)。

Answer 2

从斯特林对 ln(k!) 的近似开始，然后从那里向后工作。很抱歉没有把整个事情都解决掉；今晚我的大脑似乎没有工作。