$ Oの複雑さ（\ log（n ^ n））$ vs $ o（\ log（n！））$

Question

は $ o（\ log（n！）？この種の複雑さを備えた良い/実用的なアルゴリズムはありますか？

また、アルゴリズムの複雑さの理解を確認するには、これら2つの $> o（n \ log（n））$ ？

です。

私はこのトピックから始めていて、それを正しく取得しているのかどうかはかなりよくわからない。

ありがとうございました。

Answer 1

$ O（\ log n ^ n）$ と $ O（\ log n！）$ どちらも同じ機能を説明しています。

$（\ frac {n} {E}）^ n \ le n！\ le n ^ n $ 、したがって：

$ O（n \ log n）= O（n \ log \ frac {n} {e}）= O（\ log（\ frac {n} {E}））^ n）\ subseteq o（\ log n！）\ subseteq o（\ log n ^ n）= o（n \ log n）$ 。

これは、上記のすべてのセットが一致していることを示しています。

Answer 2

$ n ^ n $ はn！より大きい！最初の乗数n x x n x x x ... x n（n回）、後者は1 x 2 x 3 x 4 x ... x nを乗算します。そのため、明らかな $ O（\ log（n ^ n））はそうではありません真実です。 $ O（\ log（n！）> O（\ log（n！））$ は明白ではなく、真実ではありません。

両側に対数を取っているからです。対数を取って、製品を合計と指数に変更する（非常におおよそ）。そして、N！についての製品を取り入れたら、N / 2より大きいN / 2の要因があることは明らかです。 > $（n / 2）^ {n / 2} $ 。対数を取って、n！ >（N / 2）log（n / 2）。 N> 4の場合、N / 2> $ n ^ {1/2} $ 、したがってlog n / 2>（log n）/ 2、したがってlog n ！ >（n / 2）log（n / 2）> n / 4 log n= 1/4ログ $ n ^ n $ 。

だからlを丸太！= $ \ theta（\ log n ^ n）$ 。