Wie Median effizient berechnen?
Ich habe Liste von betrachteten Merkmalen x1 , ... xm habe und deren absoluten häufigkeiten h1, ... hm.
Nun soll ich ein Programm schreiben, dass in nur in abhängigkeit von m nicht von der ganzen Stichprobe den Median berechnet. Wie geht das ?
Bei uns war m immer der Modalwert…ist bei euch m der größte x-Wert oder wie kann ich mir das vorstellen und was hat der Median mit der Häufigkeit zu tun?
Ne also es ist einfach eine Liste von Merkmalen der Länge m die noch nicht sortiert ist.
Der Median ist der Wert der in der Mitte der ganzen Stichproben Liste ist , oder nicht ?
1 Antwort
Also die Methode die einem sofort einfallen würde wäre vermutlich zuerst die Werte zu sortieren und danach von der sortierten Liste den mittleren Wert zu bestimmen.
Man muss aber ja nur den "mittleren Wert" suchen, weswegen die Reihenfolge der Werte davor und danach egal ist.
Meine Idee es Effizienter zu gestalten wäre, eine Algorithmus, der ähnlich wie Quicksort ist, zu benutzen, nur, dass der Algorithmus den Median Sucht.
Also:
Lege ein Index (zum Beispiel k=1) fest und prüfe dann bei jedem Wert, ob der über oder unter dem Wert mit dem Index (also x_k) liegt. Dabei erhälst du zwei Listen
Summiere dann von den beiden Listen jeweils die absolute Häufigkeit, und prüfe dann ob der Median gleich x_k ist (du musst dir hier jedoch selber überlegen wie genau du das prüfen musst)
Falls ja hast du den Median gefunden, falls nein, musst du die Liste wählen, wo der Median drin sein muss und diese wieder in zwei Listen aufspalten. (Und so weiter, du musst aber dafür noch die Absoluten Häufigkeiten der Werte die vor und nach der Liste sind zwischenspeichern)
Das funktioniert zumindest wenn die Summe der absoluten Häufigkeiten ungerade ist, da der Median dann einer der Werte der Liste ist. Wenn jedoch die Summe gerade ist, ist der Median gleich dem Mittelwert zweier Werte (die gleich sein könnten), du musst hier also dann noch ein paar Gedanken machen, wie du die Beiden werte bestimmst.
Die Laufzeit müsste hier auf jeden Fall besser sein, weil du eben nicht die ganze Liste sortierst, sondern werte einfach streichen kannst, da du bei denen weißt, dass sie garantiert nicht der Median sind
Wird hier behauptet , man könne den M bestimmen , ohne die ganze Stichprobe zu kennen ?
Man kennt hier die ganze Stichprobe, es ist gegeben welche Werte wie oft vorkommen.
Lege ein Index (zum Beispiel k=1) fest ................ich nehme irgendeinen Wert und habe dann schlimmstenfalls in der eine Liste keine und in der anderen Liste alle ?
Ja das kann passieren. Das ist der worst case.
und sortieren ist nicht so schnell? Vor allem weil hier doch die Häufigkeiten vorliegen ?
Nein, weil sortieralgorymen O(n*log(n)) als erwartete laufzeit haben.
Quickselect ( so lautet der Algorithmus, ist aber etwas angepasst) hat die Laufzeit O(n)
ob ich die Frage richtig verstanden habe ?
.
Wird hier behauptet , man könne den M bestimmen , ohne die ganze Stichprobe zu kennen ?
Lege ein Index (zum Beispiel k=1) fest ................ich nehme irgendeinen Wert und habe dann schlimmstenfalls in der eine Liste keine und in der anderen Liste alle ?
.
Beispiel
1 1 2 3 4 5 ( noch unsortiert )
ich wähle 1