可能な説明（N！）= O（NLG（N））

Question

可能性の重複：
Is log(n!) = Θ(n·log(n))?

理由LGのための私の "証拠" である（N！） O（nlg（n））はnが多項式でlg（n！）より大きいため、nlg（n）は常に多項式でlg（n！それは容認できる理由ですか？またはあなたが数学的にそれを証明する必要がある（私は階乗に対処する方法を知っていないと思われる場合には）

Answer 1

私が見てきた通常の証明が十分に大きいNため、のnということですよ！ <n ⁿ。両方の対数をとってlog（n！）< log（n ⁿ）を得る。 ログ（b ^a）= a log（b）から、log（n！）< n log（n）が得られます。

Answer 2

おそらくもっと数学的に厳しいものが必要ですが、それほど難しいことではありません。

lg(n!) = lg 1 + lg 2 + lg 3 + ..... + lg n 

ので、あなたはy = lg xのグラフ下の面積を考慮するかもしれないし、http://en.wikipedia.org/wiki/Rectangle_methodとそれを近似します。 http://en.wikipedia.org/wiki/Stirlingのs_approximationのようなものが得られます。

あなたの四角形は上下に拘束されている必要があります。

Answer 3

ln（a⋅b）= ln（a）+ ln（b）を思い出してください。したがって、ln（n！）= ln（n・（n-1）··2・1）= ln（n）+ ln（n-1）+ ... ln（2）+ ln検査によりn・ln（n）≦ln（n！）となる。

Answer 4

使用スターリングの近似：http://en.wikipedia.org/wiki/Stirling%27s_approximation

ln n! = n\ln n - n +O(ln(n))