二分探索のアルゴリズム

分からない問題があります。

・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。
・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。

２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが
そのようになる説明をどのようにしたらいいか。また logn<n となるのは
わかるのですが理由をどう説明したらいいのか分かりません。
どなたかお教え下さい。

No.2 ベストアンサー 回答者： nozooo 回答日時： 2011/06/17 19:11

あるソートされたデータについて、データ数n、計算量xとすると

線形探索ではデータ数nに比例して処理が増えるので
x = n
より、時間計算量はO(n)となります。
二分探索ではデータ数を半分にして、その前半か後半のどちらかを探索する処理を再帰的に繰り返すことになるので、
2^x = n
の関係が成り立ち両辺に２を底とする対数を取ると
x = logn
より、時間計算量はO(logn)となります。

No.1 回答者： 178-tall 回答日時： 2011/06/17 19:06

わかるけど説明できないというのは、実は、よくわかってないのでは…？

二分探索は、対象順序の配列で既に工数を食ってるはずで、線形探索よりも探索計算量が減るのは当たり前…。

・二分探索は、対象の順序配列の中央値を見て、その前後いずれの半分に探索対象があるかを選んでいくので、1 ステップごとに対象個数が半減しますね。
はじめの対象個数が N なら、所要探索回数は Log_2(N) 。

・線形探索は、何のことはない、端から一つひとつつぶしていくだけなので、所要探索回数は対象個数 N に比例。