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

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

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

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

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

标签： algorithm

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

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

m * x - n * x,

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

因此，如果数组已排序，则计算结果是线性的。如果您使用归并排序，则对完全未排序的数组进行排序是 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) 复杂性。