Kann mir jemand den Bucketsort Laufzeitanalyse erklären?
Ich verstehe nicht was O(n) oder O(n+k) bedeutet. Weiss es jemanden?
1 Antwort
O(n) bedeutet das ein Algorithmus in linearer Zeit abläuft. Also proportional. Sprich: Bei 1 Element = 1 Zeiteinheit. Bei 100 = 100 Zeiteinheiten, bei 10.000 = 10.000 Zeiteinheiten, usw.
O(n+k) das Gleiche, nur +k, also bspw. sei k = 100, d.h. 1 = 101, 100 = 200, 10.000 = 10.100, dort wird k einfach addiert.
O(k) = k für alle Elemente, d.h. sei k = 100, 1 = 100, 100 = 100, 10.000 = 100 Zeiteinheiten.
Man betrachtet oft die asymptotische laufzeit, sprich für ganz große n Elemente. Deswegen geht der Limes gegen Unendlich und konstante Faktoren werden dann unwichtig. Das ist für die asymptotische Betrachtung einfacher.
Im Grunde hast du Recht, die Laufzeit O(n) ist besser als O(n + k); aber für große n ist es (relativ) unrelevant.
ey vielen Dank dir ehrlich! Hast du vielleicht noch ein stuktogramm vom bucketsort? finde gar nichts
z.B. hier: https://www.happycoders.eu/de/algorithmen/o-notation-zeitkomplexitaet/
Einfach Vergleich O-Notation googlen und dann auf Bilder. Das ist ziemlich basic stuff, davon gibt's reichlich.
finde irgendwie nichts für O(n+k) oder kann man das anders schreiben?
O(n) und O(n+k) ist die gleiche asymptotische Komplexität da k nur der absolute Wert in einer linearen Funktion ist. O(n+k) für n = unendlich ist unendlich deswegen irrelevant
achsoo, aber warum ist der Bestcase identisch mit den Worstcase: O(n+k)!