ログイン

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

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

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

(回答1件)

質問したい内容

1つだけわからないところがあります

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

どちらの方が速いのでしょうか。
manabu さんの質問 勉強レベル4
1週間前

回答(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

ベストアンサー
個人家庭教師
林 俊介 個人家庭教師 東京都/新富町駅 1週間前
  • 回答ありがとうございます。


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


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

    1週間前
クリックして回答へコメントする
あなたがベストアンサーに選んだ
林 俊介
さんは個人家庭教師をしています

質問する

回答するには ログイン してください。
  • この回答を見た人は以下の回答も見ています