Ordinamento di ordinamento basato sul confronto rispetto al numero totale di bit di input

Question

Gli algoritmi di ordinamento basati sul confronto sono più bassi di $ omega (NLOGN) $, dove $ n $ è il numero di elementi nell'elenco di input.

Tuttavia, quando si tratta di diversi modelli di calcolo, come gli algoritmi che si occupano di operazioni aritmetiche (Euclid-GCD) o, $ n $, la dimensione dell'input, non è più il numero di elementi ma il numero totale di bit richiesti rappresentare l'input. In questi casi, la complessità del tempo viene misurata come il numero di operazioni di bit necessarie rispetto al numero totale di bit nell'input.

Guardando il post Qual è il tempo pseudo-polinomiale in che modo differisce dal tempo polinomiale?

Il tempo polinomiale è definito come:

Un algoritmo funziona in tempo polinomiale se il suo runtime è O (xk) per un k costante K, dove x indica il numero di bit di input dati all'algoritmo.

Il tempo pseudo-polinomail è definito come:

Un algoritmo funziona in tempo pseudo-polinomiale se il runtime è un polinomio nel valore numerico dell'input, piuttosto che nel numero di bit richiesti per rappresentarlo.

Guardando Come possiamo presumere che le operazioni di base sui numeri richiedano tempo costante?

Per le dimensioni delle parole $ w = theta (logn) $, le operazioni aritmetiche standard su queste parole prendono $ o (1) $ tempo, per definizione.

Con queste definizioni in mente, ho difficoltà a vedere come alcuni algoritmi di smistamento basati sul confronto siano tempo polinomiale rispetto a $ n $, il numero di elementi nell'input e $ x $, il numero totale di bit nell'input; Il primo post a cui ho fatto riferimento fa questa affermazione.

Perché sono polinomiali rispetto a $ n $ è abbastanza ovvio, quindi esaminerò solo la rappresentazione bit di input $ x $ per gli algoritmi di smistamento basati su confronto con 2 diverse complessità temporali.

Unisci o ordina rapida in un elenco di $ n $ elementi

Abbiamo bisogno di $ w = theta (logn) $, come definito in CLRS, poiché almeno dobbiamo essere in grado di indicizzare in una matrice di dimensioni $ n $. Supponendo che tutti gli elementi si adattino a una parola, che penso sia un presupposto ragionevole qui, $ x = wn = theta (nlogn) $. Per favore fatemi sapere se il mio $ x $ è sbagliato !!!

Poiché il tempo di esecuzione era $ O (NLOGN) $, la complessità del tempo rispetto a $ x $ è $ o (x) $. Interpreterò questo come significato abbiamo bisogno di un numero lineare di operazioni sul numero totale di bit necessari per rappresentare questo elenco di input.

Ordina di selezione in un elenco di $ n $ elementi:

Assumerò lo stesso $ x = wn = theta (nlogn) $ per la dimensione dell'input. Il tempo di esecuzione è $ o (n^2) $. Qui ho bisogno di aiuto: come posso scrivere il tempo di esecuzione in modo pulito in termini di $ x $, come ho fatto per unione/ordinamento rapido sopra? Il primo post a cui ho fatto riferimento ha appena usato $ w = 32 $ bit e ha ottenuto facilmente $ o (x^2) $ polinomiale ma questo non mi sembra giusto, dal momento che il [secondo post] a cui ho fatto riferimento (Come possiamo presumere che le operazioni di base sui numeri richiedano tempo costante?) e CLRS ha sottolineato $ w $ non è una costante ma $ theta (logn) $.

Ho una domanda simile per Contare la specie, a cui non è stato ancora risposto ... il primo post Ho fatto riferimento ai reclami che è esponenziale rispetto a $ x $ senza la condizione $ k = theta (n) $ quando $ x = theta (nlogk) $ bit, ma ho difficoltà a cambiare da $ o (n + k) $ In termini di $ x $. Per favore aiuto!!