人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

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

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

●質問者: サード
●カテゴリ:はてなの使い方 学習・教育
✍キーワード:数学 計算
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● Mook
●60ポイント

係数というのは定数のことで、今回の場合は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

◎質問者からの返答

おーなるほど。

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ