【計算量Log n】僕は実際の面接でソートの計算量を聞かれて、log nですかねと言ったら「は？」と

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

ツイッターより

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

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

No.2 ベストアンサー 回答者： osamuy 回答日時： 2021/10/15 13:07

y=xとy=log(x)のグラフを書けばわかりやすいです。

log(x)のほうがyの値が小さいので、計算が速いということになります。

で、n個の数値列があってその中の最大を求めるのに必要な計算量がO(n)で、それを繰り返さないとソートできないので、ソートの計算量がO(n)以上になります。

なのに、O(n)より小さい計算量のO(logn)と答えたら、HA?と言われても仕方ないかと。

まあ、「事なきを得た」ということから、多分技術力以外のことでポイントを稼いだのでは。

この回答へのお礼

みんなありがとう

お礼日時：2021/10/16 18:51

No.1 回答者： トモクンアヤチャン 回答日時： 2021/10/15 09:53

おかしな面接ですね。

Oはオーダ量とする説明もありますが、注文（オーダ）にこたえる所要計算量（アウトプット）という方が近いかもしれません。
ｎは計算すべき数ですから、ソートするデータ量 2個とか65536個とか。
①O(n)は、nに比例した回数の計算ステップを要する場合。
　足算とか掛算は2個なら1回、3個なら2回……
②O(n^2)は、n^2に比例した回数の計算ステップを要する場合。
　バブルソートなどです。
③O(logn)は、lognに比例した回数の計算ステップを要する場合。
　log2=1,log65536=16です。クイックソートなどです。