0

探している要素が現れる 2^n-1 要素の並べ替えられた配列の二分探索の場合、償却された最悪の場合の時間計算量はどれくらいですか?

これは私の最終試験の復習シートで見つけました。最悪のケースは O(log n) であるため、二分探索に償却された時間の複雑さが必要な理由もわかりません。私のメモによると、償却コストはアルゴリズムの上限を計算し、それをアイテムの数で割るので、最悪の場合の時間の複雑さを n で割ったもの、つまり O(log n )/2^n-1?

参考までに、私が使用している二分探索は次のとおりです。

public static boolean binarySearch(int x, int[] sorted) {
    int s = 0; //start
    int e = sorted.length-1; //end

    while(s <= e) {
        int mid = s + (e-s)/2;
        if( sorted[mid] == x )
            return true;
        else if( sorted[mid] < x )
            start = mid+1;
        else
            end = mid-1;
    }
    return false;
}
4

2 に答える 2

0

iAmortized cost は、考えられるすべてのクエリの合計コストを、考えられるクエリの数で割ったものです。アイテムを見つけられなかったクエリをどのようにカウントするかによって、わずかに異なる結果が得られます。(まったくカウントしないか、不足している可能性のあるギャップごとに 1 つカウントします。)

したがって、2^n - 1 項目の検索の場合 (数学を単純にするための例として)、最初のプローブで 1 つの項目が見つかり、2 番目のプローブで 2 項目が見つかり、3 番目のプローブで 4 項目が見つかります。 , ... n 番目のプローブで 2^(n-1)。不足しているアイテムには 2^n の「ギャップ」があります (両端をギャップとして数えることを忘れないでください)。

あなたのアルゴリズムでは、プローブ k でアイテムを見つけるのに 2k-1 の比較コストがかかります。(これは、k 番目より前の k-1 個のプローブのそれぞれについて 2 回の比較に加えて、== のテストが true を返す場合に 1 回です。) テーブルにない項目を検索するには、2n 回の比較が必要です。

計算はあなたに任せますが、二分探索がこのようにコーディングされているのを見て、私がどれほど腹立たしいかを表現せずにこのトピックを離れることはできません。検討：

public static boolean binarySearch(int x, int[] sorted {
    int s = 0; // start
    int e = sorted.length; // end

    // Loop invariant: if x is at sorted[k] then s <= k < e

    int mid = (s + e)/2;
    while (mid != s) {
        if (sorted[mid] > x) e = mid; else s = mid;
        mid = (s + e)/2; }
    return (mid < e) && (sorted[mid] == x); // mid == e means the array was empty
    }

探しているアイテムにヒットしたときにループを短絡させませんが、これは欠陥のように見えますが、一方で、アイテムごとに 2 つの比較ではなく、見るすべてのアイテムに対して 1 つの比較のみを行います。それは一致しません。すべてのアイテムの半分が検索ツリーのリーフで見つかるため、欠陥のように見えるものが大きな利益になることがわかります。実際、ループを短絡することが有益な要素の数は、配列内の要素数の平方根にすぎません。

算術を精査し、償却された検索コストを計算します (「コスト」をsorted[mid]との比較の数としてカウントすると、このバージョンは約 2 倍高速であることがわかります。コストも一定です (±1 比較以内)。 , 配列内のアイテムの数のみに依存し、アイテムがどこにあるか、またはアイテムが見つかったかどうかにも依存しません.それは重要ではありません.

于 2014-12-08T19:59:04.617 に答える
0

正直なところ、これが何を意味するのかわかりません。償却が二分探索とどのように相互作用するのかわかりません。

おそらく問題は、成功した二分探索の平均コストがいくらになるかということです。配列の n 要素すべてをバイナリ検索し、そのような操作の平均コストを調べることを想像できます。その場合、検索で 1 つのプローブが作成される 1 つの要素、検索で 2 つのプローブが作成される 2 つの要素、3 つのプローブが作成される 4 つの要素などがあります。これは平均すると O(log n) になります。

お役に立てれば！

于 2014-12-08T19:43:06.180 に答える