Summe aller Elemente von 3 verschiedenen Arrays

Ich möchte und optimierten Algorithmus, um die Summe jedes einzelnen Elements des Arrays zu finden.Summe aller Elemente von 3 verschiedenen Arrays

zum Beispiel lassen 3-Array:

a = [1,2,3,4]; 
b = [5,6]; 
c = [8,9];

dann Endsumme gleich sein wird:

sum(1,5,8)+sum(1,5,9)+sum(1,6,8)+sum(1,6,9)+sum(2,5,8)...+sum(4,6,9)

Ich habe versucht zu tun, aber der Algorithmus Ich hatte Zeit, Komplexität O verwendet (n^3), also möchte ich etwas weniger als diese Komplexität.

Hier ist mein Algorithmus:

sum = 0  
for(i=0;i<a.size();i++) 
     for(j=0;j<b.size();j++) 
      for(k=0;k<c.size();k++) 
       sum = sum+a[i]+b[j]+c[k];

Quelle

2017-06-03 Mayank Joshi

Was haben Sie versucht? – Novaterata

Ich bin mir nicht sicher, was Sie versuchen zu tun.Wenn Sie versuchen, das zu tun, was ich denke, ist das ein faktorieller Zeitalgorithmus. bearbeite deine Frage. – Makogan

Auch das ist kein 2d-Array. – Makogan

Für dieses Beispiel a, b und c haben 4, 2 und 2 Elemente sind. Wenn Sie sie in jeder Kombination hinzufügen möchten, werden 4 * 2 * 2 = 16 Begriffe hinzugefügt. In diesem Sinne erscheint jedes Element von a viermal, weil es zu 2 * 2 = 4 Kombinationen von Elementen von b und c hinzugefügt wird. Gleichermaßen erscheint jedes Element von b (oder c) acht Mal, weil es zu jeder 4 * 2 = 8 Kombination von jedem Element von a und c (oder b) hinzugefügt wird.

Also, in der endgültigen Summe, jedes Element von a erscheint 4 mal und jedes Element von b und c erscheint 8 mal. Sobald Sie das herausgefunden haben, können Sie eine geringere Anzahl an Multiplikationen und Additionen durchführen, um das Ergebnis zu erhalten (einfach die Summe der Elemente der einzelnen Arrays und dann diese Summen mit 4, 8 bzw. 8 multiplizieren).

Quelle

2017-06-03 03:18:29 0605002

Um die Summe der einzelnen Arrays weiter zu optimieren, berechnen Sie sie vorher und multiplizieren Sie sie mit dem Produkt aus den Größen der anderen beiden Arrays. – ithenoob

Jedes Element von a wird in Summen mit jedem Element von b und jedem Element von c angezeigt.

Dies bedeutet, dass jedes Element in a in einer Anzahl von Summen gleich b.length * c.length erscheint.

von der Brute-Force-Pseudo-Code Dies ist auch leicht zu sehen: (modifiziert zur besseren Lesbarkeit)

for i = 0 to a.length 
    for j = 0 to b.length  // happens once for each i 
     for k = 0 to c.length // happens b.length times for each i 
     sum += a[i] + ... // happens b.length * c.length times for each i

diese Verallgemeinerung, kommen wir mit dem folgenden Algorithmus auf:

Summe alle Elemente a, multiplizieren Sie das Ergebnis mit b.length * c.length.
Summe aller Elemente b, multiplizieren Sie das Ergebnis mit a.length * b.length.
Summe aller Elemente c, multiplizieren Sie das Ergebnis mit a.length * b.length.
Geben Sie die drei oben genannten Werte zusammen.

Dies ist ein O(n) Algorithmus, wo n die Gesamtzahl der Elemente oder die durchschnittliche Anzahl von Elementen pro Array ist.

Quelle

2017-06-03 07:09:01 Dukeling

Summe aller Elemente von 3 verschiedenen Arrays

Antwort

Verwandte Themen