Алгоритми та структури даних · Middle · Запитання 8 з 75
Коли сортування підрахунком може бути швидшим за O(n log n)?
- 1Коли масив уже майже повністю відсортований
- 2Коли елементи - рядки однакової довжини
- ✓Правильна відповідь: Для малих цілих ключів у діапазоні k: O(n + k)
Пояснення
Сортування підрахунком не порівнює елементи: воно рахує, скільки разів трапляється кожен ключ, і записує їх назад по порядку. Чудово для віку чи оцінок, але величезний діапазон ключів робить масив лічильників завеликим.