1

次のようにアルゴリズムを書くように言われました 同じサイズ N の 3 つの配列 A[]、B[]、C[] があります。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

1つの組み合わせ、またはそのような組み合わせの数だけを探している場合は、次のようにします。

配列、、、からの最大MAX要素とします。私の解決策はです。ABCO(MAX log(MAX))

私は詳細なしでアイデアだけを説明しています。

Lets =配列内A_count[x]の要素の数。、および のそのような配列を計算します。 それは線形時間で行うことができます。xA
ABC

配列A_count、B_countおよびC_count多項式と考えてください。A[i] + B[j]その合計がある場合X（A_count * B_count多項式として乗算）はcoefficient[X]！=0になります。

だから今、アイデアは単純です。それらの係数を計算A_count * B_countし、の係数と比較しC_countます。計算は、離散フーリエ変換を使用して A_count * B_count行うことができます。O(MAX log(MAX))

@編集、例

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

のようなトリプレット (i、j、k) の存在を見つけたい場合は、A[i]+B[j]=C[k]で実行できますO(n^2 logn)。また、このメソッドを使用して、そのようなトリプレットの数を見つけることができます。

  • と のすべての可能なペアの合計D[]を保持するような、新しい配列を作成します。これにより、D = n^2 のサイズになります。DAB
  • 配列 C を並べ替えます。ここで、配列binary searchのすべての値について。時間複雑度はです。DCO(n^2 logn)

トリプレットの数を数えるには、

  • その値が に存在する場合にのみ、 のlower boundとupper boundの値を検索します(これは、下限関数によって返されるインデックスを使用して確認できます)。C[]DD

    count += upper_bound_index - lower_bound_index;

これの時間計算量もO(n^2 logn)です。

于 2012-04-06T18:05:58.417 に答える
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 に答える