Complejidad de Radix Sort

Question

Estoy un poco confundido por la prueba de complejidad de Radix Sort.

Para contar la ordenación , la complejidad informada es$O(n+R)$, dónde $n$ es el número de elementos y $R$ es el rango.

Pero esto no es del todo correcto, ¿verdad? Para hacer aritmética binaria con números tan grandes como$R$, Necesito $\log_2 R$operaciones para cualquier función hash determinista. Entonces, la complejidad de contar disparos debería ser$O(\log_2 R \cdot (n+R))$.

Entonces la complejidad de la ordenación de radix con base$b$ debiera ser $O(\log_b R \cdot \log_2b \cdot (n+b))$, que es equivalente a $O(\log_2R \cdot n)$. Para rango$R = \Omega(n)$, esto es $\Omega(n \log n)$ y por lo tanto no $O(n)$.

¿Alguien puede señalar dónde me estoy equivocando en mi prueba? Hasta donde yo sé, el tipo de radix es$O(n)$ por $R = O(n^c)$.

Answer 1

Normalmente analizamos algoritmos en la denominada "máquina RAM" o "modelo transdicotómico". En este modelo, las operaciones con palabras de máquina toman$O(1)$y una palabra de máquina tiene longitud $O(\log n)$ bits, donde $n$ es el tamaño de la entrada (en bits) o cualquier otra cantidad relacionada polinomialmente.

Si $R$ es polinomio en $n$ (en este caso, la longitud de la matriz), luego un número entero en el rango $\{1,\ldots,R\}$ puede almacenarse en una sola palabra de máquina, por lo que las operaciones con tales números enteros toman un tiempo constante en este modelo.