Algorithmus entwerfen

[InformaticStudent]

Hallo Leute!
ich schreibe schon sehr bald (in 3 Tagen) eine wichtige Klausur (Algorithms & Datastructures) und bereite mich gerade darauf vor.
Leider komme ich bei dieser Aufgabe nicht weiter, und wäre für jede Hilfe sehr dankbar!

Aufgabe: Man soll einen Algorithmus entwerfen, der für eine gegebene Menge s von n reellen Zahlen und einem gegebenen positiven k <= n die Teilmenge A_k c s der k dem Median von s am nächsten liegenden Zahlen berechnet. Die "Nähe" zweier Zahlen ist der Absolutbetrag ihrer Differenz. Welche Laufzeit kann man erzielen? Ist die Antwort A_k immer eindeutig?

Ich verzweifle leider schon an der Realisierung und freue mich über eure Antworten!

 

[httpdigest]

Zentral für die Aufgabe ist ja erstmal die Berechnung des Medians. Was ist der Median und was genau musst du tun, um ihn zu ermitteln?
Auch wichtig in der Aufgabenstellung ist die Erwähnung, dass es sich um reelle Zahlen handelt, also insbesondere keine ganzen Zahlen und auch nicht in einem min/max Intervall. Damit fällt schon mal ein wichtiger/nützlicher (Teil-)Algorithmus hierfür weg, den man hätte nutzen können.

 

[fhoffmann]

Eine Möglichkeit wäre sicher, die Menge s zu sortieren; der Rest ist dann einfach. Damit wäre die Laufzeit des Algorithmus' durch die Laufzeit der Sortierens beschränkt. Ob es noch eine schnellere Möglichkeit gibt, weiß ich nicht (würde es aber bezweifeln).

Die Menge A_k ist sicherlich nicht eindeutig. Nimm dir für solche Fragen ein kleines Beispiel: Es könnte s = {1, 2, 3} und k = 2;
dann ist der Median = 2 und für A_k gibt es die Möglichkeiten {1, 2} und {2, 3}.

 

[mihe7]

Ob es noch eine schnellere Möglichkeit gibt, weiß ich nicht (würde es aber bezweifeln).

Man möchte es kaum für möglich halten, aber der Blum-Floyd-Pratt-Rivest-Trijan-Algorithmus löst das Problem in O(n).

 

[InformaticStudent]

Danke für jede Antwort!