Algorithmen und Datenstrukturen · Middle · Frage 8 von 75
Wann kann Counting Sort O(n log n) schlagen?
- 1Wenn das Array schon fast vollständig sortiert ist
- 2Wenn die Elemente Strings gleicher Länge sind
- 3Bei kleinen ganzzahligen Schlüsseln im Bereich k: O(n + k)
Antwort zeigen
Richtige Antwort: Bei kleinen ganzzahligen Schlüsseln im Bereich k: O(n + k)
Erklärung
Counting Sort vergleicht keine Elemente: es zählt, wie oft jeder Schlüssel vorkommt, und schreibt sie der Reihe nach zurück. Ideal für Alter oder Noten, aber ein riesiger Schlüsselbereich macht das Zähl-Array zu groß.