403
правки
Изменения
→Сложность
Пусть <tex> m </tex> {{---}} количество разрядов, <tex> n </tex> {{---}} количество объектов, которые нужно отсортировать, <tex> T(n) </tex> {{---}} время работы устойчивой сортировки. Цифровая сортировка выполняет <tex> k </tex> итераций, на каждой из которой выполняется устойчивая сортировка и не более <tex> O(1) </tex> других операций. Следовательно время работы цифровой сортировки {{---}} <tex> O(k \cdot T(n)) </tex>.
Рассмотрим отдельно случай сортировки чисел. Пусть в качестве аргумента сортировке передается массив, в котором содержатся <tex> n </tex> <tex> m </tex>-значных чисел, и каждая цифра может принимать значения от <tex> 0 </tex> до <tex> k - 1 </tex>. Тогда цифровая сортировка позволяет отсортировать данный массив за время <tex> \ThetaO(m \cdot (n + k)) </tex>, если устойчивая сортировка имеет время работы <tex> \ThetaO(n + k) </tex>. Если <tex> k </tex> небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.
Если количество разрядов {{---}} константа, а <tex> k = O(n) </tex>, то сложность цифровой сортировки составляет <tex> O(n) </tex>, то есть она линейно зависит от количества сортируемых чисел.
