54740


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

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

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

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

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

[code]

    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"
    
[/code]

プログラム2  
実行例

[code]

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

コード

[code]

    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が１になる直前の要素番号を記録する変数
            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が１になったらlifeが１になる直前までを線形探索
            S = []
            for t in range(r):
                S.append(t)
    
            #配列内要素とtargetの間の差、仮に初期値100とする
            diff = 100
    
            #lifeが１になる直前までの区間
            for u in range(len(S)):
                if targe > S[u] and abs(target - S[u]) < diff:
                    place = u
    
                return "位置" + str(place) + "に存在する"
    
[/code]


CC BY-SA 4.0
2019-05-04T14:00:04.377
54716
2019-05-05T17:16:05.953
question
python python3 アルゴリズム 計算量
耐久試験を想定したアルゴリズムにおいて計算量を減らす方法


目的の値を超えてもいい回数を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)
になります。

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

[code]

    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)))
    
[/code]

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


CC BY-SA 4.0
2019-05-05T10:07:49.030
54740
2019-05-05T17:16:05.953
2019-05-05T17:16:05.953
33033
33033
54716
answer