304
правки
Изменения
м
→Сложность
==Сложность==
Пусть <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> O(m \cdot (n + k)) </tex>, если устойчивая сортировка имеет время работы <tex> O(n + k) </tex>. Если <tex> k </tex> небольшое, то оптимально выбирать в качестве устойчивой сортировки сортировку подсчетом.
