ソートされた配列が与えられた場合、O（n^2）のすべてのペアの合計の並べ替えられた配列を作成できますか？

ソートされた整数の配列が与えられていると、O（n^2）のすべてのペアの合計の並べ替えられた配列を作成できますか？ソートされた配列が与えられた場合、O（n^2）のすべてのペアの合計の並べ替えられた配列を作成できますか？

些細な解決策は、O（n^2）に合計の配列を作成し、それをO（n^2（n^2））= O （例えばhereを参照）時間（N^2）Oで、そして（N^2 LOGN）Oでそれらをマージ

別の解決策は、N個それぞれのN個のソートされたアレイを構築することであろう。

2013-07-18 Lior Kogan

Um、なぜ最初の解はO（n^2（log^2）n）時間になるでしょうか？長さn^2の配列をソートするには、それをO（n^2 log（n^2））（= O（n^2 logまたは、比較ソートよりも速いものを使用していますか？ –

別名[ソートX + Y]（http://cs.smith.edu/~orourke/TOPP/P41.html） –

@DavidEisenstatまだ存在しない解決策を考えることができない限り問題は解決します – aaronman

これは、文献にはSorting X + Yとして知られている未解決の問題です。O（n^2 log n）時間アルゴリズムは、O（n^2） LambertおよびSteiger--Streinu。

2013-07-18 21:20:35

しかし、それは最高だとは証明されていません、そうですか？ – aaronman

@aaronman：それはオープンな問題が意味するものです... –

@aaronmanはい、O（n^2）時間アルゴリズムがある可能性があります。私が知る限り、そのようなアルゴリズムの存在には "悲惨な"結果はP = NPのようになります。 O（n^2）比較アルゴリズムが存在することにより、下界の証明者になることが困難になります。 –

答えて