ログイン 新規登録

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

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

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

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

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

回答(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)もお答えいただけますと大変助かります。


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

    4か月前
回答へコメントする
あなたがベストアンサーに選んだ
林 俊介
さんは個別指導塾講師をしています

累計17,000問以上の質問から、あなたがわからない問題・回答を写真で検索しよう!

あなたと同じ問題を探そう
写真で検索する

この質問に関連した回答一覧

あなたと同じ問題を探そう
写真で検索する