Buchstaben normieren

[Christian Kruse]

Hallo seth,

hier hat sich ein Verpeiler eingeschlichen: der Aufwand zum Sortieren bei Quicksort ist
natuerlich O(n * ld n), nicht O(ld n) -- das waere ja traumhaft.

quicksort liegt iirc im worst case in O(n^2) und bloss "im mittel" in O(n*log(n)).

Quicksort liegt dann bei O(n²), wenn das Pivotelement stets so gewählt wird, dass es das
groesste oder das kleinste Element des (Teil-)Arrays ist, also wenn als Pivot-Element
immer das Element am Ende des (Teil-)Arrays gewaehlt wird und der zu sortierende Array
schon sortiert ist. Und genau deshalb wird idR (auch in der von PHP verwendeten libc) kein
reiner Quicksort, sondern ein Quicksort mit “Meridian aus drei“ oder ein “randomisierter
Quicksort” eingesetzt. Das macht dann halt die Wahrscheinlichkeit von O(n²) so klein, dass
man effektiv von O(n ld n) ausgehen kann.

mergesort liegt bspw. in O(n*log(n)).

Ja, aber Mergesort kann nicht “in place” arbeiten, die Speicherkomplexitaet ist daher
hoeher (es werden temporaere Arrays benoetigt).

Grüße,
 CK