X + Yソート

コンピュータサイエンスにおける未解決問題

ありますか${\displaystyle X+Y}$ソートアルゴリズムはより高速です${\displaystyle O(n^{2}\log n)}$？

コンピュータサイエンスにおける未解決問題

コンピュータサイエンスにおいて、X + Yソートとは、2 つの数値をその合計値に基づいてソートする問題です。この問題の応用例としては、交通費の最小化、VLSI設計、疎行列多項式の乗算などが挙げられます。比較ソートやより一般的な整数ソートと同様に、この問題のアルゴリズムは、これらの合計値の比較のみに基づくもの、または入力が小さな整数の場合にのみ機能する他の演算に基づくものなどがあります。

この問題には、同数の項目からなる非構造化リストのソートよりも実行時間が漸近的に速い比較ベースの解法が存在するかどうかは不明である。そのため、この問題に関する研究は、そのような改善が可能かどうかという疑問を解決するために、2つのアプローチに焦点を当ててきた。1つは、実行時間全体ではなく比較回数において非構造化ソートを改善するアルゴリズムの開発、もう1つは、高次元空間の分割におけるセルを数えることに基づく比較回数の下限値である。この2つのアプローチは、比較回数が少ない最初のアルゴリズムがセルカウントの下限値の弱点に基づいていたという点で、歴史的に密接に関連している。

入力${\displaystyle X+Y}$ソート問題は、2つの有限な数値の集合から構成される。${\displaystyle X}$そして${\displaystyle Y}$同じ長さの。問題の出力は、からのすべての数のペアのコレクションです。${\displaystyle X}$そして数から${\displaystyle Y}$各ペアの合計によってソートされた順序に並べられます。^{[ 1 ]}簡単な例として、入力の場合${\displaystyle X=\{1,2,9\}}$そして${\displaystyle Y=\{0,4,9\}}$出力はペアのリストになるはずです$${\displaystyle (1,0),\,(2,0),\,(1,4),\,(2,4),\,(9,0),\,(1,9),\,(2,9),\,(9,4),\,(9,9)}$$1つの要素から${\displaystyle X}$そして、${\displaystyle Y}$ペアの合計値に基づいてソートされた順序でリストされています$${\displaystyle 1,2,5,6,9,10,11,13,18.}$$この問題を解決する一つの方法は、ソートするペア（2つのコレクションの直積）を構築し、これらのペアをマージソートやヒープソートなどの標準的な比較ソートアルゴリズムへの入力として使用することです。入力の長さが${\displaystyle n}$それらは形成する${\displaystyle n^{2}}$ペアを生成し、このようにペアをソートする時間は${\displaystyle O(n^{2}\log n)}$ビッグオー記法の観点から見ると、この方法は既知のアルゴリズムの中で最速です。${\displaystyle X+Y}$ソート。より高速なアルゴリズムが存在するかどうかは未解決の問題であり、^{[ 1 ] [ 2 ]} 1975 年以前にElwyn Berlekampによって提起された。^{[ 1 ] [ 3 ]}

この問題の変形では、ペアの合計の集合である合計セットをソートし、重複する合計を単一の値にまとめます。この変形では、合計セットのサイズは、より小さくなる可能性があります。${\displaystyle n^{2}}$、そしてそれを構築するための出力依存型アルゴリズムが研究されてきた。^{[ 4 ]}

スティーブン・スキエナは、最短経路問題の一例である交通運賃最小化の実用例について述べている。これは、各ホップのコストと、どのホップのペアを1枚のチケットに組み合わせることができるかを記述した入力から、2つの都市間の最も安い2ホップの航空券を見つけるというものである。スキエナのソリューションは、ホップのペアを合計コストでソートすることから成り、${\displaystyle X+Y}$ソート問題、そして結果として得られたペアをこのソート順でテストし、許可されるペアが見つかるまで繰り返します。この順序でソートされたペアを生成するために、Skiena はペアの優先度キューを使用します。このキューには、最初は最も安い 2 つのホップで構成される 1 つのペアのみが含まれています。次に、ペアが${\displaystyle (x,y)}$がキューから削除され、許可されていないことが判明した場合、さらに 2 つのペアが追加され、これらの 2 つのペアのうちの 1 つが結合されます${\displaystyle x}$次のホップの後${\displaystyle y}$目的地までのホップのソート済みリストと、もう一方のペアを組み合わせたもの${\displaystyle y}$次のホップの後${\displaystyle x}$開始点からのホップのソート済みリスト内で。このようにして、各連続するペアは対数時間で見つけることができ、最初の許容ペアまでのペアのみをソートする必要があります。^{[ 2 ]}

${\displaystyle X+Y}$ソートは、 VLSI設計の問題に対するアルゴリズムの中で最もコストのかかるサブルーチンです。この問題では、VLSI回路の2つのサブユニットを通信チャネルに沿って並べて配置し、一方のサブユニットから他方のサブユニットへワイヤのペアを配線するために必要なチャネルの幅を最小化する必要があります。一方のサブユニットが他方のサブユニットに対して連続的にシフトされると、チャネルの幅は2本のワイヤの端が互いに揃う離散的な位置でのみ変化します。これらの位置のソートされた順序を見つけて幅の変化のシーケンスを計算するには、次の操作を実行できます。${\displaystyle X+Y}$ソート。このソート問題を高速化できれば、このVLSI設計タスクも高速化されるだろう。^{[ 5 ]}

別の応用例として、次数よりも項数がはるかに少ない単一変数の多項式の乗算があります。2つの多項式の積は、各多項式から1つずつ、項のペアの積の和として表すことができ、これらの項ごとの積を次数順に並べることは、次数の合計でソートすることに相当します。たとえば、次の例が挙げられます。${\displaystyle X+Y}$ソート${\displaystyle n=3}$上記の例は、2つの3項多項式を乗算して9項多項式を生成することに相当します。 $${\displaystyle {\begin{aligned}(&x+x^{2}+x^{9})(1+x^{4}+x^{9})\\&=x+x^{2}+x^{5}+x^{6}+x^{9}+x^{10}+x^{11}+x^{13}+x^{18}.\\\end{aligned}}}$$ 次数は常に整数なので、整数ベースのアルゴリズムは${\displaystyle X+Y}$ソートが適用される場合がある。^{[ 6 ]}ただし、項数が次数と同程度の多項式の場合、FFT ベースの多項式乗算アルゴリズムは、項ごとの乗算よりもはるかに効率的である可能性がある。^{[ 7 ]}

決定木モデルにおける非構造化ソートのよく知られた下限は、非構造化リストが持つ可能性のあるソート済み順序の階乗数に基づいています。各比較は可能な順序の数を最大で2分の1に減らすことができるため、ソートには階乗の二進対数に等しい数の比較が必要です。${\displaystyle n\log _{2}nO(n)}$[ ^{8 ]初期の}研究${\displaystyle X+Y}$ソートは、この問題で可能なソート順の数がいくつあるかを問い、その数が最大で であることを証明することで、同様のアプローチをとりました。${\displaystyle O(n^{8n})}$しかし、その二進対数は最大で${\displaystyle 8n\log _{2}n+O(1)}$既知の時間制限よりもはるかに小さい${\displaystyle X+Y}$ソートの場合、この方法は比較回数の下限値しか得られません。^{[ 3 ] [ 9 ]}

この限界の証明は${\displaystyle X+Y}$高次元幾何学における超平面の配置の複雑さへのソート。${\displaystyle X+Y}$ソート問題には以下が含まれる${\displaystyle 2n}$数値は、別の解釈では、点のデカルト座標として表すこともできます。${\displaystyle 2n}$次元空間$\displaystyle \mathbb {R} ^{2n}}$この空間はセルに分割でき、単一のセル内のすべての点は、同じソート順を生成する入力に対応します。この分割では、2 つのセル間の各境界は、ペアの等式によって定義される超平面内にあります。${\displaystyle x_{i}+y_{j}=x_{k}+y_{\ell }}$、 どこ${\displaystyle (x_{i},y_{j})}$そして${\displaystyle (x_{k},y_{\ell })}$これらは、隣接するセル間で順序が変化する2組のペアです。これらの超平面は、互いに素な2組のペアによって生成されるか、または簡略化された形式を持ちます。${\displaystyle x_{i}=x_{k}}$または${\displaystyle y_{j}=y_{\ell }}$したがって、このようにして決定できる異なる超平面の数は $${\displaystyle k=2{\binom {n}{2}}^{2}+2{\binom {n}{2}}.}$$ この数の超平面が次元空間を分割できるセルの数${\displaystyle 2n}$に $${\displaystyle {\binom {k}{2n}}+{\binom {k}{2n-1}}+\cdots +{\binom {k}{0}}=O(n^{8n}).}$$したがって、セット${\displaystyle X+Y}$もっている${\displaystyle O(n^{8n})}$異なる可能なソート順。^{[ 3 ] [ 9 ] [ 10 ]}

同様の分析手法は、特定の一般化に対する迅速な解決策を排除するのに成功している。${\displaystyle X+Y}$ソートは、ソートするには順序が多すぎることを示すことによって行われます。特に、Harper ら (1975) は、別々にソートすることを提案しています。${\displaystyle X}$そして${\displaystyle Y}$そして、次の値の2次元行列を構築する。${\displaystyle X+Y}$これは行と列の両方でソートされ、この部分的にソートされたデータを使用してソートを完了します。${\displaystyle X+Y}$[ ^{3 ]}行と列がソートされた行列を使用するこのアイデアは、スキエナが輸送アプリケーションで使用した方法の基礎を形成しており、^{[ 2 ]単純}な比較ソートと比較して比較数を定数倍に減らすことができます。しかし、行と列がこのようにソートされた行列の場合、行列全体の可能なソート順序の数は、${\displaystyle O(n^{8n})}$非常に大きいため、任意の比較ソートアルゴリズムは機能しません${\displaystyle n\times n}$行と列でソートされた行列は、依然として${\displaystyle \Omega (n^{2}\log n)}$比較。したがって、${\displaystyle X+Y}$ソート問題を迅速に解決するには、セットに関する追加情報を使用する必要がある。${\displaystyle X+Y}$この行列順序を超えて。^{[ 3 ]}

古典的な比較ソート問題では、ソートにかかる時間とソートに必要な比較回数は定数倍以内です。しかし、${\displaystyle X+Y}$ソートの場合、比較回数は既知の最良の時間制限よりも少ない。マイケル・フレッドマンは1976年に、${\displaystyle X+Y}$ソートは、${\displaystyle O(n^{2})}$比較。より一般的には、彼は任意の集合が${\displaystyle N}$既にソート順序がファミリーに制限されている要素${\displaystyle \Gamma }$順序付けは、${\displaystyle \log _{2}|\Gamma |+O(N)}$比較は、バイナリ挿入ソートの一種によって行われます。${\displaystyle X+Y}$ソート問題、${\displaystyle N=n^{2}}$、 そして${\displaystyle |\Gamma |=O(n^{8n})}$、 それで${\displaystyle \log _{2}|\Gamma |=O(n\log n)}$そしてフレッドマンの境界は、${\displaystyle O(n^{2})}$比較は必要である。しかし、フレッドマンの方法では、どの比較を実行するかを決定するのに必要な時間が、比較の数の上限よりもかなり長くなる可能性がある。^{[ 9 ]}

両方を実現する最初の明示的なアルゴリズム${\displaystyle O(n^{2})}$比較と${\displaystyle O(n^{2}\log n)}$全体の計算複雑性は、フレッドマンの発表から16年後にランバート（1992）によって発表された。このアルゴリズムは以下の手順を実行する。

1. 2つのセットを再帰的にソートする${\displaystyle X+X}$そして${\displaystyle Y+Y}$。
2. 等価性を使用する$\displaystyle x_{i}-x_{j}\leq x_{k}-x_{\ell }\Leftrightarrow x_{i}+x_{\ell }\leq x_{j}+x_{k}}$ソートされた順序を推測する${\displaystyle XX}$そして${\displaystyle YY}$追加の比較は不要です。
3. 2つのセットをマージする${\displaystyle XX}$そして${\displaystyle YY}$合計サイズに比例する数の比較を用いて、単一のソート済み順序にまとめる。
4. マージされた順序と等価性を使用する${\displaystyle x_{i}+y_{j}\leq x_{k}+y_{\ell }\Leftrightarrow x_{i}-x_{k}\leq y_{\ell }-y_{j}}$ソートされた順序を推測する${\displaystyle X+Y}$追加の比較は不要です。

再帰的にソートするアルゴリズムの部分${\displaystyle X+X}$（または同等の）${\displaystyle Y+Y}$) は、以下の手順でそれを行います。

1. スプリット${\displaystyle X}$2つの等しいサブリストに分割する${\displaystyle A}$そして${\displaystyle B}$。
2. 再帰的にソートする${\displaystyle A+A}$そして${\displaystyle B+B}$
3. 順序を推測する${\displaystyle A+B}$上記のように、単一のマージステップからの比較のみを使用します。
4. ソートされた結果をマージする${\displaystyle A+A}$、${\displaystyle B+B}$、 そして${\displaystyle A+B}$一緒に。

比較回数${\displaystyle C(n)}$この再帰アルゴリズムを入力に対して実行するために必要な${\displaystyle n}$項目は再帰関係を用いて分析できる$${\displaystyle C(n)\leq 2C(n/2)+O(n^{2}),}$$ どこで${\displaystyle 2C(n/2)}$再帰式の項は、ソートアルゴリズムの再帰呼び出しにおける比較回数をカウントします。${\displaystyle A+A}$そして${\displaystyle B+B}$、そして${\displaystyle O(n^{2})}$項は、結果を統合するために使用される比較の数をカウントします。この形式の漸化式のマスター定理は、次のことを示しています。${\displaystyle C(n)=O(n^{2}).}$全体の時間計算量は遅く、${\displaystyle O(n^{2}\log n)}$アルゴリズムのステップでは、既に行われた比較を利用して他のセットの順序を推論するため、これらのステップは時間で実行できます。${\displaystyle O(n^{2}\log n)}$標準的な比較ソートアルゴリズムの比較ステップを、前述の推論に置き換えることによって。^{[ 11 ]}

要素間の比較のみ${\displaystyle X+Y}$が許可されている場合、対応する下限もあります。${\displaystyle \Omega (n^{2})}$比較の数に関しては、^{[ 9 ] [ 12 ]}定数個の要素の線形結合を含むより一般的な比較では、${\displaystyle O(n\log ^{2}n)}$比較が必要である。^{[ 13 ]}

十分小さい整数の場合、整数ソートが比較ソートよりも高速になるのと同様に、${\displaystyle X+Y}$ソート。特に、整数入力の範囲は${\displaystyle 0}$ある上限まで${\displaystyle M}$問題は解決できます${\displaystyle O(n+M\log M)}$高速フーリエ変換による演算。^{[ 1 ] [ 3 ]}

計算幾何学における他のいくつかの問題は、同等またはより複雑な複雑さを持ち、${\displaystyle X+Y}$階段多角形のミンコフスキー和の構築、線分の配置の交点をその順序で見つけることなどを含むソート${\displaystyle x}$-座標、点のペアを距離順に並べ、ある直交多角形が別の直交多角形の中に収まるように移動できるかどうかをテストします。^{[ 14 ]}

2 つのペアが${\displaystyle X+Y}$等しい合計を持つソート問題は、ペアをソートしてから連続するペアの等価性をテストすることで解決できます。さらに、3SUM問題を解決するために使用できるため、強力な準二次アルゴリズムが存在する可能性は低いことを示唆しています。^{[ 1 ]}