数学がよくわからないので教えてください。


 計算量(オーダ)を求める際には、係数を除外します。

 しかし、『n log n』という計算量を良く見かけます。

 n は log n の係数ではないのでしょうか?

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2008/04/18 20:23:43
  • 終了:2008/04/18 22:51:48

回答(1件)

id:Mook No.1

Mook回答回数1312ベストアンサー獲得回数3912008/04/18 21:21:43

ポイント60pt

係数というのは定数のことで、今回の場合はnと log n が変数としての積になっている点が異なります。


たとえば、単純な2重ループの場合それぞれが1次関数的に増加しますから、全体の計算量のオーダーは

O(n^2)になります。


質問の場合は2重ループで外側が1次、内側が log n のオーダーのような場合ですから、

計算量がO(n log n)となります。

この例としては、クイックソートのようなものがあげられますね。


下記のページが参考にならないでしょうか。

http://www.remus.dti.ne.jp/~yositomo/ura/arugo.htm

id:FLine

 おーなるほど。

 参考にした本と別の書籍も参照し直してみました。

 変数nを大きな値にしたときに無視することのできる低位の項や定数倍の係数を省略します。

2008/04/18 22:51:34

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません