在线性空间中存储成对和

Question

如果我们有两个大小为n的数组并且想要对它们的和进行排序,那么天真的方法是将它们的和存储在O(n ^ 2)空间中并在O(n ^ 2 logn)时间内对其进行排序.假设我们被允许具有相同的O(n ^ 2 logn)运行时间,我们如何将总和存储在O(n)的线性空间中？

我想我们并不打算存储所有的金额,因为它们n ^ 2个元素不适合n个空格,而且我们只是按排序顺序打印出所有内容,所以这是否意味着我们必须动态存储项目？有小费吗？

(这是作业问题)

Answer 1

据我了解，问题是我们想要找到总和

a1 + b1  a1 + b2  ...  a1 + bn
a2 + b1  a2 + b2  ...  a2 + bn
  ...      ...    ...    ...
an + b1  an + b2  ...  an + bn

并按排序顺序打印它们。限制是进程中仅使用 O(n) 内存和 O(n^2 log n) 时间。

将上表视为每个元素n的列表（行）n。如果我们对初始数组进行排序，使得a1 <= a2 <= ... <= an和b1 <= b2 <= ... <= bn，每个列表都已经排序。现在，问题简化为合并n排序列表。

为此，请考虑如何合并两个排序列表（如 MergeSort 中），然后合并三个列表，依此类推。这可以简单地扩展到合并每个输出元素的操作中每个n长度的列表，总共. 现在，剩下的就是减少将每个输出元素降低到 的时间。当您寻求提示而不是完整的解决方案时，请看看您是否可以自己处理该步骤。nnO (n^3)O (log n)