Можем ли мы сделать алгоритм сортировки подсчета для n элементов с O (n) пространственной сложностью?

Question

Сегодня у меня был промежуточный экзамен, и одной из проблем алгоритма было «Можем ли мы сделать сложность пространства для подсчета сортировки O (n) для n элементов». На самом деле я не мог найти никакого решения для этого. Кто-нибудь знает какой-либо алгоритм или структуру данных. Я хочу узнать ответ и подумать об этом. Большое спасибо.

Answer 1

Если мы используем массив для подсчета в сортировке подсчета, то для этого требуется пространство, равное разнице между максимальным и минимальным значениями ключа.Мы можем использовать хеш-таблицу, тогда мы можем уменьшить сложность пространства до линейной относительно количества элементов на входе.Но в этом случае скрытая константа может быть слишком большой, а производительность может ухудшиться.