Wie geringste Absolutdifferenz zum Median bestimmen?

[Screen]

Hallo,

ich muss einen Algorithmus entwickeln ,der in einem Array der Länge n und einer Zahl k mit 1<=k<=n , die k Zahlen mit der geringsten Absolutdifferenz zum Median bestimmt. In der linearen Komplexität von O(n).

Hab schon die Suche und Google benutzt, aber nichts braubares gefunden.

Also einfach den Medien bestimmen und dann jeden Wert im Array von ihm subtrahieren und dann den Lösungsarray sortiern geht nicht, weil ich dann dann der Algo mehr als O(n) braucht.

Eine Lösungsstrategie wäre den Mediean per Select Algorithmus in O(n) zu finden, aber was dann müsste ich trotzdem noch mal sortieren und dann wäre es wieder mehr als O(n).

Wie kann ich das realisieren?

 

[Timothy Truckle]

ich muss einen Algorithmus entwickeln ,der in einem Array der Länge n und einer Zahl k mit 1<=k<=n , die k Zahlen mit der geringsten Absolutdifferenz zum Median bestimmt. In der linearen Komplexität von O(n).

deklariere 2 Variablen:

aktuellerMinMedian

und

minMedianIndex

Dann läuft Du über das Array
für jeden Eintrag berechnest den aktuellen Median und vergleichst ihn mit der Variablen

aktuellerMinMedian

.
Wenn der Berechnete Median kleiner ist ersetzt du den Inhalt von

aktuellerMinMedian

und

minMedianIndex

mit den aktuellen Werten.

Wenn die Objekte eine eigene Variable für den Median haben braucht du nur den Index zu speichern.

bye
TT

 

[Screen]

deklariere 2 Variablen:

aktuellerMinMedian

und

minMedianIndex

Dann läuft Du über das Array
für jeden Eintrag berechnest den aktuellen Median und vergleichst ihn mit der Variablen

aktuellerMinMedian

.
Wenn der Berechnete Median kleiner ist ersetzt du den Inhalt von

aktuellerMinMedian

und

minMedianIndex

mit den aktuellen Werten.

Wenn die Objekte eine eigene Variable für den Median haben braucht du nur den Index zu speichern.

bye
TT

Ich verstehe leider nicht was du meinst.
Wie kann ich für jeden Eintrag ( Element) den aktuellen Median berechnen? Ist er nicht für jedes Elment gleich, da es im Array nur einen "wirklichen" Median gibt. Oder irre ich mich?

 

[Timothy Truckle]

Ich verstehe leider nicht was du meinst.
Wie kann ich für jeden Eintrag ( Element) den aktuellen Median berechnen? Ist er nicht für jedes Elment gleich, da es im Array nur einen "wirklichen" Median gibt. Oder irre ich mich?

Sorry, habe nicht jeden Tag mit Statistik zu tun...

Wenn ich aber richtig erinnere erlaubt O(n) ja auch mehrere Durchläufe. Die Bearbeitungszeit muß ja nur linear mit der Elementezahl wachsen. (Man korrigiere mich, wenns nicht stimmt.) Also kannst Du im ersten Durchlauf den Median berechnen und im zweiten
Das Element mit der geringsten Abweichung suchen.

bye
TT

 

[Gast2]

Ganz genau, bei einer Eingabelänge von n liegt eine Laufzeit von 2*n in O(n).
Du kannst also Problemlos zwei Durchläufe machen.

 

[DrZoidberg]

Du könntest es mit java.util.TreeSet versuchen.
Hier mal eine Methode, die die k kleinsten Zahlen in einer Liste findet. Wenn ich mich nicht täusche, sollte der Code O(n) sein.

static double[] getKSmallest(double[] array, int k) {
    TreeSet<Double> set = new TreeSet<Double>();
    for(double d: array) {
        if(set.size() < k) set.add(d);
        else if(!set.contains(d)) {
            double last = set.last();
            if(last > d) {
                set.remove(last);
                set.add(d);
            }
        }
    }
    double[] result = new double[set.size()];
    int i = 0;
    for(double d: set) result[i++] = d; 
    return result;
}

 

[Timothy Truckle]

Du könntest es mit java.util.TreeSet versuchen.
Hier mal eine Methode, die die k kleinsten Zahlen in einer Liste findet. Wenn ich mich nicht täusche, sollte der Code O(n) sein.

Laut API:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

ist also zu schnell...

bye
TT

 

[DrZoidberg]

Die Methode fügt aber bis zu n mal einen Wert hinzu. Damit kommen wir dann auf n*log(k). Gilt das dann noch als O(n)?

 

[Bleiglanz]

Da oben steht möglicherweise Zeugs das nicht ganz richtig ist (glaub ich).

1) Das Problem ist es erst mal, den Median in O(n) zu finden, ohne eine vollständige Sortierung zu nehmen

Selection algorithm - Wikipedia, the free encyclopedia

2) Danach einmal durchlaufen, um alle Absolutdifferenzen zu finden, das ist sicher O(n)

3) Wenn du jetzt mit TreeSet dran gehst, dann wird jedes add die Zeit O(log n) erfordern, wodurch 3) zu O(n log n) würde, was nicht erlaubt ist

Algorithm to find k smallest numbers in array of n items - Stack Overflow