私は漸近分析に関する問題を練習しており、この問題に悩まされています。log（n！）= O（（log（n））^ 2）ですか？
はlog(n!) = O((log(n))^2)ですか？
私がさらに進行することはできませんよ
log(n!) = O(n*log(n))
(log 1 + log 2 + .. + log n <= log n + log n + ... + log n)
と
(log(n))^2 = O(n*log(n))
(log n <= n => (log n)^2 <= n*logn)
ことを示すことができています。どのように進むべきかについてのヒントや直感は？おかげ
Stirling's ApproximationにAccoriding：
log(n!) = n*log(n) - n + O(log(n))
O(nlogn)
なりますlog(n!)行き
：
log(1) + ... + log(n/2) + ... + log(n) = log(n/2) + ... + log(n) = log(n/2) + ... + log(n/2) = n/2 * log(n/2)
したがって、下限もnlognです。明らかに答えはです。
それは疑問ではありませんでした！ –
'はlog（n！）= O（（log（n））^ 2）ですか？'答えはNO @JanakyMurthy –
@JanakyMurthyあなたはどんな答えを期待していますか？ –
私は自分の質問に答えてくれたと思います。私たちは、以下の事実を証明します：
1）n*log(n)タイトlog(n!)
2のためにバインドされている）n*log(n)が(log(n))^2
3の上限である）n*log(n)が(log(n))^2
（1）の証明のためにthisを参照してください。
証明書（2）&（3）は質問自体で提供されます。 成長速度log n<成長速度n。 成長率log(n)^2<成長率n*log(n)です。だから、結論は私が何を間違い
プルーフ3について、あなたが与えたリンクでは、アプローチは下限については私と同じであり、下限は 'n/2 * log（n/2）' @ジャナキ –
を行った場合
log(n!) = big-omega(log(n^2))は が私を修正していることである（ここで私はn*log(n)の成長率がlog(n)^2の成長率よりも厳密に大きい表すために少し-Oを使用していた ので
log(n)^2 = o(n*log(n))（log n）^ 2）にありません。 – Henryこの質問は、数学に関するものであり、プログラミングアルゴリズムに関するものではありません。 – FDavidov
@Henryそれではどのように表示しますか？グラフをプロットするよりも、それを表示するためのより正式な方法がありますか？ –