12

私は、適切なピボット要素を選択するためのSelectアルゴリズムに基づくクイックソートバリアントの実装に取り​​組んでいます。従来の知識では、配列を5要素のブロックに分割し、それぞれの中央値を取得してから、結果の中央値に同じブロッキングアプローチを再帰的に適用して、「中央値の中央値」を取得するようです。

私を混乱させているのは、3要素ブロックではなく5要素ブロックを選択していることです。5要素のブロックでは、5の中央値の操作を実行するように見えますがn/4 = n/5 + n/25 + n/125 + n/625 + ...、3要素のブロックでは、3のn/2 = n/3 + n/9 + n/27 + n/81 + ...中央値の操作を実行します。各中央値5は6回の比較であり、各中央値3は2回の比較であるため、3*n/2中央値5を使用した比較と、n中央値3を使用した比較になります。

誰かがこの不一致を説明できますか、そして5要素ブロックを使用する動機は何でしょうか？私はこれらのアルゴリズムを適用するための通常の方法に精通していないので、いくつかのステップを切り取って、中央値に「十分に近づけて」適切なピボットを確保する方法があるかもしれません。そのアプローチは5要素ブロックでより適切に機能します。 ？

4

3 に答える 3

11

その理由は、3つのブロックを選択することにより、O（n）時間アルゴリズムを持つという保証が失われる可能性があるためです。

5のブロックの場合、時間計算量は

T（n）= T（n / 5）+ T（7n / 10）+ O（n）

3のブロックの場合、

T（n）= T（n / 3）+ T（2n / 3）+ O（n）

これをチェックしてください：http ：//www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

于 2010-10-11T17:06:18.883 に答える
6

私はそれが「良い」分割を保証することに関係していると信じています。5要素のブロックに分割すると、最悪の場合の70〜30の分割が保証されます。標準的な引数は次のようになります。n/5ブロックのうち、中央値の少なくとも半分は中央値の中央値であるため、ブロックの少なくとも半分にはn/5少なくとも3つの要素（5の1/2）>=中央値があります。 of-mediansであり、これにより3n/10分割が発生します。これは、他のパーティションが7n/10最悪の場合であることを意味します。

それは与えるT(n) = T(n/5) + T(7n/10) + O(n)。

以来n/5 + 7n/10 < 1、最悪の場合の実行時間はO（n）です。

したがって、3要素のブロックを選択すると、ブロックの少なくとも半分にn/3少なくとも2つの要素> =中央値の中央値が含まれるため、n/3分割が2n/3発生します。最悪の場合は、このようになります。

それは与えるT(n) = T(n/3) + T(2n/3) + O(n)。

この場合n/3 + 2n/3 = 1、、なので、最悪の場合はO（n log n）になります。

于 2010-10-11T17:10:44.113 に答える
4

サイズ3のブロックが使えます！はい、私はあなたと同じように驚いています。2014年（2010年にあなたが尋ねた）に、その方法を示す論文が出ました。

考え方は次のとおりです。、、、、、...を実行する代わりmedian3に、、、、、、、、 ...をpartition実行します。この論文では、これは「反復ステップアルゴリズム」と呼ばれています。median3partitionmedian3median3partitionmedian3median3partition

したがって、代わりに：

T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)

1つは取得します：

T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)

上記の記事は、K。ChenとA. Dumitrescu（2014、arxiv）による「3または4のグループで選択」または「3または4のグループで選択」（2015、著者のホームページ）です。

PS： A. Alexandrescu（D言語で有名です！）による高速決定論的選択。これは、上記をさらに効率的に実装する方法を示しています。

于 2016-09-02T09:07:33.223 に答える