Ich versuche, einen schnellen Algorithmus zur Berechnung zu finden
die Menge b[i]= med |y_i+y_j|, 1<=j!=i<=n when
Die y_1,...,y_n sind bereits sortiert (also b[] ist ein Vektor
gleich lang wie y[] ).
Ich nehme an, dass alle Elemente von y[] eindeutig sind
und das n ist gerade.
Also, der folgende Code berechnet den b[i] den naiven ( O(n**2) ) Weg:
(Ich schrieb dies in R für Bequemlichkeit, aber ich bin sprachunabhängig)
Ich habe einen vorläufigen Vorschlag - unten -, um es in O(n) zu machen.
Aber es funktioniert nur, wenn y[] positive Zahlen enthält.
Meine Frage ist: Wie soll ich den schnellen Algorithmus ändern?
funktioniert auch, wenn y[] sowohl positiv als auch enthält
negative Zahlen? Ist das überhaupt möglich?
Und der Code unter dem (vorläufigen) O(n) Weg
(Ich schrieb dies in R für Bequemlichkeit, aber ich bin sprachunabhängig)
Einfaches, anschauliches Beispiel. Wenn wir einen Vektor der Länge 4 haben
%Vor%Dann, zum Beispiel für i = 1, sind die 3 absoluten paarweisen Summen
%Vor%und ihr Median ist 1.
Dann, zum Beispiel für i = 2, sind die 3 absoluten paarweisen Summen
%Vor%und ihr Median ist 3.
Hier ist ein längeres Beispiel mit positiven und negativen y[] :
und hier ist meine neue b_slow[] (das ist die Grundwahrheit, berechnet auf naive Art):
Aber jetzt passt meine neue a_fast[] nicht mehr:
Hier ist meine Implementierung von Francis 'Lösung (bis zu dem Punkt, wo wir zwei sortierte Arrays haben, deren Median leicht zu berechnen ist). Ich habe es in R gemacht, um im Geiste der Frage zu bleiben.
Nichtsdestoweniger scheint mir ein Korrekturfaktor für den Index (das ww in dem Code unten) zu fehlen, so dass der untenstehende Code manchmal ein wenig abweicht. Dies liegt daran, dass in der obigen Definition die Mediane über n-1 Beobachtungen (i! = J) berechnet werden.
%Vor%Hier ist eine O (Nxln (N) xln (N)) Lösung:
für alle i:
1) finde Element k wie j<k <=> y[j]+y[i]<0 (Dichotomie, O (ln (N)))
k trennt zwei sortierte Listen: eine über -y [i], die andere unter -y [i], für die das Vorzeichen geändert werden soll, um abs (y [i] + y [j]) zu erhalten. Jetzt suchen wir nach dem Median dieser Listen.
Von hier aus ist es nur das Problem von Finden des Medians zweier sortierter Listen , n-mal wiederholt.
2) Wählen wir das Maximum (M = abs (y [1] -y [i]) oder M = abs (y [Größe] -y [i])) und das Minimum (m um k) dieser Listen und starten Sie eine Dichotomie (O (ln (N)). Beginnen wir mit der Auswahl der Mitte (M + m) / 2 ... in jedem Stadium, wählen Sie die Mitte ...
3) Stufe dieser großen Dichotomie: Wieviele Items y [j] + y [i] sind über (M + m) / 2 in der ersten Liste? Noch einmal eine Dichotomie ... O (ln (N)). Wie viele Elemente -y [j] -y [i] sind über (M + m) / 2 in der zweiten Liste? Erraten Sie, was ? Dichotomie ... Summe diese zwei Zahlen. Wenn es über (Größe-1) / 2 ist, ist m = (M + m) / 2. Ansonsten M = (M + m) / 2.
4) Wenn m = M stopp! b[i]=m;
Ich nehme an, jemand wird mit einer besseren Lösung kommen ...
Edit: Ich sollte @ user189035 für seine Verbindung zu einem O (ln (n + m)) Algorithmus danken, um den Median von zwei sortierten Listen zu berechnen. Wie findet man das k-kleinste Element in der Vereinigung von zwei sortierten Arrays?
Tschüss,
Tags und Links algorithm language-agnostic c c++