以线性 space 形式存储成对总和

Question

如果我们有两个大小为 n 的数组，并且想要对它们的总和进行排序，天真的方法是将它们的总和存储在 O(n^2) space 中并在 O(n^ 2 登录）时间。假设我们允许拥有相同的运行时间 O(n^2 logn)，我们如何将总和存储在 O(n) 的线性 space 中？

我想我们不打算存储所有的总和，因为它们 n^2 个元素不适合 n space 并且我们只是按排序顺序打印所有内容，所以这样做意味着我们必须动态存储项目？有什么建议吗？

（这是一道作业题）

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)时间。

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

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

Answer 2

在 python 中你可以这样：

import heapq

a = [2, 1, 3]
b = [4, 6, 5]

a.sort()
b.sort()

def add_to_b(x):
    for v in b:
        yield v + x

for v in heapq.merge(*[add_to_b(x) for x in a]):
    print v

结果：

我们的想法是对两个数组进行排序。然后向 b 添加一个 a 的元素定义一个递增数字的生成器。所以我们创建了 n 个这样的生成器，并使用 heapq.merge 合并它们。上面用add函数表示的生成器，在特定时间需要常量space（space需要保持当前位置在b）。 heapq.merge本身需要线性space。所以我们需要线性space来执行算法。

Answer 3

先将2个数组按升序排序，时间复杂度为2 * O(n*lgn)，也可以看做是O(n*lgn)。然后使用长度为n + 1的max heap来维持最小n个和

如何保持最小n个和？首先将a1 + b1、a1 + b2、a1 + b3、...、a1 + bn压入堆中。然后对于每个 a[i], 1 <= i < n 和 b[j], 0 <= j < n，压入 a[i] + b[j] 然后弹出最大的一个：

for(int j=0;j<n;j++) {
    heap.push_into(a[0] + b[j]);
}
for(int i=1;i<n;i++) {
    for(int j=0;j<n;j++) {
        heap.push_into(a[i] + b[j]);
        heap.pop(); // remove the current largest sum in the heap, then the sums remain in the heap are the smallest n sums
    }
}

那么堆中的n个元素就是最小的n个和

时间复杂度为O(n^2 * lgn)，space复杂度为O(n)。

以线性 space 形式存储成对总和

Storing pairwise sums in linear space

arrays

sorting

algorithm

big-o

asymptotic-complexity