4

大きな配列内の k 要素の連続する各サブ配列の最大要素を返すことができるアルゴリズムを作成し、これらの最大要素を独自の配列に読み込むことができる問題に直面しています。

Given int array = {3, 7, 20, 6, 12, 2, 0, 99, 5, 16}, and int k = 4,
--> creates the array {20, 20, 20, 12, 99, 99, 99} 
[because there are 7 consecutive sub-arrays of size 4 within the given array:
{3, 7, 20, 6}, {7, 20, 6, 12}, {20, 6, 12, 2}, ... , {0, 99, 5, 16}
and the max element of these, respectively, is 20, 20, 20, ..., 99 which 
are read into the resulting array.

ここに私の問題があります：これをO（n ^ 2）の複雑さで実装する方法は知っていますが、O（n）になるように高速化したい、またはそれが不可能な場合はO（nlog（n）） . これを行うためのより速い方法があるかどうか、誰かが知っていますか?もしそうなら、どのように?

4

1 に答える 1

1

まず、単純なアルゴリズムの複雑さはO(k(n-k+1)) (通常、これはO(kn)に近似されます) であり、O(n^2)ではありません。ここで、連続するサブアレイ (可能なn-k+1の) ごとに、 k回の比較を実行する必要があります。

と呼ぶことができる長さkの追加の配列を使用して、いくつかのメモ化を行うことで、これよりもうまくいくことができます。その配列は、次の最大値のインデックスを格納します。maximums

データセットを反復するたびに、 の最初の要素を調べますmaximums。「期限切れの」インデックスを削除すると、最初の要素が現在の反復の答えになります。

ウィンドウ (サイズk ) をデータ上でスライドするとき、現在のインデックスを にプッシュし、maximums次のようにプルーニングします: indexの値は index の値より小さくmaximums[i] なければmaximums[i-1]なりません。maximumsそうでない場合は、これが true になるまで、一度に 1 スポットずつの先頭に向かってインデックスをバブリングし続けます。

実際には、maximums配列をリング バッファーとして扱うのが最善です。プルーニング プロセスはテールをヘッドに向かって縮めますが、「期限切れの」最大値をポップすると (ウィンドウがそれらを過ぎてスライドするとき)、ヘッドが 1 ステップ進みます。

少し不格好ですが、説明するための実用的なコードを次に示します。

#include <vector>
#include <iostream>

int main()
{
    const int window_size = 4;
    std::vector<int> vals = { 3, 7, 20, 6, 12, 2, 0, 99, 5, 16 };
    std::vector<int> maximums( window_size );
    int mhead = 0, mtail = 0;

    for( int i = 1; i < vals.size(); i ++ )
    {
        // Clean out expired maximum.
        if( maximums[mhead] + window_size <= i )
        {
            int next_mhead = (mhead + 1) % window_size;
            if( mtail == mhead ) mtail = next_mhead;
            mhead = next_mhead;
        }

        if( vals[i] >= vals[ maximums[mtail] ] )
        {
            // Replace and bubble up a new maximum value.
            maximums[mtail] = i;
            while( mhead != mtail && vals[ maximums[mtail] ] >= vals[ maximums[(mtail+window_size-1)%window_size] ] )
            {
                int prev_mtail = (mtail + window_size - 1) % window_size;
                maximums[prev_mtail] = maximums[mtail];
                mtail = prev_mtail;
            }
        }
        else
        {
            // Add a new non-maximum.
            mtail = (mtail + 1) % window_size;
            maximums[mtail] = i;
        }

        // Output current maximum.
        if( i >= window_size - 1 )
        {
            std::cout << vals[ maximums[mhead] ] << " ";
        }
    }

    std::cout << std::endl;
    return 0;
}

さて、時間の複雑さ...

最良のケースはO(n)です。これは、すべてのデータが (昇順または降順で) 並べ替えられている場合に発生します。

最悪のケースはO(2n)だと思います。1 回の反復でk 個の余分な操作を必要とする唯一の方法は、(リング バッファーがいっぱいになるように) 線形複雑度のkステップが既にある場合です。このような場合、リング バッファは次のステップのために空になります。リング バッファをいっぱいにして空にできるのはn/k回だけなので、これらの時折のk回の操作はkn/kまたはちょうどnで行われます。

リング バッファーを常に部分的に空にすることでさえ、同じ複雑さをもたらすことを示すことができるはずです。

そして最後に、すべてをまとめてO(n)と呼ぶことができます。これは、定数係数が大きなn に対して重要でなくなるためです。実際、思ったよりもうまくいきました。=)

于 2016-02-15T07:17:04.093 に答える