最大1万円超分の電子書籍プレゼント♪

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

ツイッターより

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

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

gooドクター

A 回答 (2件)

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

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

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

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

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

みんなありがとう

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

おかしな面接ですね。


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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

このカテゴリの人気Q&Aランキング