arrays - 配列内の極小値を見つける

Question

整数の配列が与えられたら、極小値を見つけます。要素A[i]は、A [i-1]>A[i]およびA[i]<A [i + 1]の場合、極小値として定義されます。ここで、i = 1...n-2です。境界要素の場合、その数は隣接する数よりもわずかに小さい必要があります。

極小値が1つしかない場合は、修正された二分探索で解くことができます。しかし、配列に複数の極小値が存在することがわかっている場合、それはO(log n)時間内に解決できますか？

Answer 1

配列要素が明確であることが保証されていない場合、O（log n）時間でこれを行うことはできません。この理由は次のとおりです。すべてのn>1の値が同じである配列があるとします。この場合、隣接する要素よりも小さい要素はないため、どの要素も極小値にすることはできません。ただし、すべての値が同じであると判断するには、すべての配列要素を調べる必要があります。これにはO（n）時間がかかります。使用する時間がO（n）未満の場合、必ずしもすべての配列要素を確認できるとは限りません。

一方、配列要素が明確であることが保証されている場合は、次の観測値を使用して、O（log n）時間でこれを解決できます。

1. 要素が1つしかない場合は、極小値であることが保証されます。
2. 複数の要素がある場合は、真ん中の要素を見てください。極小値であれば、これで完了です。それ以外の場合は、その隣の要素の少なくとも1つをそれより小さくする必要があります。ここで、小さい要素の1つから始めて、中央の要素から離れる方向に配列の端の1つに向かって徐々に移動するとどうなるか想像してみてください。各ステップで、次の要素が前の要素よりも小さいか、大きくなります。最終的には、この方法で配列の最後に到達するか、極小値に到達します。これはあなたができることを意味することに注意してくださいこれを実行して、極小値を見つけます。ただし、実際にはそうしません。代わりに、配列の半分を破棄する理由として、配列のこの半分に極小値が存在するという事実を使用します。残っているものでは、極小値を見つけることが保証されています。

したがって、次の再帰的アルゴリズムを構築できます。

1. 配列要素が1つしかない場合、それは極小値です。
2. 配列要素が2つある場合は、それぞれを確認してください。1つは極小でなければなりません。
3. それ以外の場合は、配列の中央の要素を確認してください。極小の場合は返却してください。それ以外の場合、少なくとも1つの隣接する値はこれよりも小さくする必要があります。その小さい要素を含む配列の半分で再帰します（中央ではありません）。

これには漸化式があることに注意してください

T（1）≤1

T（2）≤1

T（n）≤T（n / 2）+ 1

マスター定理を使用すると、必要に応じて、このアルゴリズムが時間O（log n）で実行されることを示すことができます。

お役に立てれば！

また、このアルゴリズムは、配列のエッジが隣接する要素よりも小さい場合に極小値としてカウントされる場合にのみ機能することに注意してください。

Answer 2

極小値の数は次のようになりn/2ます。それらすべてを時間内に列挙することはできませんO(log n)。

Answer 3

あなたのアルゴリズムはこの配列では機能しません

15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1

ここで極小値は 12 です..しかし、7 である中央の要素をチェックすると、アルゴリズムは左半分 (最小値を持つ) を破棄し、右半分をチェックインします。したがって、機能しません

配列が A[1] ≥ A[2] および A[n − 1] ≤ A[n] という特別なプロパティを持つ特別なケースでのみ機能すると思います。

Answer 4

実際、以前のアルゴリズムを変更して、O(log n) 時間ですべての最大値を取得できます。提供されたすべての入力に対してうまく機能することをテストしました。フィードバックをお寄せください

public class LocalMaximas {

@Test
public void test () {
    System.out.println("maximas: please modify code to handle if array size is <= 2");

    int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59,2};
    localMaximas(a);

    int []b = {9,7,2,8,5,6,3,4, 2}; //9,8,6,4
    localMaximas(b);

    int [] c= {15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1};//15,20
    localMaximas(c);
}

public  void localMaximas (int [] a) {
    System.out.println("\n\n");
    if(isMaxima(a,0)) {
        System.out.println(a[0]);
    }
    if(isMaxima(a,a.length-1)) {
        System.out.println(a[a.length-1]);
    }
    localMaximas(a,0,a.length-1);
}

int localMaximas(int []a,int low, int high) {
    int mid = (low+high)/2;
    if(high-low > 3) {     // more than 4 items in currently  divided array
        if(isMaxima(a,mid)) {
            System.out.println(a[mid]);
        }   
        localMaximas(a,low, mid);
        localMaximas(a,mid, high);
    }
    else if(high-low == 3){ //exactly 4 items in currently  divided array
        localMaximas(a,low, mid+1);
        localMaximas(a,mid, high);
    }   
    else if((high-low == 2) && (isMaxima(a,low+1))) {
        System.out.println(a[low+1]);
    }
    return 0;
}

int maxof(int []a, int i, int j) {
    if(a[i] <a[j]) {
        return j;
    }
    else {
        return i;
    }
}

boolean isMaxima(int []a ,int mid) {
    if(mid == 0) {
        if(maxof(a, mid, mid+1) == mid) {
            return true;
        }
        else {
            return false;
        }
    }
    else if(mid==a.length-1) {
        if(maxof(a,mid,mid-1) == mid) {
            return true;
        }
        else {
            return false;
        }
    }
    else {
        if((maxof(a, mid, mid+1) == mid) && (maxof(a, mid, mid-1) == mid)) {
            return true;
        }
        else {
            return false;
        }           
    }
}
}