Sto leggendo (Cormen) sul conteggio sort.
Capisco la struttura dell'algoritmo ma l'affermazione:
In practice, we usually use counting sort when we have k = O(n), in which case the running time is Theta(n).
Non è chiaro nella mia mente.
k è solo l'intervallo di interi previsti nell'input.
Perché la notazione asintotica usata in questa affermazione per k? Non capisco
La tua citazione sta dicendo che se l'intervallo di interi k è linearmente proporzionale al numero totale di elementi nella raccolta n, allora un ordinamento di conteggio avrà una complessità temporale di caso migliore e di caso peggiore di O (n) , rendendolo un tipo molto efficiente in tal caso.
Big Oh (e altri nella famiglia di notazioni di Bachman-Landau) sono solo delle semplificazioni della precisa complessità della funzione in ogni caso, utilizzate per illustrare il valore crescente della funzione man mano che N cresce. Nella programmazione, Big Oh viene solitamente utilizzato nel contesto della complessità temporale; per n valori, una funzione f (n) verrà eseguita in un tempo nell'ordine di g (n), e quindi diciamo che ha una complessità Big Oh di O (g (n)). Tuttavia, il costrutto matematico di Big Oh non è così limitato. In questo caso particolare, viene usato per riferirsi alla relazione generale tra k e N come numeri.
In parole semplici, quando k (l'intervallo dei valori di una raccolta di elementi n) aumenta come n fa nell'ordine di O (n), allora l'ordinamento del conteggio sarà efficiente. Questo sarà vero se, per esempio, la lista contenesse tutti i multipli di 4 tra 1 e x (nel qual caso k ~ = x e n = x / 4, che significa k ~ = 4n = O (n)). La condizione k = O (n) sarebbe falsa per, diciamo, l'insieme di tutti i quadrati perfetti da 1 a x 2 (nel qual caso k = x 2 ma n = x, quindi k = n 2 = O (n 2 )). In tal caso, k aumenta sul quadrato (O (n 2 )) quando N aumenta linearmente (O (n)), quindi l'ordinamento del conteggio verrebbe eseguito nel tempo più complesso (che sarebbe O (n 2 )), che si comporta in modo peggiore rispetto ad altre implementazioni di ordinamento eseguite in Theta (nlogn).
La complessità di un ordinamento di conteggio è O (max (k, n)), quindi se k = O (n) l'ordinamento viene eseguito nel tempo O (n).
Almeno mentre lo interpreto, dico semplicemente che la gamma degli input e il numero di input sono un po 'simili [Edit: almeno che sia frainteso, lo sta dando come condizione in cui la complessità è Theta (n) , non dicendo che è necessariamente sempre vero.]
Per esempio, il solito tempo è ragionevole per mille o un milione o un miliardo di ingressi di qualcosa come 32 o 64 bit ciascuno.
Ignorando, per il momento, il fatto che non avresti mai effettivamente finito, considera cosa succederebbe se avessi un numero di cifre a 500 cifre (o 10.000 cifre) di ingressi a 3 bit. In tal caso, il tempo impiegato per eseguire ogni singola aggiunta potrebbe iniziare a diventare significativo [Modifica: I.e, non sarebbe più costante], quindi Theta (n) non sarebbe più preciso. Nel solito caso, possiamo ignorare il tempo per le aggiunte perché è un fattore costante.
Leggi altre domande sui tag theory algorithms computer-science sorting