Complexité du tri Radix

Question

Je suis un peu confus par la preuve de complexité de Radix Sort.

Pour le tri de comptage , la complexité rapportée est$O(n+R)$, où $n$ est le nombre d'articles et $R$ est la gamme.

Mais ce n'est pas tout à fait correct, non? Pour faire de l'arithmétique binaire sur des nombres aussi grands que$R$, J'ai besoin de $\log_2 R$opérations pour toute fonction de hachage déterministe. Donc, la complexité du comptage des coups devrait être$O(\log_2 R \cdot (n+R))$.

Puis la complexité du tri radix avec base$b$ devrait être $O(\log_b R \cdot \log_2b \cdot (n+b))$, ce qui équivaut à $O(\log_2R \cdot n)$. Pour la gamme$R = \Omega(n)$, c'est $\Omega(n \log n)$ et donc pas $O(n)$.

Quelqu'un peut-il indiquer où je me trompe dans ma preuve? Autant que je sache, le tri radix est$O(n)$ pour $R = O(n^c)$.

Answer 1

Nous analysons généralement les algorithmes dans ce que l'on appelle la «machine RAM» ou le «modèle transdichotomique». Dans ce modèle, les opérations sur les mots machine prennent$O(1)$, et un mot machine a une longueur $O(\log n)$ bits, où $n$ est la taille de l'entrée (en bits), ou toute autre quantité polynomialement liée.

Si $R$ est polynomial dans $n$ (dans ce cas, la longueur du tableau), puis un entier dans la plage $\{1,\ldots,R\}$ peuvent être stockées dans un seul mot machine, et donc les opérations sur ces entiers prennent un temps constant dans ce modèle.