07: Array, Liste, Hash

La complessità ammortizzata di un'operazione è il costo medio di un'operazione in una sequenza di operazioni.

Il costo ammortizzato di un inserimento in un array dinamico che raddoppia la sua dimensione quando è pieno è O(1).

Il costo ammortizzato di un inserimento in un array dinamico che espande la sua dimensione di una costante è O(n).

Una lista è una struttura dati lineare in cui l'ordine degli elementi è determinato dai puntatori che indicano l'elemento successivo. Il primo elemento di una lista è indicato da un puntatore chiamato "head".

In una lista, l'operazione di inserimento e di cancellazione di un elemento alla testa della lista ha una complessità temporale O(1).

In una lista, l'operazione di inserimento o di cancellazione di un elemento in una posizione qualsiasi della lista ha una complessità temporale O(n), dove n è la posizione dell'elemento.

Le liste sono efficienti per l'inserimento e la cancellazione, ma meno efficienti per l'accesso ad elementi specifici rispetto agli array.

Le liste sono usate per rappresentare dati che cambiano dinamicamente, come ad esempio un elenco di persone in una coda.

La probabilità che un qualsiasi elemento venga inserito in una specifica lista è 1 m (uniformità semplice).

Il tempo medio per cercare un dato elemento in una tabella hash con liste di collisione. Rappresenta la complessità del caso medio.

La lunghezza media di una lista in una tabella hash.

Il tempo richiesto per trovare una specifica lista in una tabella hash. Questo è costante, indipendentemente dalla dimensione della tabella.

Il numero di elementi che precedono un dato elemento xi nella stessa lista, dopo che xi è stato inserito.

Il tempo necessario per controllare gli elementi presenti nella lista in cui si trova l'elemento cercato, oltre all'elemento stesso.

Il tempo totale richiesto per cercare un elemento in una tabella hash con liste di collisione.

Il tempo medio necessario per ricercare un elemento in una tabella hash in cui le collisioni vengono risolte tramite liste.

Il tempo medio per trovare un elemento in una tabella hash con liste di collisione, escluse l'operazione di hashing.

La complessità media di una ricerca in una tabella hash con liste di collisione.

Rappresenta l'insieme di tutte le possibili chiavi che possono essere inserite nella tabella hash. Ad esempio, se stiamo memorizzando numeri di matricola a 6 cifre, l'universo delle chiavi sarebbe composto da tutti i possibili numeri di matricola a 6 cifre.

Rappresenta l'insieme di tutte le chiavi effettivamente inserite nella tabella hash.

Funzione che trasforma una chiave in un indice della tabella hash. L'indice calcolato dalla funzione hash indica la cella in cui la chiave verrà memorizzata.

Il caso peggiore per la ricerca in una tabella hash si verifica quando tutte le chiavi vengono mappate nella stessa cella della tabella. In questo caso, la ricerca diventa come una ricerca lineare in una lista, quindi il costo è proporzionale al numero di elementi nella tabella.

Il caso migliore per la ricerca in una tabella hash si verifica quando la cella corrispondente alla chiave cercata è vuota o contiene un solo elemento. In questo caso, la ricerca è molto efficiente e richiede solo un accesso alla cella della tabella.

Il caso medio per la ricerca in una tabella hash dipende dalla funzione hash. Se la funzione hash è uniforme, ogni cella della tabella riceve circa lo stesso numero di chiavi, quindi la ricerca richiede mediamente un tempo proporzionale al fattore di carico.

Il fattore di carico è il rapporto tra il numero di elementi nella tabella hash (N) e il numero di celle nella tabella (m). Un fattore di carico alto indica che la tabella è piena e potrebbe causare un aumento dei tempi di ricerca.

Un array è come una sequenza di caselle in memoria, ognuna delle quali può contenere un valore. Le caselle hanno tutte la stessa dimensione e sono disposte in modo sequenziale. L'accesso a una determinata casella è molto rapido e richiede un tempo costante, indipendentemente dalla posizione della casella.

Un array statico è un tipo di array in cui la dimensione massima è fissa e non può essere modificata durante l'esecuzione del programma. Ciò significa che il numero massimo di elementi che possono essere memorizzati nell'array è definito al momento della creazione dell'array stesso.

In un array statico, N rappresenta il numero attuale di elementi memorizzati all'interno dell'array. M rappresenta la dimensione massima dell'array, ovvero il numero massimo di elementi che l'array può contenere.

L'operazione di inserimento di un nuovo elemento in un array statico consiste nell'aggiungere l'elemento all'ultima posizione disponibile dell'array, incrementando il numero di elementi memorizzati. Se l'array è pieno, non è possibile inserire nuovi elementi.

L'operazione di rimozione di un elemento da un array statico implica la ricerca dell'elemento da rimuovere e la sua eliminazione dall'array. Gli elementi successivi vengono spostati in avanti per riempire il vuoto lasciato dall'elemento rimosso.

Il costo dell'inserimento in un array statico è costante, ovvero O(1), in quanto richiede un'operazione di accesso e scrittura in una posizione specifica dell'array. Il costo non dipende dal numero di elementi o dalla dimensione dell'array.

Il costo della rimozione da un array statico è lineare, ovvero O(N), in quanto richiede un ciclo per scorrere l'array e spostare gli elementi successivi per riempire il vuoto lasciato dall'elemento rimosso. Il costo dipende dal numero di elementi presenti nell'array.

Se l'array statico è vuoto o se non ci sono elementi uguali a quello da eliminare all'interno dell'array, l'operazione ArrayDelete restituirà nil (null).

Nell'inserimento in un array dinamico, se la dimensione massima dell'array (M) è molto più grande del numero di elementi (N), il costo di un inserimento è generalmente costante (O(1)). La complessità è costante poiché c'è abbastanza spazio disponibile per l'inserimento, quindi non è necessario riallocare l'array.

Nell'inserimento in un array dinamico, se la dimensione massima dell'array (M) è uguale al numero di elementi (N), il costo di ogni inserimento successivo richiederà una riallocazione dell'array, con una complessità di O(N).

La dimensione massima (M) e le operazioni eseguite influenzano la complessità del tempo per le operazioni in un array dinamico.

Una strategia per gestire la crescita di un array dinamico è quella di raddoppiare la dimensione dell'array quando è pieno. Questo approccio prevede un investimento in spazio, ma porta a un guadagno futuro in tempo. Quando l'array è pieno, viene raddoppiata la dimensione massima (M) e viene allocato nuovo spazio per gli elementi aggiuntivi.

Quando il numero di elementi in un array dinamico si riduce ad un quarto della dimensione massima (M), la dimensione dell'array viene dimezzata. Questa strategia consente di recuperare spazio sprecato, riducendo la dimensione dell'array e il consumo di memoria.

La prima idea di gestione della crescita di un array dinamico prevede una dimensione massima fissa (M) e riallocazioni ogni volta che si inserisce un nuovo elemento. La seconda idea prevede di raddoppiare la dimensione dell'array quando è pieno e di dimezzarla quando il numero di elementi scende a 1/4 della dimensione massima. La scelta tra le due idee dipende dalle esigenze specifiche dell'applicazione: la prima idea è più semplice da implementare, ma può portare a riallocazioni frequenti, mentre la seconda idea è più efficiente nello spazio a lungo termine, ma più complessa da implementare.

In una sequenza di 2K inserimenti in un array dinamico, dove la dimensione massima (M) è inizialmente 1, la prima idea (dimensione fissa) comporta un costo di O(N) per ogni inserimento tranne il primo. La seconda idea (raddoppio e dimezzamento) comporta un costo di O(N) per K inserimenti e un costo di O(1) per gli altri. La complessità ammortizzata della seconda idea è quindi inferiore, in quanto il costo medio per inserimento è inferiore.

L'algoritmo ArraySearch(A, k) cerca un elemento specifico k in un array A. Controlla ogni elemento dell'array uno alla volta. Se trova l'elemento k, restituisce il valore trovato. Altrimenti, restituisce nil, indicando che l'elemento non è presente nell'array.

La complessità di un algoritmo misura il tempo necessario per eseguire l'algoritmo in funzione della dimensione dell'input. Una complessità lineare indica che il tempo di esecuzione cresce proporzionalmente alla dimensione dell'input. Quindi, se l'input raddoppia, anche il tempo di esecuzione raddoppia.

Quando si inserisce un elemento in un array ordinato, è necessario mantenere l'ordinamento. Il tempo necessario per spostare gli elementi per fare spazio al nuovo elemento può essere proporzionale al numero di elementi già presenti nell'array. Quindi, l'inserimento in un array ordinato ha una complessità lineare O(N).

L'algoritmo ArrayExtend(A, n) crea un nuovo array B più grande dell'array originale A. La dimensione di B è aumentata di n elementi. Tutti gli elementi di A vengono copiati in B. L'operazione ArrayExtend ha una complessità lineare O(N) perché la copia degli elementi richiede un tempo proporzionale al numero di elementi in A.

Un array dinamico è un array che può cambiare dimensione durante l'esecuzione del programma. Ciò è possibile perché invece di allocare memoria per il numero massimo di elementi possibili in anticipo, si alloca memoria per un determinato numero di elementi e si espande l'array quando necessario. Questa strategia è utile quando non si conosce in anticipo il numero di elementi che dovranno essere memorizzati nell'array.

La prima strategia per l'inserimento in un array dinamico prevede l'espansione dell'array di una cella ogni volta che viene aggiunto un nuovo elemento. Se l'array è pieno, viene esteso di una cella con una complessità lineare O(N). Se invece l'array non è pieno, l'inserimento ha una complessità costante O(1).

Il costo a lungo termine degli inserimenti in un array dinamico con la prima strategia dipende dal numero di volte in cui l'array è stato espanso. Ogni espansione di un array ha una complessità lineare O(N), il che può portare a prestazioni lente se l'array viene espanso frequentemente. Per evitare ciò, si potrebbero adottare altre strategie, come ad esempio raddoppiare la dimensione dell'array quando è pieno, invece di espanderlo di una sola cella.

L'algoritmo DynArrayInsert1(A, k) inserisce un elemento k in un array dinamico A. Se l'array A è pieno, viene esteso di una cella con l'algoritmo ArrayExtend. Quindi, l'elemento k viene inserito nell'array A con l'algoritmo ArrayInsert.