Skip to main content
1 / 2
yudedako
  • 691
  • 1
  • 4
  • 8

目的の値を超えてもいい回数を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を超えるとき -1
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 + 1
                break
            else:
                lo = t + 1
        if (hi == lo):
            break
    print("比較回数 = " + str(comp) + ", 失敗回数 = " + str(fail))
    if lo == 0:
        return -1
    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 を比較ごとに短くしていくことで計算量が減らせそうですが、複雑なのでやってません。

yudedako
  • 691
  • 1
  • 4
  • 8