42
правки
Изменения
Нет описания правки
<tex>p</tex> - количество разрядов в объекте.
Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем <Tex>O (p \cdot (n + k))</Tex> итераций.
Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно, в средним алгоритм "карманной сортировки" совершает <Tex>O (n \cdot \log_k n)</Tex> действий. При этом на некотором множестве наборов, где <tex> k = O(n)</tex>, алгоритм отработает за линейное время.
В худшем случае сортировка работает за <tex>O (n^2)</tex>.
==Примечания==
