4

比較モデルに基づくソートアルゴリズムには、nlogn、つまり Omega(nlogn) の下限があることがわかっています。数学的に証明できること。

しかし、ご存知のように、オランダの旗の問題は 3 つの異なる要素 (繰り返し使用される) を O(n) 時間でソートできます。これも比較モデルに基づいていますが、O(n) 時間でソートできます。では、比較モデルに基づいてソートの下限を正当化するにはどうすればよいでしょうか。

違いを理解するのを手伝ってください.....

ありがとう

4

5 に答える 5

3

私の意見では、これは下限の関連する「矛盾」ではありません. O(N*logN) よりも高速なアルゴリズムを見つけるために悪用されます。これは、一般的な比較ベースの並べ替えアルゴリズム (つまり、シーケンスの内容に関する情報がない場合) の下限です。

一般に、N 個の要素が 0..K の範囲内にあり、K < N の場合、カウントソートのような非比較ソートを効率的に利用して、O(N) の問題を解決できます。

于 2012-01-23T11:23:34.870 に答える
2

境界は、任意の要素Omega(n log n)の比較ベースの並べ替えの下限を示します。

オランダの旗の問題が考慮しているのは、任意の要素がなく、要素ごとに 3 つのオプションしかない場合です。

したがって、Omega(n log n)制限は追加の制約なしで、一般的に問題に適用されます。ただし、他の制約 (たとえば、各要素に 3 つのオプションしかないなど) を課すと、他の制約を適用できる特定のケースを検討するだけで、この境界よりも優れたアルゴリズムを見つけることができる可能性があります。ヒューリスティックなど

于 2012-01-23T11:26:26.960 に答える
1

ポイントは、オランダの国旗セットは完全に順序付けられていないということです。多くの等しい要素があります。実際、個別のオブジェクトを数えると、(最大で) サイズ 3 のセットになります。

Omega(n log n)境界が難しいのは、オブジェクトとaどちらbかa<bがb>a保持されている場合のみです (別名:すべてのオブジェクトが個別です) 。

O(0)実際、すべてのオブジェクトが でなければならないときに、 でソートできますnull。

少なくとも 2 つの別個のオブジェクトがあると仮定すると、適切な境界は、 がオブジェクトの数であり、 が別個のオブジェクト (ソートが等しくない)の数Omega(n log m)であるようなものだと思います。簡単に言えば、出力バケットを見つけるために必要な決定の数です。一般的なケースでは、等しいオブジェクトの量が少ない場合。オランダ国旗問題では、.nmlog mO(log m)=O(log n)m=3

基数ソートはこれを別の方法で利用します。また、線形であると見なされます。log mただし、データを渡す必要があります。ここmで、 は異なる可能性のある要素の数です。したがって、実際には基数ソートも でありOmega(n log m)、mは識別できるオブジェクトの数です。

于 2012-01-23T11:31:43.860 に答える
0

オランダの旗の問題は、パーティション分割アルゴリズムに近いものです。

これは、並べ替えの最初のステップにすぎません。（パーティションに何度も適用することで）ソートに使用できますが、最終的には Omega(nlogn) になると思います。

異なる値の数 (フラグの場合は 3) とその値 (青、白、赤) を知ることは非常にまれなケースです。

于 2012-01-23T11:38:22.920 に答える
0

オランダの旗の問題には、通常の並べ替えよりもいくつかの基本的なデータがあり、3 つの異なる値があることを認識しており、ウィキペディアのアルゴリズムのページを見ると、次のようになります。

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

実際には、要素のペア間の比較を使用せず、下限/中/上限と要素間の比較を使用しただけであり、通常の並べ替えで使用される他の比較方法とは無関係であり、Counting Sort と比較できます。

于 2012-01-23T11:30:50.100 に答える