Complessità di Radix Sort

Question

Sono un po 'confuso dalla prova di complessità di Radix Sort.

Per il conteggio dell'ordinamento , la complessità riportata è$O(n+R)$, dove $n$ è il numero di elementi e $R$ è la gamma.

Ma questo non è del tutto corretto, giusto? Per eseguire operazioni aritmetiche binarie su numeri grandi come$R$, Ho bisogno $\log_2 R$operazioni per qualsiasi funzione di hashing deterministica. Quindi la complessità del conteggio dei colpi dovrebbe essere$O(\log_2 R \cdot (n+R))$.

Poi la complessità dell'ordinamento digitale con base$b$ dovrebbe essere $O(\log_b R \cdot \log_2b \cdot (n+b))$, che è equivalente a $O(\log_2R \cdot n)$. Per gamma$R = \Omega(n)$, questo è $\Omega(n \log n)$ e quindi no $O(n)$.

Qualcuno può farmi notare dove sto sbagliando nella mia prova? Per quanto ne so, l'ordinamento digitale è$O(n)$ per $R = O(n^c)$.

Answer 1

Tipicamente analizziamo gli algoritmi nella cosiddetta "macchina RAM" o "modello transdicotomico". In questo modello, le operazioni sulle parole macchina richiedono$O(1)$e una parola macchina ha lunghezza $O(\log n)$ bit, dove $n$ è la dimensione dell'input (in bit) o ​​qualsiasi altra quantità correlata in modo polinomiale.

Se $R$ è polinomiale in $n$ (in questo caso, la lunghezza dell'array), quindi un numero intero nell'intervallo $\{1,\ldots,R\}$ può essere memorizzato in una singola parola macchina, quindi le operazioni su tali numeri interi richiedono un tempo costante in questo modello.