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!)のスターリング近似から開始し、そこから逆方向に作業します。すべてを解決できなかったことをお詫びします。今夜は頭が働かないようです。