Algorithmen und Datenstrukturen · Middle · Frage 7 von 75
Warum kann kein vergleichsbasiertes Sortierverfahren im schlimmsten Fall O(n log n) schlagen?
- 1Sortieren kopiert das ganze Array immer log n Mal
- 2Es muss n! Reihenfolgen unterscheiden: log(n!) ≈ n log n
- 3Jeder Vergleich kostet im Speicher O(log n) Zeit
Antwort zeigen
Richtige Antwort: Es muss n! Reihenfolgen unterscheiden: log(n!) ≈ n log n
Erklärung
Jeder Vergleich hat zwei Ausgänge, k Vergleiche unterscheiden also höchstens 2ᵏ Reihenfolgen. Um eine von n! Reihenfolgen zu bestimmen, braucht man log₂(n!) Vergleiche, also Θ(n log n).