Почему Radix Sort ?

23

В радикальной сортировке мы сначала сортируем по наименьшей значащей цифре, затем сортируем по второй наименьшей значащей цифре и так далее и получаем отсортированный список.

Теперь, если у нас есть список из чисел, нам нужно бит, чтобы различать эти числа. Таким образом, количество проходов сортировки по основанию будет . Каждый проход занимает времени и, следовательно, время выполнения радикальной сортировки равноnlognlognO(n)O(nlogn)

Но хорошо известно, что это линейный алгоритм времени. Почему?

Пратик Деогхаре
источник
Вот почему линейные временные сортировки обычно требуют, чтобы входные данные были целыми числами в некотором фиксированном диапазоне. Radix sort требует фиксированного диапазона цифр. В вашем примере вы предполагали, что диапазон был , но для цифр возможен любой целочисленный диапазон; Например, вы могли бы выбрать[0,1][0,n]
Джо

Ответы:

19

если у нас есть список из чисел, нам нужно записать n битnlogn

Нет: если у нас есть список чисел от до 2 k - 1 , нам нужно k бит. Между k и log n вообще нет никакой связи .02k1kklogn

Если все числа различны, то , и радикальная сортировка по разным числам, следовательно, имеет временную сложность Ω ( n log n ) . В общем, сложность радикальной сортировки равна Θ ( nlognkΩ(nlogn) где n - количество элементов для сортировки, а k - количество битов в каждом элементе.Θ(nk)nk

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


Существует общая теорема о том, что метод сортировки массива или списка, который работает путем сравнения двух элементов за один раз, не может работать быстрее, чем в худшем случае. Radix sort не работает при сравнении элементов, но работает тот же метод доказательства. Radix sort - это процесс принятия решения, чтобы определить, какую перестановку применить к массиву; есть n ! перестановки массива и радикальная сортировка принимает двоичные решения, т. е. решает, нужно ли поменять местами два элемента или нет на каждом этапе. После m двоичных решений радикальная сортировка может выбирать между 2 m перестановками. Чтобы достичь п ! возможные перестановки, необходимо, чтобыΘ(NжурналN)N!м2мN! .mlog(n!)=Θ(nlogn)

В доказательстве, которое я не выписал выше, предполагается, что алгоритм должен работать в случае, когда элементы различны. Если априори известно, что элементы не все различны, то число потенциальных перестановок меньше полного , При сортировке k- битных чисел возможно иметь n различных элементов только при n 2 k ; в этом случае сложность радикальной сортировки действительно равна Ω ( n log n ) . Для больших значений n должны быть коллизии, что объясняет, как радикальная сортировка может иметь сложность, меньшую чем Θ (n!knn2kΩ(nlogn)n когда n > 2 k .Θ(nlogn)n>2k

Жиль "ТАК - перестань быть злым"
источник
1
Альтернативная точка зрения - это модель стоимости слово-RAM: наша машина может работать с целыми числами бит в постоянном времени. (Текущие машины имеют w = 64. ) Таким образом, один шаг сортировки распределения с 2 сегментами w может быть выполнен за O ( 1 ) времени путем прямого доступа к соответствующему элементу массива. Таким образом, радикальная сортировка является линейной для n целых чисел по w = O ( log n ) битов каждый. ww=642wO(1)nw=O(logn)
Себастьян
9

Будьте осторожны с анализом: что вы предполагаете, чтобы сортировка выполнялась за раз? Это потому, что каждая из ваших цифр находится в диапазоне от 0 до k - 1 , что означает, что ваши цифры могут принимать k возможных значений. Вам нужен стабильный алгоритм сортировки, так что вы можете, например, выбрать сортировку отсчета. Подсчет сортировки выполняется за Θ ( n + k ) времени. Если k = O ( n ) , подсчет сортировки выполняется за линейное время.O(n)0k1kΘ(n+k)k=O(n)

Каждая из ваших строк или чисел имеет цифры. Как вы говорите, вы делаете D проходов над ними. Следовательно, радикальная сортировка явно выполняется за время Θ ( d ( n + k ) ) . Но если мы считаем d постоянным и k = O ( n ) , мы видим, что радикальная сортировка выполняется за линейное время.ddΘ(d(n+k))dk=O(n)

Юхо
источник
1
Например, предположим, что вы сортируете целые числа в диапазоне для некоторого N = O ( n d ) для константы d . Тогда вы можете иметь O ( d ) цифр каждая с диапазоном O ( n ) . [0,N1]N=O(nd)dO(d)O(n)
Джо
-2

Я думаю, что предположение неверно. Вы можете выполнить основную сортировку с числами, например, в шестнадцатеричном. Таким образом, на каждом шаге вы разбиваете массив чисел на 16 сегментов.k=log2(n)16

Александр кандалинцев
источник
6
Что касается big-O, то нет разницы между и log 16 n . log2nlog16n
Рик Декер