Q&A
一つ言い忘れました。epistemeさんがおっしゃるように「計算量は同じ」と思います。係数が違うだけなので。
前提・実現したいこと
二分探索法で中点以外を分割点としたアルゴリズムの計算量を明らかにしようとしています。
今回は中点ではなく、1:2に分ける点を分割点とした二分探索を考えています。
中点を分割点とする二分探索法の計算量はO(log n)ですが、1:2に分ける点を分割点とした場合はどのようになるのか知りたいです。
発生している問題・エラーメッセージ
やってみたこととして、分割の仕方によって探している値にたどり着くまでに計算する分割点の回数に違いがあるか確認しました。
しかし、探す値が配列のどの位置にあるかによって回数の差の傾向はバラバラで
・中点を分割点とする場合と1:2に分ける点を分割点とする場合の二分探索法どちらが速いのか
・1:2に分ける点を分割点とする二分探索法の計算量の求め方
がわからず困っています。
該当のソースコード
中点を分割点として選ぶ二分探索法
python
1def solution(A, N): 2 lo = 0 3 hi = len(A)-1 4 5 while hi>lo: 6 mid = round((hi+lo)/2) 7 8 if A[mid] == N: 9 return "位置" + str(mid) + "に存在する" 10 11 elif A[mid] >= N: 12 hi = mid -1 13 14 elif A[mid] < N: 15 lo = mid + 1 16 17 return "None"
1:2に分ける点を分割点として選ぶ二分探索法
python
1def solution(A, N): 2 lo = 0 3 hi = len(A)-1 4 5 while hi>lo: 6 point = round(2*lo/3 + hi/3) 7 print('point =' + str(point)) 8 9 if A[point] == N: 10 return "位置" + str(point) + "に存在する" 11 12 elif A[point] >= N: 13 hi = point -1 14 15 elif A[point] < N: 16 lo = point + 1 17 18 return "None"
試したこと
A = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
N1 = 9
N2 = 17
とした時のそれぞれの分割点の変遷を確認しました。
中点を分割点としたときは
N1 mid =10 mid =4 mid =7 mid =8 N2 mid =10 mid =16
一方で1:2に分割した時は
N1 point =4 point =7 point =9 N2 point =7 point =12 point =15 point =17
補足情報（FW/ツールのバージョンなど）
python 3.6
回答3件
0
ベストアンサー
まずド真ん中で分割すると。
1/2の確率で上1/2
1/2の確率で下1/2
だから一回の操作で検索対象は 1/21/2 + 1/21/2 = 1/2 になる
[1] すると計算量は 2/1を底としたlog
1:2で分割すると
1/3の確率で上1/3
2/3の確率で下2/3
だから一回の操作で検索対象は 1/31/3 + 2/32/3 = 5/9
[2] すると計算量は 9/5を底としたlog
[1] = 定数倍の[2] だから
計算量はどちらも O(logN)
...じゃないかしら。
投稿2019/05/03 02:29
総合スコア16614
0
1/2の点で分割すると・・・
配列の前後にあるデータの割合は1/2, 1/2
前半にあったときは分割後のサーチ範囲は1/2, 後半にあったときは1/2
∴任意の数について1回目の分割で見つからなかった場合次の分割後のサーチ範囲の平均は
1/2 * 1/2 + 1/2 * 1/2 = 1/2
1/3の点で分割すると・・・
配列の前後にあるデータの割合は1/3, 2/3
前半にあったときは分割後のサーチ範囲は1/3, 後半にあったときは2/3
∴任意の数について1回目の分割で見つからなかった場合次の分割後のサーチ範囲の平均は
1/3 * 1/3 + 2/3 * 2/3 = 5/9
それ以降も同様です。
分割後のサーチ範囲は1/3で分割した方が1/2で分割したときに比べて1/18だけ長いということになります。
サーチ対象の数値を次の^の位置と考えてそれらの平均的なサーチ回数を求めるには・・・
text
1 n0 n1 n2 n3 ... 2^ ^ ^ ^ ^ ^ ^ ^ ^ ...
このあたりになると自分は正しい結果をささっと出す自身がなくなってくるので「えーと、まぁ計算機で実際にやらせてみよっかな」とか思ってしまいます。数学はそれほど得意じゃないのです。
質問者さんのコードのsolutionに分割点の位置を追加し、戻り値を「見つかったかどうか」「サーチ回数」として入力データの長さとサーチする値を規則的に変化させ、結果を蓄積した上で、それぞれの平均サーチ回数の比を求めたりグラフにプロットしたりします。
比率を求めてみると1/2分割の平均サーチ回数と1/3のそれの比率はいつも大体同じある一定の比率になるみたいに見えました。質問者さんもそういうふうにして「プログラムを動かした結果を目でみてどうこうする」のではなく「プログラム自体に平均回数を計算させる」ようなことを考えるとよいと思います（プログラミングの練習としてですが）。
投稿2019/05/03 04:07
総合スコア18394
ご回答いただきましてありがとうございます。
定数倍のちがいは、オーダ表記の規則によると計算量がどちらも同じなのは理解できました。
epistemeさんとKSwordOfHasteさんのご回答を受けて、一点伺いたいことがあります。サーチ範囲の平均値についてですです。
最悪の計算量を想定すると1:1での２分割の場合は、前半後半のどちらも1/2ですが、1:2の場合は異なるので、後半ばかりに探している値の範囲が該当する場合はサーチを繰り返すと平均の5/9よりも悪い値になるのではないでしょうか。
計算量に加えて係数の具合についても気にしておられるような印象を受けたのでこんな回答を書いてみました。本来計算量を評価するならいちいち細かな係数は問題にせずepistemeさんのような考え方でさくっと出すのが普通と思います。epistemeさんの評価ポイントが高いのはつまりはそういう意味だと思います！
> 平均の5/9よりも悪い値になる
もちろんそうです。最悪は2/3になります。
ご説明いただきましてありがとうございました。
0
ヒント：1:1では毎回検索範囲が半分になります。1:2では検索範囲は3/2です。・・・分かりますか？
投稿2019/05/03 02:25
総合スコア6851
ヒントをいただきましてありがとうございます。
範囲としては1:1分割の場合1/2→1/4→1/8と狭まっていくと思いますが、1:2では3/2ということは増えているということでしょうか？3/２の意味についてもう少し詳しくお聞きしたいです。
計算量は最悪の場合を想定するので、1:2に分割するときにいつも2/3の方に探したい値があるとすると、2/3→4/9→8/27と範囲が狭まっていくと考えられないのでしょうか？
worst-caseでもやっぱり O(logN) だよね。
> 1:2では3/2ということは増えているということでしょうか？
違う。そうだとすると"いつまでも終わらない"ことになる。
一回ごとに検索対象の数が 2/3 になるんだから、計算量はその逆数(3/2)を底としたO(logN)
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2019/05/04 04:47