Key index counting - Algoritmi e strutture dati

elenco di “che compito ha fatto”. Notiamo che il vettore

che indica che compito ha fatto lo studente in questo

caso usa dei numeri ma potrebbe usare delle etichette,

l’unica cosa rilevante è che queste etichette siano in

numero finito, a questo punto se mi trovo delle etichette,

o dette variabili categoriche, posso sempre rimpiazzarle

con dei numeri, quindi si tratta di un passaggio alla

codifica numerica, esso è il primo passo da fare.

Ci aspettiamo di trovare questo risultato:

abbiamo quindi che i numeri sono ordinati ma anche i

nomi sono ordinati

L’idea ora è che siccome noi abbiamo codificato le

variabili categoriche con dei numeri noi possiamo fare

un giro all’interno del vettore, considerando che le

variabili sono codificate 1,2, 3, 4 ma il vettore lo

consideriamo che parte da 0, contiamo quanti 1 ci sono,

quanti 2 ci sono etc…, quindi quando trovo un 2

incremento la colonna 2+1, quando trovo un 3

incremento la colonna 3+1 etc…:

notiamo che in questo caso la colonna 0 e 1 sono

sempre pari a 0 perché incremento la colonna i+1

La colonna 0 mi dice da dove devo cominciare a mettere

gli elementi etichettati 1, gli elementi etichettati 2

devono cominciare alla fine degli elementi etichettati 1,

quindi alla colonna 3 perché ho 3 elementi 1

Ora devo capire dove finiranno gli elementi nel vettore

riordinato, faccio il conto e dico che gli elementi 1

cominciano dalla colonna 0 e occupano 0, 1, 2 perché

sono 3 elementi, gli elementi 2 cominciano dalla colonna

3 ce ne sono 5 quindi occuperanno 3, 4, 5, 6, 7, allora gli

elementi 3 cominciano dalla colonna 8 etc…:

sono passato quindi da quella che è la frequenza relativa

degli elementi (l’immagine prima della precedente) a

quella cumulativa, quest’ultima riportata, che mi dice

che gli 1 cominceranno dalla posizione 0, i 2 dalla

colonna 3, i 3 dalla colonna 8, i 4 dalla 14 e i 5 dalla 20,

a questo punto in una passata arrivo a ciò:

quindi dico ad esempio: Anderson è un 2 quindi lo metto

nella colonna dove ci stanno i 2 che è aux[3], poi Brown

è 3 quindi lo metto nel primo posto dei 3 etc….

La prima operazione di conteggio prima delle frequenze

relative e poi quelle cumulative è proporzionale al

numero di elementi N, il riordino del vettore è anch’esso

proporzionale al N perché la faccio in una passata, per

riordinare il vettore sulla base delle categorie anziché

sulla base dei nomi ci vuole ancora un tempo

proporzionale a N

Nel caso dei confronti la complessità minima richiesta è

N*log(N), se invece ci basiamo sul calcolo portiamo la

complessità a N cioè lineare, siamo quindi riusciti a fare

il meglio del meglio in un caso in cui possiamo evitare di

fare i confronti perché abbiamo codificato le categorie