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