Hey, ich bin gerade an eine Projekt am Optimiren und zwar ich muss aus Arrays welche aus ints bestehen sehr heufig (30 mal die Sekunde) den Median berechnen! die Arrays haben eine Länge von 1e3 bi 1e6 ,hier bei ist es egal ob es zwei oder ein ergebnis gibt! die Felder sind nicht sortiert! So hier ist meine Algorithmus! könnte ihr mal drüber schauen ob das ganze so weit Klappt oder ob jemand noch ein paar optimirungen vorschlagen kann!:
Ich glaube die Komplexität ist O(n) bitte Korrigirt mich wenn ich hier falsch Liege und könnte jemand den Algorithmus noch mal kontrolieren!
Danke Schon mal!
Java:
...
medianSuch(array, 0, (array.length - 1))
...
private int medianSuch(int[] array, int l, int r) {
// Median bestimmen
int p = (l + r) / 2;
// Sotiren des Feldes so das Median in der Mitte
int pn = partition(array, 0, array.length - 1, p);
if (l == r) {
// Median gefunden
return array[array.length / 2];
}
if (pn - 1 >= array.length / 2) {
// k >= n/2 ,dann suche Links
return medianSuch(array, l, pn);
} else if (pn + 1 <= array.length / 2) {
// g <= n/2 ,dann suche Rechts
return medianSuch(array, pn + 1, r);
} else {
// Median Gefunden
return array[pn];
}
}
private int partition(int[] array, int l, int r, int p) {
// pn = Position des Median
int pn = l;
int pv = array[p];
// Median-Element an das Ende Verschieben um Platz zu haben
swap(array, p, r);
// Elemente kleiner oder gleich Median-Element nach vorn tauschen
for (int i = 0; i < r; i++) {
if (array[i] <= pv) {
// pn nach jedem tausch erhöhen
swap(array, pn++, i);
}
}
// Median zurück tauschen
swap(array, r, pn);
// neue Median Position zurück geben
return pn;
}
private void swap(int[] array, int idx1, int idx2) {
int tmp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = tmp;
}Ich glaube die Komplexität ist O(n) bitte Korrigirt mich wenn ich hier falsch Liege und könnte jemand den Algorithmus noch mal kontrolieren!
Danke Schon mal!
