Nombre total de bits nécessaires pour représenter une liste de n éléments

Question

Ceci est un extrait du manuel des algorithmes Comment penser aux algorithmes par Jeff Edmonds (ce livre est un joyau d'ailleurs).

J'obtiens sa conclusion sur les types de fusion / rapide / tas ayant des opérations $ o (nlogn) $ en ce qui concerne $ n $, le nombre d'éléments dans la liste des entrées, et en même temps qu'ils sont linéaires dans le contexte dont ils ont besoin O (n) $ opertaions par rapport au nombre de bits nécessaires pour représenter la liste des entrées. Différents modèles de calcul et une bonne façon de décrire un algorithme sous différents modèles.

Mais ma question est dans la ligne

En supposant que les chiffres $ n $ à tri sont distincts, chacun a besoin de bits $ logn $ à représenter, pour un total de $ n = theta (nlogn) $ bits.

Ma compréhension était qu'avec des nombres distincts $ n $, nous avons besoin de la taille des mots $ w = theta (verb) CLR. Nous voulons que la taille du mot puisse au moins indexer en $ n $ d'éléments différents mais pas si gros que nous pouvons mettre tout en un mot. De plus, avec des éléments $ n $ distincts, nous avons besoin de bits $ oméga (logn) pour représenter le plus grand nombre. En supposant que chaque mot s'intégrera dans $ W $, la réclamation d'Edmonds selon laquelle $ n = theta (nlogn) $ bits avait du sens. Veuillez me corriger si mon analyse est erronée ici.

Mais quand j'essaie d'appliquer cela au rythme de comptage, quelque chose ne semble pas bien. Avec $ n $ encore le nombre d'éléments dans l'entrée et $ k $ la valeur de l'élément maximum dans la liste, le temps d'exécution est $ o (n + k) $. Le rythme de comptage est linéaire par rapport à $ n $, le nombre d'éléments dans l'entrée, lorsque $ k = o (n) $. En utilisant cette contrainte pour représenter l'entrée comme le nombre total de bits $ n $, je pense que $ n = o (nlogk) = o (nlogn) $.

Donc, avec le modèle de calcul RAM, comment puis-je exprimer le ruissellement du tri de comptage par rapport aux bits $ n $? Fust / Quick / Heap Tys avait le temps de complexité $ o (n) $ en ce qui concerne les bits $ n $, comme l'exprimait proprement par Edmonds. Je ne sais pas comment faire quelque chose de similaire pour compter le tri, et peut-être peut-être pour le tri Radix en utilisant le tri de comptage comme sous-programme. Une idée comment faire cela dans les deux cas lorsque $ k = theta (n) $ et quand cette condition n'est pas présente? Je soupçonne que le premier donnera une sorte de temps polynomial en ce qui concerne $ n $ et le dernier temps exponentiel (d'où pseudo-polynôme) en ce qui concerne les bits $ n $, mais j'ai du mal à exprimer les mathématiques ...