ここから本文です

nの累乗と階乗の計算量、O(n^n)とO(n!)ではどちらの方が速度的には遅いでしょうか。

mac********さん

2019/4/2115:35:34

nの累乗と階乗の計算量、O(n^n)とO(n!)ではどちらの方が速度的には遅いでしょうか。

10程度の小さな数では、階乗の方が小さいですが、n=130あたりから反転してnの累乗の方が大きくなるので、累乗O(n^n)の方が階乗O(n!)よりも遅いという理解で合っていますか?

閲覧数:
27
回答数:
2
お礼:
100枚

違反報告

ベストアンサーに選ばれた回答

das********さん

2019/4/2116:05:17

> 10程度の小さな数では、階乗の方が小さいですが、n=130あたりから反転してnの累乗の方が大きくなるので

の部分は何が言いたいのか分かりません。
最初から累乗のほうが大きいということですよね?

> 累乗O(n^n)の方が階乗O(n!)よりも遅い
というのはあっています。

ただし、n^n が n! より大きいから。
というだけでは不十分です。

lim[n→∞] |n^n/n!| = ∞ となるため、というのが正しい理由になります。
(このような計算をしたときに正の定数になるなら、計算量としては同じです)

質問した人からのコメント

2019/4/22 12:39:05

前半が不明瞭で申し訳ございませんでした。
最初から累乗の方が大きいです。
ご回答いただきましてありがとうございました。

ベストアンサー以外の回答

1〜1件/1件中

edg********さん

2019/4/2115:48:09

単純に考えて、n^nはnをn個かけたもので、n!はn,n-1,n-2・・・2,1(全部でn個)をかけたものだから、n^nの方がでかい

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる