Algorytmy i struktury danych · Middle · Pytanie 7 z 75
Dlaczego żadne sortowanie przez porównania nie pobije O(n log n) w najgorszym przypadku?
- 1Sortowanie zawsze kopiuje całą tablicę log n razy
- ✓Poprawna odpowiedź: Musi rozróżnić n! kolejności: log(n!) ≈ n log n
- 3Każde porównanie zajmuje O(log n) czasu w pamięci
Wyjaśnienie
Każde porównanie ma dwa wyniki, więc k porównań rozróżnia najwyżej 2ᵏ kolejności. Aby wskazać jedną z n! kolejności, potrzeba log₂(n!) porównań, czyli Θ(n log n).