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

二分探索(二分検索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%AF%E3%81%8A%E3%81%95%E3%81%88%E3%81%9F%E3%81%84-%E6%96%87%E7%B3%BB%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%83%BC%E3%81%AE%E6%95%B0%E5%AD%A6%E7%9F%A5%E8%AD%98-%E5%9F%BA%E7%A4%8E%E3%81%AE%E5%9F%BA%E7%A4%8E-%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%80%8C%E7%A2%BA%E5%AE%9F%E3%80%8D%E9%A4%8A%E6%88%90%E8%AC%9B%E5%BA%A7-%E3%81%8B%E3%81%8A%E3%82%8A/dp/4774139947

プログラミング14,553閲覧

1人が共感しています

ベストアンサー

4

計算式だけで考えてもおそらく見えてきません。 イメージは、 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回勝てば優勝、です。 ----- 求めるための「結果式」よりも、求める「過程」を大事にすると良いです。

4人がナイス!しています

ThanksImg質問者からのお礼コメント

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

お礼日時:2012/2/3 0:49

その他の回答(1件)