1

入力で正の整数Nを与え、1からNまで各要素の差が1の配列Aを作成する
1からNまでの間の整数で探索する値をランダムに生成し、探索する値を超えないが最も値が近い配列Aの要素を見つけるプログラムを書いています。

具体的なアルゴリズムの用途には、衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験を想定しています。
高さは最大でNmで、試験に使える生卵に制限があるときに探索回数に制限があると考えられます。

探索回数に制限がない以下のプログラムの場合、計算量はO(logN)ですが、探索回数に制限があるプログラム2の場合、どんなに速くてもO(N)が最速になるでしょうか。

探索回数に制限があるプログラム2の場合、他にもっと計算量が速くなるアルゴリズムがあれば教えていただきたいです。

単純な二分探索で一致する値を配列A内から見つけるプログラム

def solution(N):
    A = []
    for i in range(1, N+1, 1):
        A.append(i)

    target = random.randint(1, N)

    lo = 0
    hi = len(A)-1

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

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

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

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

    return "None"

プログラム2
実行例

#6mの高さから落とせる卵は2個まで
#1/3ずつの高さから1つ目を落としてみる
solution(6, 3, 2)

コード

import random

#探索のうちに探している値を超えていいのはlife-1回までとする

    def solution(N,d,l):
        A = []
        for i in range(1, N+1, 1):
            A.append(i)

        target = random.randint(1, N)
        life = l

        #分母
        denominator = d
        #分子の候補
        numerator = []
        for j in range(1, N-1, 1):
            numerator.append(j)

        #指定された分割数のうち最も小さい位置の値をhiとする
        #k=3なら1/3、K=6なら1/6
        lo = 0
        hi = len(A) * (numerator[0]/denominator)

        #lifeが1になる直前の要素番号を記録する変数
        r = 0

        for x in range(1, len(numerator), 1):
            if life > 1:
                if A[hi] >= target:
                    life = life - 1:
                    r = hi
                else:
                    hi = len(A) * (numerator[x]/denominator)


        #lifeが1になったらlifeが1になる直前までを線形探索
        S = []
        for t in range(r):
            S.append(t)

        #配列内要素とtargetの間の差、仮に初期値100とする
        diff = 100

        #lifeが1になる直前までの区間
        for u in range(len(S)):
            if targe > S[u] and abs(target - S[u]) < diff:
                place = u

            return "位置" + str(place) + "に存在する"

1 件の回答 1

3

目的の値を超えてもいい回数をlife回とすると、life == 1 の時 O(N) ですが、life > 1の時 O(N) より速く解けます

例えば life == 2 の場合
最初に目的の値を超えるまで、sqrt(N) 間隔で調べていき、目的の値を超えたら、最後に超えなかったところから 1 ずつ調べていきます
この時、最初に超えるまでの比較が、O(N / sqrt(N)) ステップかかり、その後のステップが O(sqrt(N)) かかるので全体として O(sqrt(N)) で解けます

これを一般化すると、
life == n (n > 1) の場合
最初に目的の値を超えるまで、step 間隔で調べていき、超えたら、最後に超えなかったから超えたところまでの区間を life <- n - 1 として探索を行うと考えることができます
この時 step <- N ** ((life - 1) / life) とすると、計算量は O(life * (N ** (1 / life))) になります。

この上界の関数は life == log(N) で最小になるので、それより大きな life の時は、life ← log(N) とすることで O(logN) になります。

サンプルコード(質問内の想定用途をもとにコードにしています。質問内のコードとは仕様が違うので注意してください。詳しくはコメント参照)

import random
import math

#昇順に並んだリストAから、targetを超えない最大の値を見つける。ただしtargetの値を超える比較を行えるのはちょうどlife回まで。
#リストのすべての要素がtargetを超えるとき None
def solution(A, target, life):
    if life > math.log(len(A)):
        life = max(1, int(math.log(len(A))))
    lo = 0
    hi = len(A)
    #比較回数と失敗回数の記録用変数、compとfail
    comp = 0
    fail = 0
    for l in range(life, 0, -1):
        step = round((hi - lo) ** ((l - 1) / l))
        for t in range(lo, hi, step):
            comp += 1
            if A[t] > target:
                fail += 1
                hi = t
                break
            else:
                lo = t + 1
        if (hi == lo):
            break
    print("比較回数 = " + str(comp) + ", 失敗回数 = " + str(fail))
    if lo == 0:
        return None
    else:
        return A[lo - 1]

size = 1000000
maxLife = 3
target = random.randint(0, size)
A = range(1, size)
print("target = " + str(target) + ", answer = " + str(solution(A, target, maxLife)))

計算量をもっと厳密に計算したり、目的の値を超えるまでの比較の間隔 step を比較ごとに短くしていくことで計算量が減らせそうですが、複雑なのでやってません。

この質問に回答するには、ログインする必要があります。