質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.78%

二分探索法で中点以外を分割点としたアルゴリズムの計算量

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 661

tenjin

score 270

前提・実現したいこと

二分探索法で中点以外を分割点としたアルゴリズムの計算量を明らかにしようとしています。
今回は中点ではなく、1:2に分ける点を分割点とした二分探索を考えています。
中点を分割点とする二分探索法の計算量はO(log n)ですが、1:2に分ける点を分割点とした場合はどのようになるのか知りたいです。

発生している問題・エラーメッセージ

やってみたこととして、分割の仕方によって探している値にたどり着くまでに計算する分割点の回数に違いがあるか確認しました。

しかし、探す値が配列のどの位置にあるかによって回数の差の傾向はバラバラで
・中点を分割点とする場合と1:2に分ける点を分割点とする場合の二分探索法どちらが速いのか
・1:2に分ける点を分割点とする二分探索法の計算量の求め方

がわからず困っています。

該当のソースコード

中点を分割点として選ぶ二分探索法

def solution(A, N):
    lo = 0
    hi = len(A)-1

    while hi>lo:
        mid = round((hi+lo)/2)

        if A[mid] == N:
            return "位置" + str(mid) + "に存在する"

        elif A[mid] >= N:
            hi = mid -1

        elif A[mid] < N:
            lo = mid + 1

    return "None"

1:2に分ける点を分割点として選ぶ二分探索法

def solution(A, N):
    lo = 0
    hi = len(A)-1

    while hi>lo:
        point = round(2*lo/3 + hi/3)
        print('point =' + str(point))

        if A[point] == N:
            return "位置" + str(point) + "に存在する"

        elif A[point] >= N:
            hi = point -1

        elif A[point] < N:
            lo = point + 1

    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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+5

まずド真ん中で分割すると。
1/2の確率で上1/2
1/2の確率で下1/2
だから一回の操作で検索対象は 1/2*1/2 + 1/2*1/2 = 1/2 になる
[1] すると計算量は 2/1を底としたlog 

1:2で分割すると
1/3の確率で上1/3
2/3の確率で下2/3
だから一回の操作で検索対象は 1/3*1/3 + 2/3*2/3 = 5/9
[2] すると計算量は 9/5を底としたlog 

[1] = 定数倍の[2] だから
計算量はどちらも O(logN)

...じゃないかしら。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/04 13:47

    ご回答と補足をありがとうございました。

    キャンセル

+2

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だけ長いということになります。

サーチ対象の数値を次の^の位置と考えてそれらの平均的なサーチ回数を求めるには・・・

  n0   n1   n2   n3   ...
^ ^  ^ ^  ^ ^  ^ ^  ^ ...

このあたりになると自分は正しい結果をささっと出す自身がなくなってくるので「えーと、まぁ計算機で実際にやらせてみよっかな」とか思ってしまいます。数学はそれほど得意じゃないのです。

質問者さんのコードのsolutionに分割点の位置を追加し、戻り値を「見つかったかどうか」「サーチ回数」として入力データの長さとサーチする値を規則的に変化させ、結果を蓄積した上で、それぞれの平均サーチ回数の比を求めたりグラフにプロットしたりします。

fig

比率を求めてみると1/2分割の平均サーチ回数と1/3のそれの比率はいつも大体同じある一定の比率になるみたいに見えました。質問者さんもそういうふうにして「プログラムを動かした結果を目でみてどうこうする」のではなく「プログラム自体に平均回数を計算させる」ようなことを考えるとよいと思います(プログラミングの練習としてですが)。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/03 13:31

    計算量に加えて係数の具合についても気にしておられるような印象を受けたのでこんな回答を書いてみました。本来計算量を評価するならいちいち細かな係数は問題にせずepistemeさんのような考え方でさくっと出すのが普通と思います。epistemeさんの評価ポイントが高いのはつまりはそういう意味だと思います!

    キャンセル

  • 2019/05/03 13:33

    > 平均の5/9よりも悪い値になる
    もちろんそうです。最悪は2/3になります。

    キャンセル

  • 2019/05/04 13:54

    ご説明いただきましてありがとうございました。

    キャンセル

0

ヒント:1:1では毎回検索範囲が半分になります。1:2では検索範囲は3/2です。・・・分かりますか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/03 12:58

    ヒントをいただきましてありがとうございます。
    範囲としては1:1分割の場合1/2→1/4→1/8と狭まっていくと思いますが、1:2では3/2ということは増えているということでしょうか?3/2の意味についてもう少し詳しくお聞きしたいです。

    キャンセル

  • 2019/05/03 13:19

    計算量は最悪の場合を想定するので、1:2に分割するときにいつも2/3の方に探したい値があるとすると、2/3→4/9→8/27と範囲が狭まっていくと考えられないのでしょうか?

    キャンセル

  • 2019/05/03 19:19

    worst-caseでもやっぱり O(logN) だよね。

    キャンセル

  • 2019/05/03 19:50

    > 1:2では3/2ということは増えているということでしょうか?
    違う。そうだとすると"いつまでも終わらない"ことになる。
    一回ごとに検索対象の数が 2/3 になるんだから、計算量はその逆数(3/2)を底としたO(logN)

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.78%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る