¿Por qué es Radix Sort

23

En la clasificación por radix primero ordenamos por el dígito menos significativo, luego ordenamos por el segundo dígito menos significativo y así sucesivamente, y terminamos con una lista ordenada.

Ahora, si tenemos una lista de n números, necesitamos logn bits para distinguir entre esos números. Así número de radix pasa especie hacemos será logn . Cada pase lleva tiempo O(n) y, por lo tanto, el tiempo de ejecución de la clasificación de radix es O(nlogn)

Pero es bien sabido que es un algoritmo de tiempo lineal. ¿Por qué?

Pratik Deoghare
fuente
Esta es la razón por la cual los tipos de tiempo lineal generalmente requieren que la entrada sea entera en un rango fijo. La clasificación de radix requiere un rango fijo en los dígitos. En su ejemplo, supuso que el rango era [0,1] , pero cualquier rango entero es posible para los dígitos; por ejemplo, podrías haber elegido [0,n]
Joe

Respuestas:

19

si tenemos una lista de números necesitamos registrar n bitsnlogn

No: si tenemos una lista de números entre y 2 k - 1 , necesitamos k bits. No hay relación entre k y log n en general.02k1kklogn

Si todos los números son distintos, entonces , y la clasificación por radix en números distintos tiene una complejidad temporal de Ω ( n log n ) . En general, la complejidad de la clasificación de radix es Θ ( nlognkΩ(nlogn) donde n es el número de elementos para ordenar yk es el número de bits en cada elemento.Θ(nk)nk

Decir que la complejidad de la clasificación de radix es significa tomar un tamaño de bit fijo para los números. Esto implica que para n suficientemente grande , habrá muchos valores duplicados.O(n)n


Existe un teorema general de que un método de ordenación de matriz o lista que funciona comparando dos elementos a la vez no puede ejecutarse más rápido que en el peor de los casos. La clasificación por radix no funciona comparando elementos, pero funciona el mismo método de prueba. La clasificación por radix es un proceso de decisión para determinar qué permutación se aplicará a la matriz; hay n ! permutaciones de la matriz, y la ordenación por radix toma decisiones binarias, es decir, decide si intercambia dos elementos o no en cada etapa. Después de m decisiones binarias, la clasificación de radix puede decidir entre 2 m de permutaciones. Para llegar a la n ! posibles permutaciones, es necesario queΘ(nlogn)n!m2mn! .mlog(n!)=Θ(nlogn)

Una suposición en la prueba de que no escribí anteriormente es que el algoritmo debe funcionar en el caso cuando los elementos son distintos. Si se sabe a priori que los elementos no son todos distintos, entonces el número de permutaciones potenciales es menor que la completa . . Al ordenar números de k bits, solo es posible tener n elementos distintos cuando n 2 k ; en ese caso, la complejidad de la clasificación de radix es de hecho Ω ( n log n ) . Para valores mayores de n , debe haber colisiones, lo que explica cómo la ordenación de radix puede tener una complejidad menor que Θ (n!knn2kΩ(nlogn)n cuando n > 2 k .Θ(nlogn)n>2k

Gilles 'SO- deja de ser malvado'
fuente
1
Un punto de vista alternativo es el del modelo de costo de la palabra RAM: nuestra máquina puede trabajar con enteros de bits en tiempo constante. (Máquinas actuales que tienen w = 64. ) De esa manera, un paso de clasificación de distribución con 2 cubetas w se puede hacer en O ( 1 ) tiempo accediendo directamente a un elemento de matriz correspondiente. De esta forma, la clasificación de radix es lineal para n enteros de w = O ( log n ) bits cada uno. ww=642wO(1)nw=O(logn)
Sebastian
9

Tenga cuidado con su análisis: ¿qué supone que realiza la clasificación en tiempo ? Esto se debe a que cada uno de sus dígitos está en un rango de 0 a k - 1 , lo que significa que sus dígitos pueden tomar k posibles valores. Necesita un algoritmo de ordenación estable, por lo que puede, por ejemplo, elegir la ordenación de conteo. El recuento se ejecuta enO(n)0k1k . Si k = O ( n ) , la ordenación de conteo se ejecuta en tiempo lineal.Θ(n+k)k=O(n)

Cada una de sus cadenas o números tiene dígitos. Como dices, haces d pases sobre ellos. Por lo tanto, la ordenación de la raíz se ejecuta claramente en el tiempo Θ ( d ( n + k ) ) . Pero si consideramos que d es constante yk = O ( n ) , vemos que la ordenación por radix se ejecuta en tiempo lineal.ddΘ(d(n+k))dk=O(n)

Juho
fuente
1
Por ejemplo, suponga que está ordenando enteros en el rango para algunos N = O ( n d ) para la constante d . Entonces puede tener O ( d ) dígitos cada uno con rango O ( n ) . [0,N1]N=O(nd)dO(d)O(n)
Joe
-2

Creo que la suposición está mal. Puede realizar la clasificación de radix con números en, por ejemplo, hexadecimal. Por lo tanto, en cada paso divide su conjunto de números en 16 cubos.k=log2(n)16

Alexandre Kandalintsev
fuente
66
En lo que respecta a big-O, no hay diferencia entre y log 16 n . log2nlog16n
Rick Decker