Ich habe 4 Arrays A , B , C , D der Größe n . n ist höchstens 4000. Die Elemente jedes Arrays sind 30 Bit (positive / negative) Zahlen. Ich möchte die Anzahl der Möglichkeiten wissen, A[i]+B[j]+C[k]+D[l] = 0 kann gebildet werden, wo 0 <= i,j,k,l < n .
Der beste Algorithmus, den ich abgeleitet habe, ist O(n^2 lg n) , gibt es einen schnelleren Algorithmus?
Ok, hier ist mein O (n ^ 2lg (n ^ 2)) Algorithmus -
Angenommen, es gibt vier Arrays A [], B [], C [], D []. Wir wollen die Anzahl der Wege finden, auf denen A [i] + B [j] + C [k] + D [1] = 0 gemacht werden kann, wobei 0 & lt; = i, j, k, l & lt; n.
Summiere also alle möglichen Anordnungen von A [] und B [] und lege sie in ein anderes Array E [], das die n * n Nummer des Elements enthält.
%Vor%Die Komplexität des obigen Codes ist O (n ^ 2).
Machen Sie dasselbe für C [] und D [].
%Vor%Die Komplexität des obigen Codes ist O (n ^ 2).
Sortieren Sie nun AUX [], so dass Sie die Anzahl des Auftretens eines eindeutigen Elements in AUX [] leicht finden können.
Die Sortierkomplexität von AUX [] ist O (n ^ 2 lg (n ^ 2)).
deklariere jetzt eine Struktur -
%Vor%Platziere nun in der Struktur F [] das einzigartige Element von AUX [] und die Zeit, in der sie erschienen sind.
%Vor%Seine Komplexität ist O (n ^ 2)
Führe jetzt für jedes Element von E [] folgendes aus:
%Vor%Für die Schleife i wird insgesamt n ^ 2 Anzahl der Iterationen durchgeführt Iteration für die binäre Suche lg (n ^ 2) Vergleich ist erfolgt. Also insgesamt Komplexität ist O (n ^ 2 lg (n ^ 2)).
Die Anzahl der Wege, zu denen 0 erreicht werden kann, ist = möglichQuardtupple.
Jetzt können Sie die stl map / binary search verwenden. Aber stl Karte ist langsam, also ist es besser, binäre Suche zu verwenden.
Ich hoffe, meine Erklärung ist klar genug, um es zu verstehen.
Ich stimme nicht zu, dass Ihre Lösung in der Tat so effizient ist, wie Sie sagen. In Ihrer Lösung ist das Auffüllen von E [] und AUX [] jeweils O (N ^ 2), also 2.N ^ 2. Diese werden jeweils N ^ 2 Elemente haben.
Erzeugung von x = O (N)
Sortieren von AUX = O ((2N) * log ((2N)))
Die binäre Suche nach E [i] in AUX [] basiert auf N ^ 2 Elementen, die in N ^ 2 Elementen zu finden sind.
Sie arbeiten also immer noch mit N ^ 4, plus zusätzlicher Arbeit, um die Zwischenarrays zu erzeugen und die N ^ 2 Elemente in AUX [].
zu sortierenIch habe eine Lösung (in Arbeit), aber ich finde es sehr schwierig zu berechnen, wie viel Arbeit es ist. Ich habe meine vorherige Antwort gelöscht. Ich werde etwas veröffentlichen, wenn ich selbstsicherer bin.
Ich muss einen Weg finden, um O (X) + O (Z) + O (X ^ 3) + O (X ^ 2) + O (Z ^ 3) + O (Z ^ 2) + X zu vergleichen .log (X) + Z.log (Z) bis O (N ^ 4) mit X + Z = N.
Es ist deutlich weniger als O (N ^ 4) ... aber um wieviel ???? Meine Mathe versagt mich hier ....
Das Urteil ist falsch. Die gelieferte Lösung erzeugt Arrays mit der Größe N ^ 2. Es arbeitet dann auf diesen Arrays (Sortierung usw.).
Daher sollte die Ordnung der Arbeit, die normalerweise O (n ^ 2.log (n)) wäre, durch n ^ 2 ersetzt werden. Das Ergebnis ist daher O ((n ^ 2) ^ 2.log (n ^ 2))
Tags und Links algorithm