4

double を入れて取り出す fifo クエリがあります。各更新の後、最大値と最小値が必要です。クエリでこれらの値の位置 (またはインデックス) は必要ありません。それを効果的に行う方法は？log(N) またはおそらく O(1)?

upd: これが見つかりました push_rear()、pop_front()、および get_min() がすべて一定時間の操作であるキューを実装します

4

2 に答える 2

3

これは難しい質問です。次の点を考慮してください。

任意の時点での fifo のサイズが N であるとします。浮動小数のペアだけで最小値と最大値を追跡するとします。fifo のサイズは適度に一定のままであるとします。

したがって、キューの 1 つの「操作」は、論理的に 1 つのプッシュと 1 つのポップで構成されていると想定できます。

これを処理する 2 つの方法を比較しているとします。1 つはヒープ ペアを使用し、もう 1 つは単純な比較と検索を使用します。

ヒープ メソッドの場合:

各操作では、リストと両方のヒープにプッシュしてから、リストと両方のヒープからポップします。ヒープ操作は常に O(log(n)) であり、リスト操作は O(1) であるため、N が大きいため、1 つの操作の時間計算量は平均的なケースで O(log(N)) になります。現在ポップされている要素が最小要素であるか最大要素であるかに関係なく、ヒープ操作は常にこの複雑さであることに注意することが重要です。したがって、N 操作の時間の複雑さは O(N*log(N)) です。

単純な方法の場合:

各操作では、リストをプッシュしてポップし、ポップされたアイテムを保存されている最小値と最大値と比較します。アイテムがいずれかのアイテムと同じである場合は、次善の要素が見つかるまで、同じ値のアイテムを探すか (この場合は早期にブレークします)、リストの残り全体を検索します。次に、最小/最大を次善の値で更新します。このメソッドには、O(1) の典型的なケースと O(N) の最悪のケースがあります (最小または最大を更新する必要があります)。N 数の範囲によっては、最小値と最大値を更新する必要がある回数が定数になり、更新しない回数が N になることに注意することが重要です。したがって、N 操作の時間の複雑さは次のとおりです。オン）。単純なケースは、実際にはより高度なソリューションよりも優れています。

とはいえ、ヒープで要素を効率的に削除できるとは思わないので、その方法では多くの問題が発生します。

したがって、次の擬似コードを検討してください。

queue fifo;
float min, max;

void push(float f)
{
    if (fifo.size == 0)
    {
        min = f;
        max = f;
    }
    else if (f > max) max = f;
    else if (f < min) min = f;

    fifo.push(f);
}

float pop()
{
    if (fifo.size == 0) return (*((float *)NULL)); // explode
    float f = fifo.pop();
    if (fifo.size == 0)
    {
        min = NaN;
        max = NaN;
        return f;
    }
    if (f == max) search_max(fifo);
    if (f == min) search_min(fifo);
    return f;
}

search_max(queue q)
{
    float f = min;
    for (element in q)
    {
        if (element == max) return;
        if (element > f) f = element;
    }
    max = f;
}

search_min(queue q)
{
    float f = max;
    for (element in q)
    {
        if (element == min) return;
        if (element < f) f = element;
    }
    min = f;
}
于 2012-07-19T18:53:53.697 に答える
0

ヒープ ( http://en.wikipedia.org/wiki/Heap_%28data_structure%29 )を使用するのはどうですか。2 つのヒープを持つことができます。1 つは最小値を抽出するためのもので、もう 1 つは最大値を抽出するためのものです (1 つのヒープで最小値と最大値を同時に抽出することはできないため)。また、スペースのオーバーヘッドも必要なく、Big O は log n です。

于 2012-07-19T18:38:58.467 に答える