找到一些更好的算法来找到数组元素之间的最小差异

Question

输入：整数数组 A[0..n – 1]

输出：dmin 数组的两个元素之间的最小差异

dmin = ∞
for i = 0 to n − 1 do
   for j = 0 to n − 1 do
      if i != j &&|A[i] − A[j]| < dmin
        dmin ← |A[i] − A[j]|
return dmin
  

我知道上面代码的复杂度是O(n^2)。我想找到一个更好的算法 找到数组元素之间的最小差异并计算其复杂度。然后，将上述代码实现为单个函数，并将改进的算法实现为 c 中的另一个函数。为大小为 60000、70000、80000、90000 和 100000 的随机数组调用两个函数（为每个维度创建十个不同的随机矩阵并求平均值）。

所以，我已经做到了：

int pair1(int A[],int n)
{
    int dmin=INT_MAX,i,j;
   
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if (i != j && abs(A[i] - A[j]) < dmin) 
            {
                dmin = abs(A[i] - A[j]);
            }
        }
    }
    
    return dmin;
}

我认为如果我们对数组进行排序，可能会有更好的算法。有什么想法如何用 c 语言做到这一点以及如何将其编写为伪代码吗？我认为它的复杂度是 O(nlogn)。

我已经尝试过这段代码：

int pair2(int A[],int n)
{
    int dmin=INT_MAX,i,j;
    sort(A,A+n);

    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if (i != j && abs(A[i] - A[j]) < dmin) 
            {
                dmin = abs(A[i] - A[j]);
            }
        }
    }
        
    return dmin;
}

Answer 1

是的，如果您使用 O(nlog2(n)) 排序算法（例如快速排序或合并排序）对数组进行排序，则可以在 O(nlog2(n)) 中完成最小值，这是正确的。

然后，找到最小差异是 O(n) 的单循环。

总的复杂度是两者中较大的一个：O(n*log2(n))

这是一些示例代码。它有大量注释：

#include <stdlib.h>
#include <limits.h>

int
cmp(const void *vlhs,const void *vrhs)
{
    const int *lhs = vlhs;
    const int *rhs = vrhs;
    return *rhs - *lhs;
}

int
pair2(int A[],int n)
{

    // sort the array by any O(n*log2(n)) [or better] sort (e.g. quicksort,
    // mergesort)
    qsort(A,n,sizeof(int),cmp);

    int dmin = INT_MAX;

    // get A[i - 1] for first loop iteration
    int old = A[0];

    // loop through all remaining elements (this is O(n))
    for (int i = 1;  i < n;  ++i) {
        // get the current array value
        int cur = A[i];

        // difference between the current and previous values:
        // dif = A[i] - A[i - 1]
        int dif = cur - old;

        // get absolute value
        if (dif < 0)
            dif = -dif;

        // save new/better minimum
        if (dif < dmin) {
            dmin = dif;

            // because we took the absolute value, we can't get any better than
            // this
            if (dif == 0)
                break;
        }

        // remember A[i - 1] for next iteration
        old = cur;
    }

    return dmin;
}