8

出来ますか？そうでない場合、サイズnの配列が与えられた場合、配列を並べ替える方がよいかどうかをどのように知ることができますか？

4

4 に答える 4

9

ソートされていない配列だけでは、劣線形時間でこれを行う方法はありません。どの要素が最大で最小かわからないので、それらすべてを調べる必要があります。したがって、線形時間です。

あなたが見つける最良の種類はそれよりも悪く、おそらくそれに比べてn log n、線形スキャンを行う方が「良い」でしょう。

より多くの情報を保存できる場合は、プロセスを高速化する他の方法があります。次のルールを使用して、最小値と最大値を保存できます。

  • 空のリストに値を追加するときは、minとmaxをその値に設定します。定数時間O（1）。
  • 空でないリストに値を追加するときは、必要に応じてminまたはmaxをその値に設定します。定数時間O（1）。
  • リストから値を削除するときに、削除する値が現在の最小値または最大値と等しい場合は、最小値または最大値を「不明」に設定します。定数時間O（1）。最小/最大とそれらのカウントの両方を保存すると、これをより効率的にすることもできます。つまり、リストに現在の最大値のコピーが7つあり、そのうちの1つを削除した場合、最大値を不明に設定する必要はなく、カウントをデクリメントするだけです。カウントがゼロに達したときにのみ、不明としてマークする必要があります。
  • 空のリストの最小値または最大値を要求する場合は、特別な値を返します。定数時間O（1）。
  • 値がわかっている空でないリストの最小値または最大値を要求する場合は、関連する値を返します。定数時間O（1）。
  • 値が不明な空でないリストの最小値または最大値を要求する場合は、線形検索を実行してそれらを検出し、関連する値を返します。線形時間O（n）。

そのようにすることで、おそらく最小/最大の取得の大部分は一定の時間になります。最小値または最大値である値を削除した場合にのみ、次の取得で1回の取得に線形時間が必要になります。

その後の次の取得は、それらを計算して保存してから一定時間になります。これは、暫定的に最小/最大値を再度削除しないことを前提としています。

最大値の擬似コードは、次のように単純にすることができます。

def initList ():
    list = []
    maxval = 0
    maxcount = 0

上記の初期化コードでは、リストと最大値およびカウントを作成するだけです。最小値とカウントも簡単に追加できます。

リストに追加するには、上記のルールに従います。

def addToList (val):
    list.add (val) error on failure

    # Detect adding to empty list.
    if list.size = 1:
        maxval = val
        maxcount = 1
        return

    # If no maximum known at this point, calc later.
    if maxcount = 0:
        return

    # Adding less than current max, ignore.
    if val < maxval:
        return

    # Adding another of current max, bump up count.
    if val = maxval:
        maxcount += 1
        return

    # Otherwise, new max, set value and count.
    maxval = val
    maxcount = 1

削除は非常に簡単です。値を削除するだけです。それが最大値だった場合は、それらの最大値のカウントをデクリメントします。これは、現在の最大値を知っている場合にのみ意味があることに注意してください。そうでない場合は、計算する必要のある状態になっているので、その状態のままにしてください。

カウントがゼロになると、最大値が不明になったことを示します（すべて削除しました）。

def delFromList (val):
    list.del (val) error on failure

    # Decrement count if max is known and the value is max.
    # The count will become 0 when all maxes deleted.
    if maxcount > 0 and val = maxval:
        maxcount -= 1

最大値を取得するには、いつ計算する必要があるか（maxcountがゼロの場合）を知る必要があります。計算する必要がない場合は、次のように返します。

def getMax ():
    # raise exception if list empty.
    error if list.size = 0

    # If maximum unknown, calculate it on demand.
    if maxcount = 0:
        maxval = list[0]
        for each val in list:
            if val = maxval:
                maxcount += 1
            elsif val > maxval:
                maxval = val
                maxcount = 1

    # Now it is known, just return it.
    return maxval

その擬似コードはすべて、一見グローバル変数、、、listおよびmaxvalを使用しmaxcountます。適切に設計されたシステムでは、もちろんインスタンス変数になるため、複数のリストを並べて実行できます。

于 2011-12-04T10:31:15.277 に答える
5

一般的な質問を考えると：

並べ替えられていない配列の最大/最小値を劣線形時間で見つけることはできますか？

これを実現するメカニズムは想像できません。

However, if you keep a reference to the min and max value and update the values on every insert / append / replace operation, the amortized cost of min / max lookups can be very cheap.

Sorting the array is very expensive compared to a simple linear scan to find the min and max, so only sort if there is some other benefit. (Of course, insertion sort can provide very similar properties to updating the min and max values on every insert / append / replace operation, so it might be acceptable enough.)

于 2011-12-04T09:58:29.063 に答える
2

ソートされていない配列の場合、最小/最大の複雑さはO（N）です。それを上回る方法はありません。ソートされた配列0（1）の場合、ソートは0 {N log N）です。最小/最大を検索する必要がある場合は、1つだけ、またはその近くで並べ替えるのは役に立ちません。ただし、この操作を何度も実行する場合は、検索の線形時間を回避するために、Rbツリーやヒープなどの検索構造の一部を調べて日付を再編成してください。

于 2011-12-04T09:59:43.440 に答える
0

この完全な回答（C ++コードを使用）で私はここで見つけました-数値の配列から最小値または最大値を取得するための最良の方法は何ですか -com-比較の総数がnの場合は3n/2-2であることを明確に示していますは偶数です（奇数の場合、定数は3/2です）。

したがって、十分に大きいnに対して効果がない2つの定数（3/2の修飾子と-2）を無視した後、それは明らかにO（n）に属し、複雑さの点では線形ですが、効率の点では線形です（そう言う）それは1.5nであり、非常に優れています

于 2012-11-24T10:49:50.243 に答える