Radix Sort & O (N log N) Эффективность

Я недавно узнал о сортировке Radix, и одним из источников, которые я использовал, является страница Википедии. На данный момент там есть параграф об эффективности алгоритма:

Тема эффективности поразрядной сортировки по сравнению с другими алгоритмами сортировки несколько сложна и вызывает множество недоразумений. Будет ли поразрядная сортировка столь же эффективной, менее или более эффективной, чем у лучших алгоритмов, основанных на сравнении, зависит от деталей сделанных предположений. Сложность сортировки по основанию равна O (wn) для n ключей, которые являются целыми числами размером w. Иногда w представляется как константа, что сделало бы сортировку по основанию лучше (для достаточно больших n), чем лучшие алгоритмы сортировки на основе сравнения, которые все выполняют O (n log n) сравнений для сортировки n ключей. Однако в целом w нельзя считать константой: если все n ключей различны, тогда w должно быть не меньше log n, чтобы машина с произвольным доступом могла хранить их в памяти, что дает в лучшем случае временная сложность O (n log n). Это, казалось бы, делает сортировку radix не менее эффективной, чем лучшие сортировки на основе сравнения (и хуже, если ключи намного длиннее, чем log n) .

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

Моя ближайшая попытка такова:

Учитывая основание «B» и число в этой базе «N», максимальное количество цифр, которое может иметь «N», составляет:

(logB из N) + 1.

Если каждое число в данном списке L уникально, то у нас есть до:

L * ((logB of N) + 1) возможностей

В этот момент я не уверен, как развиваться.

Может ли кто-нибудь развернуть приведенный выше раздел жирным шрифтом и пояснить, почему для n различных ключей требуется минимум log n для хранилища с произвольным доступом?


sorting big-o radix-sort
person Levenal    schedule 25.01.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Предполагая сортировку по основанию MSB с постоянными m ячейками:

  • Для произвольно большого типа данных, который должен содержать не менее n различных значений, необходимое количество бит составляет N = ceiling(log2(n)).
  • Таким образом, объем памяти, необходимый для хранения каждого значения, также равен O(log n); предполагая последовательный доступ к памяти, временная сложность чтения / записи значения составляет O(N) = O(log n), хотя вместо этого можно использовать указатели
  • Количество цифр O(N / m) = O(log n)
  • Важно отметить, что каждая следующая цифра должна отличаться степенью двойки, т.е. m также должна быть степенью двойки; предположим, что это достаточно мало для HW-платформы, например 4-битные цифры = 16 ячеек

Во время сортировки:

  • Для каждого прохода системы счисления, из которых O(log n):

    1. Count each bucket: get the value of the current digit using bit operations - O(1) for all n values. Should note that each counter must also be N bits, although increments by 1 will be (amortized) O(1). If we had used non-power-of-2 digits, this would in general be O(log n log log n) ( source )

    2. Сделайте массив счетчика ведра кумулятивным: необходимо выполнить m - 1 добавлений, каждое из которых равно O(N) = O(log n) (в отличие от особого случая приращения)

    3. Запишите выходной массив: переберите n значений, снова определите ячейку и запишите указатель с правильным смещением

Таким образом, общая сложность равна O(log n) * [ n * O(1) + m * O(log n) + n * O(1) ] = O(n log n).

person meowgoesthedog    schedule 25.01.2018
comment
Спасибо за ответ. Что касается 4-го пункта, это просто общий комментарий? Поскольку сортировка Radix не делает никаких сравнений, насколько я знаю - person Levenal; 26.01.2018
comment
@Levenal извиняюсь, ясно My_Brain.exe has encountered a problem and has to close. - person meowgoesthedog; 26.01.2018
comment
Могу я предложить перезагрузку =) Редактирование было очень полезным, спасибо. Разбивая его на части, вы облегчите работу. Я еще не понял всего этого, но теперь уверен, что доберусь туда. - person Levenal; 26.01.2018