我有一个名为x. x[a][b] = x[a][c] = x[b][c]当然，我想尽可能快地计算所有三元素组。我不需要知道那些元素，我只需要那些组的数量。
该数组的第一个维度的大小等于第二个维度的大小。
我知道蛮力解决方案，它的复杂度为 O(n^2)，其中 n 是数组的大小。我想有一个更快的解决方案，但我不知道它是什么样子的。
问问题
102 次
2 回答
2
除了蛮力，我看不到任何方法。
在每一行中搜索一对，然后检查该对的 x[b][c]。
设数组为NxN。将行中的每个元素与行中的其他元素进行比较需要
N choose 2 = N(N-1)/2 = O(N^2)
比较，您需要对所有N行进行比较O(N^3)。如果你说话的总大小 ( M=N^2) 那么它的O(N^(3/2)).
于 2013-10-14T23:36:41.383 回答
0
我很确定蛮力解决方案将是 O(N^3)
一个不同的解决方案（除了普通的 (0,0,0) 之外）是将每对放在一个哈希表中，使用它的值作为键。然后在重复项中查找与您的标准匹配的对。
于 2013-10-14T23:44:10.017 回答