Complexidade do Radix Sort

Question

Estou um pouco confuso com a prova de complexidade do Radix Sort.

Para classificação de contagem , a complexidade relatada é$O(n+R)$, Onde $n$ é o número de itens e $R$ é o intervalo.

Mas isso não é totalmente correto, certo? Para fazer aritmética binária em números tão grandes quanto$R$, Eu preciso de $\log_2 R$operações para qualquer função de hash determinística. Portanto, a complexidade da contagem de disparos deve ser$O(\log_2 R \cdot (n+R))$.

Em seguida, a complexidade da classificação radical com base$b$ deveria estar $O(\log_b R \cdot \log_2b \cdot (n+b))$, que é equivalente a $O(\log_2R \cdot n)$. Para alcance$R = \Omega(n)$, isso é $\Omega(n \log n)$ e assim não $O(n)$.

Alguém pode apontar onde estou errando em minha prova? Até onde eu sei, radix sort é$O(n)$ para $R = O(n^c)$.

Answer 1

Normalmente analisamos algoritmos na chamada "máquina RAM" ou "modelo transdicotômico". Neste modelo, as operações em palavras de máquina levam$O(1)$, e uma palavra de máquina tem comprimento $O(\log n)$ bits, onde $n$ é o tamanho da entrada (em bits) ou qualquer outra quantidade relacionada polinomialmente.

Se $R$ é polinomial em $n$ (neste caso, o comprimento da matriz), então um inteiro no intervalo $\{1,\ldots,R\}$ pode ser armazenado em uma única palavra de máquina e, portanto, as operações em tais inteiros levam um tempo constante neste modelo.