Algorytmy i struktury danych · Middle · Pytanie 8 z 75
Kiedy sortowanie przez zliczanie może pobić O(n log n)?
- 1Gdy tablica jest już prawie w pełni posortowana
- 2Gdy elementy to napisy tej samej długości
- ✓Poprawna odpowiedź: Dla małych kluczy całkowitych z zakresu k: O(n + k)
Wyjaśnienie
Sortowanie przez zliczanie nie porównuje elementów: liczy, ile razy występuje każdy klucz, i wypisuje je po kolei. Świetne dla wieku czy ocen, ale ogromny zakres kluczy sprawia, że tablica liczników jest za duża.