2012-04-06 11 views
1

私は次のようにアルゴリズムを書くように言われました 同じサイズNの3つの配列A []、B []、C []があります。A(i、j、k) [i] + B [j] = C [k]となる。最大許容時間計算量はO(N^2).Following私は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)以上のアルゴリズムですか?

よろしく、 アルカ

+0

可能なすべての(i、j、k)をお探しですか?それとも、トリプルを見つけたいのですか?また、配列のデータは区別されますか? –

+0

あなたのコードは* all *の組み合わせを見つかりません。同じ合計を与える{i、j}のペアが複数ある場合は、それらのうちの1つだけをキャプチャします。 –

+0

また、あなたの現在のソリューションは完全に間違っています。バグが多すぎます。 –

答えて

0

は、私はあなたがの合計を取得するために、各BのためにAのすべてをループしていという理由だけで、あなたはO(N )よりも速く何かを見つけるとは思いませんすべての配列要素それだけでO(N )です。

EDIT:いくつかの最適化が行われていますが、たとえば、sum_array[a[i]+b[j]].result = a[i]+b[j]と設定します。後でキーが結果と等しいかどうかをテストします。どのようにして平等なものにすることができますか?

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}上記の例では、すべての可能なトリプレットは出力されません。

+0

+1:素敵な簡単な答え。 (これはいくつかの制約がない限り正確です。たとえば、各配列の要素は一意でなければなりません) –

+0

すべての要素が異なるという制約があっても、答えがサイズO ):a = {1,2,3、.. n}、b = {1,2,3、... n} c = {1,2,3、.. n} –

1

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

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

私は詳細なしでちょうどアイデアを記述しています。

Lets A_count[x] =要素数xは、配列Aにあります。
A,BおよびCのようなアレイを計算する。
線形時間で行うことができます。

配列を,B_countおよびC_countとし、多項式と考える。 coefficient[X]があり、その後A_count * B_count(多項式として掛け)Xに合計A[i] + B[j]がある場合は!= 0

は、だから今のアイデアは単純です。 A_count * B_countを計算し、係数をC_countの係数と比較してください。 A_count * B_countの計算はO(MAX log(MAX))Discrete Fourier transformを使用して行うことができます。

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

@edit、例は今A_count * B_countを計算することができます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} 

を計算することができます。乗算のための単純なアルゴリズム:

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]; 

しかし、それは(Discrete Fourier transformで)速く行うことができます。

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

それは意味:あなたは三つ子の存在A[i]+B[j]=C[k]が、それはO(n^2 logn)で行うことができるように(i、j、k)のために検索したい場合は

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 
+0

私はかなり理解していませんこのアプローチ。あなたは例を挙げることができますか? (コードまたは手計算のいずれか) –

+0

私は自分の答えを更新しました。あなたが理解していない部分を教えてください。 –

+0

これはタプルが何であるかは分かりません。 –

0

。また、このメソッドを使用すると、このようなトリプレットの数を見つけることができます。

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

(下限関数によって返されたインデックスを使用してチェックすることができ)、その値がDに存在する場合にのみDC[]の値についてlower boundupper boundを探す

  • 、トリプレットの数をカウントするには。

    count + = upper_bound_index - lower_bound_index;

この時間の複雑さもO(n^2 logn)です。

関連する問題