Numero totale di bit necessari per rappresentare un elenco di N elementi

Question

Questo è un estratto dal libro di testo degli algoritmi Come pensare agli algoritmi Di Jeff Edmonds (questo libro è una gemma a proposito).

Ottengo le sue conclusioni sugli ordini di unione/rapido/heap con operazioni $ o (nlogn) $ rispetto a $ n $, il numero di elementi nell'elenco di input e allo stesso tempo sono lineari nel contesto di cui hanno bisogno $ O (N) $ OPERTAIONS rispetto al numero di bit necessari per rappresentare l'elenco di input. Diversi modelli di calcolo e un buon modo per descrivere un algoritmo sotto diversi modelli.

Ma la mia domanda è in linea

Supponendo che i numeri $ n $ da ordinare siano distinti, ognuno ha bisogno di $ logni $ bit da rappresentare, per un totale di $ n = theta (nlogn) $ bit.

La mia comprensione di questo era che con $ n $ distinti, abbiamo bisogno di dimensioni delle parole $ w = theta (log) $, come definito in CLRS. Vogliamo che la dimensione della parola sia in grado di indicizzare almeno $ n $ diversi elementi ma non così grandi che possiamo mettere Tutto quanto in una parola. Inoltre, con $ n $ distinti elementi, abbiamo bisogno di $ omega (log) $ bit per rappresentare il numero maggiore. Supponendo che ogni parola si adatti a $ w $, l'affermazione di Edmonds secondo cui $ n = theta (nlogn) $ bit aveva senso. Per favore correggimi se la mia analisi è sbagliata qui.

Ma quando provo ad applicare questo per contare, qualcosa non sembra giusto. Con $ n $ di nuovo il numero di elementi nell'input e $ k $ il valore dell'elemento massimo nell'elenco, il tempo di esecuzione è $ o (n + k) $. Il conteggio dell'ordinanza è lineare rispetto a $ n $, il numero di elementi nell'input, quando $ k = o (n) $. Usando questo vincolo per rappresentare l'input come numero totale di bit $ n $, penso che $ n = O (nlogk) = O (nlogn) $.

Quindi, con nel modello di calcolo RAM, come posso esprimere il tempo di esecuzione del conteggio dell'ordinamento rispetto a $ n $ bit? Gli ordini unione/rapido/heap avevano la complessità del tempo $ o (n) $ rispetto a $ n $ bit, come espresso in modo pulito da Edmonds. Non sono sicuro di come fare qualcosa di simile per il conteggio dell'ordinanza, e forse forse per l'ordinamento di Radix usando il conteggio dell'ordinanza come una subroutine. Qualche idea su come farlo nei due casi in cui $ k = theta (n) $ e quando questa condizione non è presente? Sospetto che il primo darà una sorta di tempo polinomiale rispetto a $ n $ e il secondo tempo esponenziale (quindi pseudo-polinomiale) rispetto a $ n $ bit, ma avranno problemi a esprimere la matematica ...