ここから本文です

二分探索(二分検索orバイナリサーチ)の計算量のlog2nが理解できません。

y2jhhhwweさん

2012/1/2711:16:19

二分探索(二分検索orバイナリサーチ)の計算量のlog2nが理解できません。

他の知恵袋を拝見しましたがそれでも…イマイチ理解できていません。

例題1
n=10個なら線形探索の計算量は10回、二分探索の計算量は4回となる

なぜ、二分探索の計算量は4回になるのか?

例題2
100万個のデータから探すとき、順次検索(1番目から探す)と最大100万回、
二分検索(バイナリサーチ)だと、最大21回で検索できる

なぜ、二分探索の計算量は21回になるのか?

二分探索はサーチの対象となる範囲を2分割することを繰り返してデータを見つける手法
というのは分かります。

計算量の求め方がイマイチです。

どなたかご教示を御願い致します!

追伸
プログラムの勉強をしているのですが…文系出身なので肝心な数学が苦手です。。。
Amazonで自分にピッタリな本を見つけました!これはオススメでしょうか?

これだけはおさえたい 文系プログラマーの数学知識 基礎の基礎
http://www.amazon.co.jp/%E3%81%93%E3%82%8C%E3%81%A0%E3%81%91%E3%81%...

閲覧数:
12,207
回答数:
2

違反報告

ベストアンサーに選ばれた回答

mahoo_nieeさん

2012/1/2712:43:59

計算式だけで考えてもおそらく見えてきません。

イメージは、

ABCDEFGHIJの10文字からJを見つけるには

1回)FGHIJ

2回)HIJ

3回)IJ

4回)J

10 -> 5 -> 3 -> 2 -> 1
1文字に絞り込むまでに何回2分割しないといけないのか?、で
逆に言えば
10文字あっても12文字あっても
10 -> 5 -> 3 -> 2 -> 1
12 -> 6 -> 3 -> 2 -> 1
回数は同じです。
が、20文字あると違う。
20 -> 10 -> 5 -> 3 -> 2 -> 1
この考えを整理すると、
1→2→4→8→16→32→・・・・と
2の何乗で表現できる桁かがわかれば、その何回2分割かが見えてきます。
アイテムが4つあれば、4-2-1、2回となる。
4のときは2の2乗だから計算量は2。

競技のトーナメント方式で何回戦まで必要か、何回勝てば優勝か、と考え方が似ています。
4チームいれば普通は2回勝てば優勝、です。


-----
求めるための「結果式」よりも、求める「過程」を大事にすると良いです。

質問した人からのコメント

2012/2/3 00:49:37

降参 mahoo_nieeさん,k032yfさん,御忙しい所,有難う御座いました!大変勉強になりました!また何かありましたら宜しく御願いします!

ベストアンサー以外の回答

1〜1件/1件中

k032yfさん

2012/1/2711:37:53

y2jhhhwweさん

n=2=2^1

n=4=2^2

n=100万=2^20

n=2^s
s回

あわせて知りたい

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。