Изменения
Нет описания правки
Важно, что эта теорема дает оценку времени выполнения алгоритма в худшем случае.
Дальнейшее улучшение было получено Волганом Праттом. Если все смещения при сортировке выбираются из множества чисел вида <tex>2^p3^q</tex>, меньших <tex>N</tex>, то время выполнения алгоритма будет порядка <tex>O(NlogN\log^2{N})</tex>.
== Смотри также ==
