Frage zur Laufzeitkomplexität best, average and worst case (informatik)?
Grüßt euch ihr Lieben,
ich habe folgendes Problem. Ich muss bei einem fiktiven Beispiel aus dem wahren Leben (Algorithmus) eine Laufzeitkomplexität ( best, average and worst case) zuorden.
Der fiktive fall lautet:
Bei einem fiktiven Speed-dating gibt es für jede Person einen optimalen Partner. Jede Beziehung ist hier symmetrisch (d.h. der optimale Mann für eine Frau hat immer eben diese als optimale Frau) und dass man das in einem 5-minütigen in einem Gespräch feststellen kann.
Haben Mann und Frau sich in einem Gespräch als optimale Partner erkannt, können beide aus dem Speed-Dating ausscheiden. Im Speed-Dating führen eine gleiche Anzahl n von Männern und Frauen, d.h. insgesamt 2n Personen Gespräche.
Ich wollte das der Notaion O(n^2) zuordnen, aber das macht irgendwie kein Sinn, weil hier beide aus dem Speed-dating ausscheiden, wenn Sie sich als perfekte Partner erkannt haben. Hat jemand eine Idee wie man diesen Fall als Algorithmus in best, aver.. und worst case zuordnen kann?
1 Antwort
Du beschreibst zwar ein Problem, aber keinen Algorithmus dazu.
Die Problembeschreibung suggeriert, dass im ersten Schritt n Gespräche gleichzeitig stattfinden. Dann wäre alles spätestens nach n Runden fertig. Wenn der Algorithmus alle Paare für eine Runde in konstanter Zeit bestimmen kann, liegt die Gesamtlaufzeit in 𝓞(n) (worst case).
Bestenfalls passt alles schon in der ersten Runde. Dann ist liegt die Gesamtlaufzeit in 𝓞(1) (best case).
Für die mittlere Laufzeit musst Du abschätzen, wie viele Paare in jeder Runde im Durchschnitt ausscheiden und wieviele Kandidaten die übrigen Männer/Frauen noch haben. Für die erste Runde ist das einfach: Im Durchschnitt scheidet genau ein Paar aus, und die übrigen haben zwei Kandidaten weniger. Ab dann wird es kompliziert: Im Schnitt scheiden zwar immer mehr Paare aus, aber möglicherweise sind diese bei einigen Teilnehmern schon aus der Liste gestrichen. Ich vermute, dass die Gesamtaufzeit effektiv auf 𝓞(√n) schrumpft, kann es aber nicht beweisen.
_________________________________________
Falls Gespräche nicht parallel stattfinden können, kann man leicht einen Algorithmus finden, der in 𝓞(n²) liegt: Ein Mann redet nacheinander mit allen n Frauen und scheidet bei seiner "richtigen" aus. Das braucht höchstens n Gespräche in der ersten Runde, n-1 in der zweiten usw. Insgesamt sind das bis zu n+(n-1)+(n-2)+...+2∊𝓞(n²) Gespräche.
Schlimmstenfalls müssen alle diese Gespräche tatsächlich geführt werden (denk Dir ein Beispiel aus).
Bestenfalls passt bei jedem Mann gleich das erste Gespräch. Dann ist man nach n Gesprächen durch.
Und im Mittel führt jeder halb so viele Gespräche pro Runde, aber n/2+(n-1)/2+(n-2)/2+...+2/2 liegt ebenso in 𝓞(n²). Man spart also im Mittel nur die halbe Zeit.
Aber vielleicht gibt es ja einen anderen Algorithmus, der zumindest im Mittel besser abschneidet?
