java - 高效的 Minkowski 和计算

Question

我想知道是否有一种算法可以有效地计算离散的一维Minkowski 和。Minkowski 和定义为：

S + T = { x + y | x in S, y in T }

是不是我们可以将集合表示为列表，对 S 和 T 进行排序，然后做一些类似的事情来计算两个集合的并集。即并行地沿着集合走并生成结果。

有没有这样的算法，我不必额外对结果进行排序以删除重叠案例 x1+y1 = x2+y2？最好用Java编写？

Answer 1

首先，输出的大小可以是O(nm)，如果没有碰撞（例如，A={0, 1, 2, ..., n-1}，B={n, 2*n, 3*n, ...n*n}），所以如果我们依赖n和m，我们就没有希望找到二次算法。一个简单的方法是计算所有对 ( O(nm))、排序和唯一性（总计O(nm log nm).

如果你有一个上限M使得x <= M所有xin A union B，我们可以通过O(M log M)以下方式计算总和。

1. 生成特征向量A[i] = 1 ff i \in A, 0 otherwise，对于B. 每个这样的向量的大小为M。

2. 计算A并B使用 FFT 的卷积（时间：O(M log M)）。输出大小为 O(· M)。

3. 扫描输出O- 在每个单元格，如果是 Minkowski 和的一个元素，O[i]则非零。i

证明：O[i] != 0当且当且当且当且当且当且k即当且在闵可夫斯基A[k] != 0和中时。B[i-k] != 0k \in Ai-k \in Bk + i-ki

（取自这篇论文）

Answer 2

对 S 和 T 进行排序，遍历 S 搜索 T 中的匹配元素，每次找到匹配项时，从 S 和 T 中删除元素并将其放入新的集合 U 中。因为它们是排序的，一旦在 T 中找到匹配项， T 中的进一步比较可以从最后一场比赛开始。

现在 S、T 和 U 都是不相交的。所以迭代 S 和 T 并添加一个，以及 S 和 U，以及 T 和 U。最后迭代 U，并将 U 中的每个元素添加到 U 中的每个元素，其集合索引等于或大于当前集合索引。

可悲的是，这种优化算法仍然是 O(n^2)。如果 T 和 S 相同，它将比简单解决方案快 2 倍。您也不必在输出集中搜索重复项。