Ein schnellerer Algorithmus

Question

Ich wurde aufgefordert, einen Algorithmus wie folgt zu schreiben Es gibt drei Arrays A [], B [], C [] der gleichen Größe N. Finden Sie alle möglichen (i, j, k) so dass A [i] + B [j] = C [k]. Die maximal zulässige Zeitkomplexität O (N^2) .Following der Algorithmus I für 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; 
} 

Meine Frage geschrieben ist, wie es schneller zu machen? Irgendein O (N * logN) oder besserer Algorithmus dafür?

Grüße, Arka

Answer 1

Das glaube ich nicht, dass du etwas schneller als O (N) finden, nur weil Sie für jedes B eine Schleife durch alle A die Summen erhalten von alle Array-Elemente. Das allein ist O (N), was verhindert, dass Sie etwas schneller bekommen.

EDIT: Obwohl, es gibt einige Optimierungen zu tun. Beispielsweise legen Sie sum_array[a[i]+b[j]].result = a[i]+b[j] fest. Später testen Sie, ob der Schlüssel dem Ergebnis entspricht. Wie kann es alles andere als gleich sein?

Answer 2

Die maximale Antwort ist von Größe N^3 und daher kann keine bessere Komplexität erreicht werden. Nehmen Sie dieses Beispiel A = {1,1,1,1,1,1,1}, B = {1,1,1,1,1,1} C = {2,2,2,2,2, 2} Sie nähern sich nicht alle möglichen Triplets für das obige Beispiel.

Answer 3

Wenn Sie für eine Kombination oder gerade Anzahl solcher Kombinationen suchen, dann:

MAXA, B, C von Arrays maximales Element sein lassen. Meine Lösung ist O(MAX log(MAX)).

Ich beschreibe nur Idee ohne Details.

Lets A_count[x] = Anzahl der Elemente x im Array A.
Berechnen Sie solche Arrays für A, B und C.
Es kann in linearer Zeit erfolgen.

Denken Sie an Arrays A_count, B_count und C_count als Polynome. Wenn es A[i] + B[j], die X summiert dann A_count * B_count (als Polynome multipliziert) hat coefficient[X]! = 0.

So, jetzt Idee ist einfach. Berechne A_count * B_count und vergleiche ihre Koeffizienten mit Koeffizienten von C_count. Die Berechnung A_count * B_count kann in O(MAX log(MAX)) mit Discrete Fourier transform erfolgen.

@edit, zB auf

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

Lets berechnen 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} 

Jetzt können A_count * B_count berechnen.Einfacher Algorithmus für die Multiplikation:

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

Aber es kann schneller durchgeführt werden (durch Discrete Fourier transform).

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

Es bedeutet, dass:

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 

Answer 4

Wenn Sie auf die Existenz von Tripletts finden wollen (i, j, k), so dass A[i]+B[j]=C[k], dann kann es in O(n^2 logn) erfolgen. Mit dieser Methode können Sie auch solche Tripel zählen.

• Machen Sie ein neues Array D[], so dass D Summe aller möglichen Paar A und B hält. Dies macht die Größe von D = n^2.
• Array C sortieren. Jetzt binary search für alle Werte von D im Array C. Die Zeitkomplexität ist O(n^2 logn).

Anzahl von Tripletts zu zählen,

• die lower bound und upper bound für Werte von C[] in D nur finden, wenn dieser Wert in D existiert (die durch untere Schranke Funktion zurück mit Index überprüft werden kann) .

  Anzahl + = oberer_bound_index - lower_bound_index;

Zeit Komplexität von diesem ist auch O(n^2 logn).