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