问从数组中求每一对整数绝对差的乘积

EN

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

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

M*x-n* x，

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

因此，如果数组是排序的，则计算结果是线性的。如果数组完全未排序，则排序是n* log(n)，如果使用mergesort的话。因此，复杂性是

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

但是对于绝对差的乘积，

你有一个形式的乘积

(a1 - b1) *(.)

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

(a1 - b1) * (a2 - b2)

是

a1a2 - a1b2 - b1a2 + b1b2

我不知道可以用于优化的任何模式，所以我认为这具有O(n^2)的复杂性。