基本情報技術者での質問です。

問題
５００個の要素をもつ配列を線形探索するとき、探索キーと配列中の要素との平均比較回数をAとする。
また、昇順に整列された５００個の要素をもつ配列を2分探索するとき、探索キーと配列中の要素との平均比較回数をBとする。
このとき、AはBの約何倍か。ここで、探索キーと一致する要素が、配列中に必ず存在するものとする。

答えは３１倍なんですが。

自分の解釈としては、まず線形探索の最大比較回数＝n
この場合だと500です。

この場合2分探索の最大比較回数＝（ｌｏｇ２Ｎ＋１回）

を割れば何倍かがでてくるであっていますか？？

それとバカな質問ですいません高校のときにlogをならっておらず

いまさら数学の先生がいなく理解にくるしんでいます。

(logとこの自分が考えてる解き方であっているか)回答おねがいします。

No.1 回答者： jjon-com 回答日時： 2012/10/15 21:33

質問カテゴリは次が適切です。

ビジネス・キャリア > 資格 > 情報処理技術者

--------
平均比較回数なので，Ａは Ｎではなく Ｎ／２。
Ｂは log2Ｎ＋１ではなく [log2Ｎ]です。
（ガウス記号の説明は http://oshiete.goo.ne.jp/qa/82468.html ）

Ａ＝500／2 ＝250回。

log2Ｎ とは 2のｘ乗＝Ｎ となるｘのことなので，
２のx乗＝500となるｘをガウス記号で整数化した[ｘ]は
２の8乗(＝256) ≦ 500 ＜ ２の9乗(＝512)
より，ｘ＝８回。

よって，250／8＝31.25