[解決済み】log(n!)=Θ(n-log(n))なのか？）

質問

私は、以下のことを示す必要があります。 ログ( n !) = Θ( n -log( n )) .

で上界を示せというヒントがありました。 n ⁿ で下界を示す。 ( n /2) ^{( n /2)} . これは、私にはそれほど直感的に理解できない。 なぜそうなるのでしょうか？ を変換する方法は確かにわかります。 n ⁿ から n -log( n ) (つまり、方程式の両辺をログすること)ですが、これはちょっと逆効果ですね。

この問題に取り組むには、どのようなアプローチが正しいのでしょうか？ 再帰ツリーを描けばいいのだろうか？ 再帰的なものは何もないので、そのようなアプローチはなさそうですが...。

どのように解決するのですか？

次のことを忘れないでください。

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

で上限を求めることができます。

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

そして、前半の和を捨ててから同じようなことをすれば下限が求まるのです。

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2)