101
правка
Изменения
→Анализ
=== Анализ ===
Весь алгоритм состоит из двух проходов по массиву <tex>A</tex> размера <tex>n</tex> и одного прохода по массиву <tex>P</tex>, размера <tex>k</tex>.Его трудоемкость, таким образом, равна <tex> O(n + k)</tex>. На практике сортировку подсчетом имеет смысл применять, если <tex>k</tex> значительно меньше <tex>= O(n)</tex>, поэтому можно считать время работы алгоритма равным <tex> O(n)</tex>. <br>
Как и в обычной сортировке подсчетом, требуется <tex> O(n + k)</tex> дополнительной памяти {{---}} на хранение массива <tex>B</tex> размера <tex>n</tex> и массива <tex>P</tex> размера <tex>k</tex>.
