algorithm - 查找第一个元素不小于第二个元素的向量对

Question

这是 How to compare each element in two arrays with time complexity less than O(n^2) 的概括.假设我们有两个大小为 nxk 和 mxk 的矩阵 A 和 B，可寻址为 A[row][col]和 B[row][col] .让一对(i, j)如果对于每个 r 都是可以接受的, A[i][r] >= B[j][r] .有什么方法比朴素的 O(nmk) 更快地识别每个可接受的对

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        bool accept = true;
        for (int r = 0; r < k && accept; ++r) {
            accept &= (A[i][r] >= B[j][r]);
        }
        if (accept) { std::cout << i << ", " << j << "\n"; }
    }
}

?

如果 k=1，那么我可以使用链接问题暗示的解决方案在 n log n 时间内完成任务。然而，当 k>1 时，由于这样的矩阵，它变得更加困难:

A[0] = {1, 1}
A[1] = {3, 1}
A[2] = {3, 5}
A[3] = {5, 3}
A[4] = {5, 5}

B[0] = {2, 4}
B[1] = {4, 2}

可接受的对是 (2, 0)、(4, 0)、(3, 1) 和 (4, 1)。按第一个元素排序给出上面的顺序，其中 B=1 可接受的是连续的(A=3 和 A=4)，但 B=0 可接受的不是。按第二个元素排序类似地使 B=0 可接受的内容连续而 B=1 Not Acceptable 内容。像 k=1 解决方案一样进行一次排序和读取连续范围似乎不起作用。

我想到的问题的特定设置是 n 和 m 为百万级，k 为千级，因此 nmk 时间不是很实用。

Answer 1

输出的大小可以是nm，所以算法的性能不可能比O(nm)更好。改善平均情况当然是可能的，但在很大程度上取决于您的数据和分布。以下是一些通用提示:

如果你能负担得起 m * k 内存，你可以保留一个按第一列值排序的 B 索引的排序列表。第二列相同，依此类推。通过这种结构+二分查找，可以回答给定固定列c和固定数x，O(log m)中有多少个B[j][c] <= x。

然后对于 A[i] 中的每个值 x，您可以检查有多少 B[j][c] <= x。按此数量对它们进行排序。第一个值(我们称它为 L1)将是最小的数字，因此您将与按该列排序的列表中的 B 进行比较。通过使用二进制搜索，您可以跳过开头，只与 B 的 L1 数组进行比较。

您可以按照我们从 B[j][c] <= x 计算中保留的顺序进行比较，而不是以任何顺序逐列比较。这意味着我们使用 A 中的第二个值与其他列相比 B 中的值更低的可能性最小。这将有助于最大程度地减少对不满足条件的对的比较。