Bucket Sort: Komplexität

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
jr29zyni
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 14. Apr 2016 15:03

Bucket Sort: Komplexität

Beitrag von jr29zyni » 6. Aug 2016 10:09

Guten Morgen,

zur Bucket Sort-Komplexität steht im Transscript:
  • [...] Alle anderen Schritte des Algorithmus sind asymptotisch geringer. Insgesamt ist die Laufzeit linear in der Summe aller Stringlängen.
Warum diese Summe aller Stringlängen (=: s) in die asymptotische Komplexität "hineinspielt" ist mir klar.
Also wäre Bucket Sort nach dem Transscript in O(s).
Aber warum kann man davon ausgehen, dass das Anschauen und Einsortieren der Strings in B (was durch das s ja ausgedrückt wird) asymptotisch schneller geht als das Einsortieren aus den Buckets in die Liste S am Ende jeder Iteration?
Meiner Ansicht nach bräuchte das je Iteration k Schritte (wobei k = Anz. der Buckets = Anz. der Zeichen im Alphabet). Wir haben l Iterationen (mit l = Länge des längsten Strings).
Ich würde den Algorithmus dann auf O(s + l*k) abschätzen, da l*k ja asymptotisch nicht unbedingt schneller ist als s...
Oder mache ich einen Denkfehler?

Edit: Ich glaube ich habe es verstanden: Die Anzahl, die in die Buckets einsortiert wird, ist offensichtlich auch die, die dann in S gelegt wird. Also wären wir eigentlich bei O(2s) = O(s).

LG
Jonas

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Bucket Sort: Komplexität

Beitrag von Prof. Karsten Weihe » 7. Aug 2016 18:20

jr29zyni hat geschrieben: Edit: Ich glaube ich habe es verstanden: Die Anzahl, die in die Buckets einsortiert wird, ist offensichtlich auch die, die dann in S gelegt wird. Also wären wir eigentlich bei O(2s) = O(s).
Ja

KW

Antworten

Zurück zu „AuD: Vorlesung“