algorithm - 从数组中查找每对整数的绝对差的乘积

Question

给定一个数组，求出每对整数的绝对差的乘积。

例如:给定 a[]= {2,3, 5, 7 };

输出将是(3-2) * (5-2) * (7-2) * (5-3) * (7-3) * (7-5) = 240 .

它能比 O(n^2) 做得更好吗？编辑:所有元素都是不同的。

Answer 1

如果您必须计算绝对差的总和，那么这就是您的解决方案

基本上，如果你取一个任意数，我们把它命名为x，那么你就有了它

m * x - n * x,

其中 m 是小于 x 的项目数，n 是 n 大于 x 的项目数。所以，如果出于某种原因你有一个排序数组，那么如果它在数组中是唯一的，那么每个项目的索引将直接告诉你有多少更大或更小的项目。如果不是，那么您也可以确定更高和更低元素的数量。

因此，如果数组已排序，则计算结果是线性的。如果使用合并排序，则对完全未排序的数组进行排序是 n * log(n) 的复杂性。因此，复杂度为

O(n + n * log(n)) = (n + 1)log(n)

但对于绝对差的乘积

你有一个形式的产品

(a1 - b1) * ... (...)

由于您有减法的乘积，为了找到可用于优化的模式，您需要有关数据的更多信息。您的输入似乎包含质数。产品

(a1 - b1) * (a2 - b2)

是

a1a2 - a1b2 - b1a2 + b1b2

我不知道您可以使用任何模式进行优化，所以我认为这具有 O(n^2) 复杂度。