Frage zur Laufzeitkomplexität best, average and worst case (informatik)?

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

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?

Danke. Sehr hilfreich!!!

0

Worst case Laufzeit:

Stell dir einen langen Tisch mit 2n Stühlen vor(n Stühle vor dem Tisch und n Stühle hinter dem Tisch.) Nun stell dir vor hinter dem Tisch sitzen die n Frauen und vor dem Tisch sitzen die n Männer. Die Frauen bewegen sich nicht und bleiben jede Runde sitzen und die Männer rotieren alle einen Platz nach links wenn sie nach 5 min nicht die perfekte Frau gegenüber gefunden haben (der der schon am linken Ende des Tisches saß wechselt ans rechte Ende) . Stell dir nun vor jeder Mann sitzt einen Platz rechts neben seiner perfekten Frau das heißt jeder Mann müsste n mal nach links rotieren bis er die perfekte Frau findet. Da es n Männer gibt die n mal rotieren müssen (da niemand vor dem n-ten mal die perfekte Frau findet scheidet auch kein paar aus) benötigt es n*n überprüfungen bis der perfekte Partner gefunden wurde. Also O(n^2)

Best case:

Jeder sitzt bereits vor seinem perfekten Partner, Mann muss also für jedes Paar einmal prüfen, bei n paaren also eine Laufzeit von O(n)

Avg Case:

Ohne das ausscheiden von paaren würde sich jeder der n Männer mit durchschnittlich n/2 Frauen treffen bis beide den perfekten Partner finden, also (n/2)*n. In O notation also O(n^2) was das ausscheiden jetzt verändert weiß ich auf die schnelle nicht aber hier ist ein link in dem das mit der avg Laufzeit erklärt wird

https://hpi.de/friedrich/teaching/units/amortisierte-analyse.html

Supi danke. Das Beispiel hat wirklich geholfen, weiß jetzt ungefähr, wie ich an die Aufgabe rangehen muss.

Lg Schönen Sonntag

0
Da es n Männer gibt die n mal rotieren müssen (da niemand vor dem n-ten mal die perfekte Frau findet scheidet auch kein paar aus) benötigt es n*n überprüfungen bis der perfekte Partner gefunden wurde. Also O(n^2)

Das verstehe ich nicht. n Männer können doch gleichzeitig in einem Takt weiter rutschen. Also 𝓞(n).

1
Jeder sitzt bereits vor seinem perfekten Partner

Hier auch: Dann sind doch 5 Minuten später alle glücklich. Also 𝓞(1).

1
@ralphdieter

Ich davon ausgegangen das der Algorithmus der beschrieben wird für jedes Paar am Ende der 5 Minuten prüft ob sie das perfekt paar waren und somit in jeder Runde Anzahl verbliebener Paare mal konstantem Zeitaufwand zum prüfen eines Paares benötigt wird. Es sind einfach zwei verschiedene Herangehensweisen.

Um es an einem anderen Beispiel zu erklären, stell dir folgendes Programm vor:

x = input(binärzahl)

return x + x

Sagen wir der Input ist eine binärzahl x der Länge n. Es ist nun zum einen möglich zu argumentieren der Aufwand die Operation x + x zu rechnen ist O(n) da mann um zwei binärzahlen zu addiere n mal die einzelnen bits addieren muss. Es ist aber auch möglich zu sagen x + x zu rechnen ist eine einzelne Operationen und wir haben deshalb einen Aufwand von O(1)

Beide Argumentation sind richtig, betrachten das ganze nur aus verschiedenen Sichtweisen

0

Was möchtest Du wissen?