algorithm - 给定一个排序数组，我们可以构建一个 O(n^2) 中所有对的总和的排序数组吗？

Question

给定一个排序的整数数组，我们可以构建一个 O(n^2) 中所有对的和的排序数组吗？

一个简单的解决方案是在 O(n^2) 中构建总和数组，然后在 O(n^2 (log(n^2)) = O(n^2 logn) 时间内对其进行排序。

另一种解决方案是在 O(n^2) 时间内构建 n 个已排序的数组，每个数组包含 n 个数字，并在 O(n^2 logn) 时间内将它们合并（例如，请参见此处）。

我们能做得更好吗？

Answer 1

这是文献中称为排序X + Y的开放问题。由于Lambert和Steiger--Streinu ，已知的最佳结果是使用 O(n^2) 比较的 O(n^2 log n) 时间算法。