各エントリが整数のペアで構成される、m行と列を持つ行列が与えられます。行列にペアが 2 回現れることはありません。n(a,b)
ここで、これらのペアを並べ替えたいと思います。同じ行にある2 つのペア(a,b)とについて、そのペアが の左側にあるようにします。さらに、同じ列にある 2 つのペアの場合、 の場合に限り、それが以下になります。(c,d)(a,b)(c,d)((a < c) or (a=c and b < d))(a,b)(c,d)(a,b)(c,d)((b < d) or (b=d and a < c)
すべての行と列が上記の条件を満たす配置を見つけた場合、それを安定と呼びます。
最初にすべてのペアを列の状態に従って並べ替えると、安定した配置が得られやすくなりますが、これにはO(mn log(mn))時間がかかります。次に、このリストを m 個の部分に分割しますp_1,...,p_m(それぞれが n 個の要素で構成され、それぞれ(a,b)の in p_i、(c,d)in p_jit isで構成されます(a,b) < (c,d) if i < j)。p_iここで、各パーツを列条件に従ってソートします。これは、パーツO(n log(n))ごと、つまりO(mn log(n))すべてのパーツに対して行われます。ソートされた部分p_iを列に書き込むとi、安定した配置が得られます。
ここで、特殊なケースm=nを考えてみましょうN=n²。上記の引数を使用すると、安定した配置が時間内に取得できることがわかりO(N log(N))、上限が得られます。さて、これは疑問を投げかけます：
この問題の下限は? O(N log(N))最適ですか？