1

有人告诉我写一个算法如下 三个数组 A[],B[],C[] 大小相同 N.找出所有可能的 (i,j,k) 使得 A[i]+B[j ]=C[k]。允许的最大时间复杂度为 O(N^2)。以下是我为 O(N^2) 编写的算法

#include<stdio.h>

#define MAX 1000

struct sum
{
        int result;
        int i;
        int j;
};

int main()
{
        struct sum sum_array[MAX];
        int n=4;
        int a[] = {4,1,2,5};
        int b[] = {1,7,6,0};
        int c[] = {11,3,8,2};
        int k;
        int i,j;
        for(i=0;i<MAX;i++)
                sum_array[i].result=-1;
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        sum_array[a[i]+b[j]].result=a[i]+b[j];
                        sum_array[a[i]+b[j]].i=i;
                        sum_array[a[i]+b[j]].j=j;
                }
        }
        for(k=0;k<n;k++)
        {
                if(sum_array[c[k]].result==c[k])
                {
                        printf("<i,j,k> = <%d,%d,%d>\n",sum_array[c[k]].i,sum_array[c[k]].j,k);
                }
        }
        return 0;
}

我的问题是如何更快地做到这一点？有任何 O(N*logN) 或更好的算法吗？

问候， 阿尔卡

4

4 回答 4

6

最大答案的大小为 N^3，因此无法实现更好的复杂性。举这个例子 A={1,1,1,1,1,1,1} , B = {1,1,1,1,1,1} C = {2,2,2,2,2,2对于上面的例子，你的方法不会输出所有可能的三元组。

于 2012-04-06T13:43:30.793 回答
1

如果您正在寻找一种组合或只是这种组合的数量，那么：

设MAX为数组A, B,中的最大元素C。我的解决方案是O(MAX log(MAX))。

我只是在描述没有细节的想法。

让=数组A_count[x]中的元素数。为和 计算这样的数组。 它可以在线性时间内完成。xA
ABC

A_count将数组B_count视为C_count多项式。如果有那么A[i] + B[j]总和（乘以多项式）有！= 0。XA_count * B_countcoefficient[X]

所以现在想法很简单。计算A_count * B_count它们的系数并将其与 的系数进行比较C_count。A_count * B_count可以O(MAX log(MAX))使用 离散傅里叶变换进行计算。

@edit，示例

int A[] = {4,1,2};
int B[] = {1,0};
int C[] = {3,8,2};

让我们计算 A_count、B_count、C_count

                 0, 1, 2, 3, 4, 5, 6, 7, 8
int A_count[] = {0, 1, 1, 0, 1};
int B_count[] = {1, 1}; 
int C_count[] = {0, 0, 1, 1, 0, 0, 0, 0, 1}

现在让我们计算 A_count * B_count。简单的乘法算法：

for(int i=0; i<A_count_SIZE; i++)
    for(int j=0; j<B_count_SIZE; j++)
        mult_result[i+j] += A_count[i] * B_count[j];

但它可以更快地完成（通过离散傅里叶变换）。

int mult_result[] = {0, 1, 2, 1, 1, 1}

代表着：

1 pair sums to 1
2 pairs sums to 2
1 pair sums to 3
1 pair sums to 4
1 pair sums to 5
于 2012-04-06T14:08:14.893 回答
0

我认为您不会找到比 O(N 2 ) 更快的方法，因为您必须为每个 B 遍历所有 A 以获得所有数组元素的总和。仅此一项就是 O(N 2 )，阻止您更快地获得任何东西。

编辑：虽然，有一些优化要做。例如，您设置sum_array[a[i]+b[j]].result = a[i]+b[j]. 稍后您测试密钥是否等于结果。怎么可能是平等的呢？

于 2012-04-06T13:42:56.957 回答
0

如果你想找到三元组 (i,j,k) 的存在使得A[i]+B[j]=C[k]，那么它可以在 中完成O(n^2 logn)。此外，您可以使用此方法找到此类三元组的计数。

  • 制作一个新数组D[]，以D保存每对可能的A和的总和B。这将使 D = n^2 的大小。
  • 对数组 C 进行排序。现在，对于数组binary search中的所有值。时间复杂度为。DCO(n^2 logn)

要计算三胞胎的数量，

  • 仅当该值存在于（可以使用下界函数返回的索引进行检查）时，才查找该值的lower bound和。upper boundC[]DD

    计数 += 上界索引 - 下界索引；

这个时间复杂度也是O(n^2 logn)。

于 2012-04-06T18:05:58.417 回答