Как количество цифр d среди n ключей имеет порядок log n?

Я читал статью в Википедии о сортировке Radix и, описывая ее эффективность, говорит:

Эффективность сортировки по основанию равна O(d·n) для n ключей, содержащих d или меньше цифр. Иногда d представляется как константа, что сделает сортировку по основанию лучше (для достаточно больших n), чем лучшие алгоритмы сортировки на основе сравнения, которые требуют всего O(n·log(n)) количества сравнений. Однако вообще d нельзя считать константой. В частности, при общепринятом (но иногда неявном) предположении, что все ключи различны, тогда d должно быть как минимум порядка log(n), что дает в лучшем случае (с плотно упакованными ключами) временную сложность O(n·log(n)).

Теперь то, что я не понимаю, это строка - предположение, что все ключи различны, тогда d должно быть как минимум порядка log(n) Что именно он пытается сказать?


sorting algorithm radix-sort
person Anoop Dixith    schedule 16.10.2014    source источник
comment
Для нумерации n ключей требуется Log(n) цифры, поэтому ключи имеют как минимум такую ​​длину.   -  person Yves Daoust    schedule 16.10.2014

Ответы (2)


arrow_upward
2
arrow_downward

Если мы считаем, что ключи различны, то у нас есть n различных ключей, теперь предположим, что самый большой ключ - k , мы знаем это, поскольку все числа различны, поэтому k больше или равно n. так что k имеет log(k) цифр, и это по крайней мере log(n), поэтому d равно O(log(n))

EDIT: Чтобы лучше понять log в базе 10 и 2 и Big-O, прочитайте этот опубликовать.

person Lrrr    schedule 16.10.2014
comment
@Srivatskrishnan нет разницы между журналом в базе 10, 2 или 16 и ... там все в одном порядке. постоянный порядок не влияет. - person Lrrr; 16.10.2014

arrow_upward
0
arrow_downward

Если все ключи различны, вы можете заказать их, и самый большой из них будет не менее n (учитывая только положительные целые числа)

Тогда количество цифр n равно log10 (n), поэтому d не меньше log (n)

person yunandtidus    schedule 16.10.2014