【計算量Log n】僕は実際の面接でソートの計算量

質問

【計算量Log n】僕は実際の面接でソートの計算量を聞かれて、log nですかねと言ったら「は？」という顔をされたので即座に「nより速いのはありえないですよねー、HAHAHA!」とごまかして事なきを得た。

ツイッターより

計算量のlog nのnより早いのはあり得ないってどういう意味ですか?

あとLog nの計算量とOのオーダ量の違いは何ですか?

回答No.2

lupin__X · ベストアンサー

ソートというのは、すべてのデータを比較して順番に並べる
から、 n が大きくなるとそれより大きいオーダーで計算量は
大きくなるはずで、それより小さいことはあり得ない。

ソートというのは、最大値から最小値までの並べ替えなので、
最大値を求めるだけでデータの個数 n個を比較する必要がある。
すべての順番は、n*n の比較で求まるはずで、O(n^2)より
大きいのは無駄な処理があることになる。理論上、ソートの
計算量は O(n log n)より小さくなることはない。
まして、 O(n) よりも小さい O(log n) なんて、全データを
比較してないのに、ソートできるはずがない。

O(log n) < O(n) < O(n log n) < O(n^2)

だから、ごまかせてるはずはない。
全然わかってないとバレてるはず。

計算量は、通常オーダーのレベルでします。
同じオーダーなら、個々のアルゴリズムの違いとかを比較します。

お礼

ありがとう

回答No.1

asciiz

＞計算量のlog nのnより早いのはあり得ないってどういう意味ですか?

その発言は間違っているので、その人が面接に通ったかどうかわかりませんね。
以下のページに O(n) の話があるのご参考まで。

＞一週間で身につくアルゴリズムとデータ構造|応用編第1日目：アルゴリズムと計算量
＞http://sevendays-study.com/algorithm/ex-day1.html