Por que Radix Sort ?

23

Na classificação radix, classificamos primeiro pelo dígito menos significativo, depois classificamos pelo segundo dígito menos significativo e assim por diante e terminamos com a lista classificada.

Agora, se temos lista de números que precisamos bits para distinguir entre aqueles número. Portanto, o número de passes de classificação de radix que fazemos será . Cada passagem leva tempo e, portanto, o tempo de execução da classificação de raiz énlognlognO(n)O(nlogn)

Mas é sabido que é um algoritmo de tempo linear. Por quê?

Pratik Deoghare
fonte
É por isso que as ordenações lineares do tempo geralmente exigem que a entrada seja um número inteiro em algum intervalo fixo. A classificação Radix requer um intervalo fixo nos dígitos. No seu exemplo, você assumiu que o intervalo era , mas qualquer intervalo inteiro é possível para os dígitos; por exemplo, você poderia ter escolhido[0,1][0,n]
Joe

Respostas:

19

se tivermos uma lista de números, precisamos bitsnlogn

Não: se tivermos uma lista de números entre e , precisaremos de bits. Não há relacionamento entre e em geral.2 k - 1 k k log n02k1kklogn

Se os números forem todos distintos, então , e a classificação do radical em números distintos, portanto, possui uma complexidade de tempo de Ω ( n log n ) . Em geral, a complexidade da classificação do radical é Θ ( nlognkΩ(nlogn) onde n é o número de elementos a serem classificados e k é o número de bits em cada elemento.Θ(nk)nk

Dizer que a complexidade da classificação de raiz é significa assumir um tamanho de bit fixo para os números. Isso implica que, para n grande o suficiente , haverá muitos valores duplicados.O(n)n


Existe um teorema geral de que um método de classificação de matriz ou lista que funciona comparando dois elementos por vez não pode ser executado mais rapidamente que na pior das hipóteses. A classificação Radix não funciona comparando elementos, mas o mesmo método de prova funciona. A classificação Radix é um processo de decisão para determinar qual permutação aplicar à matriz; existem n ! permutações da matriz e a classificação de radix toma decisões binárias, isto é, decide se deve trocar dois elementos ou não em cada estágio. Depois m decisões binárias, radix sort pode decidir entre 2 m permutações. Para alcançar o n ! possíveis permutações, é necessário queΘ(nlogn)n!m2mn! .mlog(n!)=Θ(nlogn)

Uma suposição na prova de que não escrevi acima é que o algoritmo deve funcionar no caso em que os elementos são distintos. Se se sabe a priori que os elementos não são todos distintos, então o número de permutações potenciais é menor que o valor . Ao classificar números de bits de k , só é possível ter n elementos distintos quando n 2 k ; nesse caso, a complexidade da classificação do radical é de fato Ω ( n log n ) . Para valores maiores de n , deve haver colisões, o que explica como a classificação de raiz pode ter uma complexidade menor que Θ (n!knn2kΩ(nlogn)n quando n > 2 k .Θ(nlogn)n>2k

Gilles 'SO- parar de ser mau'
fonte
1
Um ponto de vista alternativo é o do modelo de custo da palavra RAM: Nossa máquina pode trabalhar com números inteiros de bits em tempo constante. (Máquinas atuais com w = 64. ) Dessa forma, uma etapa de classificação da distribuição com baldes de 2 w pode ser realizada no tempo O ( 1 ) acessando diretamente um elemento de matriz correspondente. Dessa forma, a classificação do radical é linear para n números inteiros de w = O ( log n ) bits cada. ww=642wO(1)nw=O(logn)
23314 Sebastian
9

Tenha cuidado com sua análise: o que você supõe para executar a classificação em tempo? Isso ocorre porque cada um dos seus dígitos está no intervalo de 0 a k - 1 , o que significa que seus dígitos podem assumir k valores possíveis. Você precisa de um algoritmo de classificação estável, para poder, por exemplo, escolher a classificação de contagem. A classificação da contagem é executada em Θ ( n + k ) . Se k = O ( n ) , a classificação da contagem é executada em tempo linear.O(n)0k1kΘ(n+k)k=O(n)

Cada uma de suas seqüências ou números tem dígitos. Como você diz, você faz d passar por cima deles. Portanto, a classificação de raiz é executada claramente em Θ ( d ( n + k ) ) . Mas se considerarmos que d é constante e k = O ( n ) , vemos que a classificação do radical é executada em tempo linear.ddΘ(d(n+k))dk=O(n)

Juho
fonte
1
Por exemplo, suponha que você esteja classificando números inteiros no intervalo para alguns N = O ( n d ) para a constante d . Então você pode ter O ( d ) dígitos, cada um com o intervalo O ( n ) . [0,N1]N=O(nd)dO(d)O(n)
11113 Joe
-2

Eu acho que a suposição está errada. Você pode executar a classificação radix com números, por exemplo, hexadecimal. Assim, em cada etapa, você divide seu conjunto de números em 16 blocos.k=log2(n)16

Alexandre Kandalintsev
fonte
6
No que diz respeito ao big-O, não há diferença entre o e o log 16 n . log2nlog16n
Rick Decker