ログイン 新規登録

お使いのブラウザ(Internet Explorer)では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ:Google Chrome(グーグル・クローム)

時間計算量のオーダ記法で、cが定数の時O...

時間計算量のオーダ記法で、cが定数の時O(n^c)<O(n!)ということはわかるのですが、O(n^n)とO(n!)の関係性がわかりません。

どちらの方が速いのでしょうか。
11か月前

回答(1件)

ベストアンサーに選ばれました
オンライン家庭教師

こんにちは!


結論を述べると、n^n の方が(発散が)早いです。

n! のオーダーは n! ~ sqrt(2πn)(n/e)^n となっており、e^n の分だけ違いがでるということですね。

「スターリングの近似」などで検索すると、理解が深まると思います。


Wiki:

https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%AE%E8%BF%91%E4%BC%BC

この回答をした先生に
オンラインでの個別指導を依頼できます

林 俊介
オンライン家庭教師

自己紹介

みなさん、こんにちは! 林 俊介 (はやし しゅんすけ)と申します。 ---------- 私の塾...

合格実績

合格実績のうち一部をお示しいたします! <中学受験> 女子学院中学校 豊島岡女子学園中学校 渋谷教...
  • 回答ありがとうございます。


    可能であればこちらの質問(https://noschool.asia/question/192511-1562491435)もお答えいただけますと大変助かります。


    よろしくお願いいたします。

    11か月前
回答へコメントする
あなたがベストアンサーに選んだ
林 俊介
さんはオンライン家庭教師をしています

他の質問・回答も見る