0

私は次のコードを与えられ、ビッグ シータ表記で最高および最悪の実行時間を見つけるように言われました。

def find(a, target):
    x = 0
    y = len(a)
    while x < y:
        m = (x+y)/2
        if a[m] < target:
            x = m+1
        elif a[m] > target: 
            y = m
        else:
            return m
    return -1

このコードの最悪の場合の実行時間は O(lg(n)) であることがわかっています。しかし、5 行目を「m=(x+y)/2」から「m=(2*x+y)/3」に変更すると、実行時間は変わるのでしょうか?という質問がありました。

私の直感では、バイナリ検索のようにリストを半分に分割する必要がなくなり、効率が低下するため、実行時間が少し長くなりますが、この時点で大きな O が何であるかを計算する方法がわかりません

4

1 に答える 1

1

最悪の場合、N 要素の配列の最後にある要素を検索しているとしましょう。

最初の繰り返しの後、リストは 2N/3 に減ります。

2 回目の繰り返しの後、リストは 4N/9 に減少します。

. . .

(k-1) 回目の繰り返しの後、リストは 2 つの要素に減らされます

k回目の繰り返しの後、最終的に候補を見つけます。

したがって、N * (power(2/3,k)) = 1 です。

k ~ log (N) を基数 1.5 に

于 2013-09-10T16:40:31.733 に答える