Algoritmi e Strutture Dati Capitolo 8 - Insiemi e dizionari Alberto Montresor Università di Trento This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA. © Alberto Montresor 1 Insiemi e dizionari Insieme ✦ Collezione di oggetti ✦ Dizionario ✦ Insieme di associazioni chiave-valore ✦ Implementazioni ✦ Molte delle strutture dati viste finora ✦ Vantaggi e svantaggi ✦ © Alberto Montresor 2 Insiemi realizzati con vettori booleani Insieme ✦ Interi 1...N ✦ Collezione di N oggetti memorizzati in un vettore ✦ Rappresentazione dell’insieme: ✦ Vettore booleano di N elementi ✦ Vantaggi ✦ Notevolmente semplice ✦ Efficiente verificare se un elemento appartiene all’insieme ✦ Svantaggi ✦ Occupazione di memoria O(N), indipendente dalla dimensione dell’insieme ✦ Operazioni inefficienti O(N) ✦ © Alberto Montresor 3 Insiemi realizzati con vettori booleani © Alberto Montresor 4 Insiemi realizzati con liste non ordinate Vantaggi ✦ Occupazione di memoria proporzionale alla dimensione del vettore ✦ Svantaggi ✦ Operazioni di ricerca e cancellazione: O(n) ✦ Operazioni di inserimento (senza controllo duplicati): O(1) ✦ Operazioni di unione, intersezione e differenza: O(nm) ✦ © Alberto Montresor 5 Insiemi realizzati con liste non ordinate © Alberto Montresor 6 Insiemi realizzati con liste ordinate Vantaggi ✦ Occupazione di memoria proporzionale alla dimensione dell’insieme ✦ Operazioni di unione, intersezione e differenza: O(n) ✦ Svantaggi ✦ Operazioni di ricerca, inserimento e cancellazione: O(n) ✦ © Alberto Montresor 7 Insiemi realizzati con liste ordinate © Alberto Montresor 8 Realizzazione con strutture dati complesse Con alberi di ricerca bilanciati ✦ Ricerca, inserimento, cancellazione: O(log n) ✦ Viene mantenuto l’ordinamento ✦ Elencare tutti gli elementi: O(n) ✦ Con tabelle hash ✦ Ricerca, inserimento, cancellazione: O(1) ✦ Viene perso l’ordinamento ✦ Elencare tutti gli elementi: O(m), dove m è la dimensione della tabella hash ✦ © Alberto Montresor 9 Insiemi e dizionari Insieme ✦ Collezione di oggetti ✦ Dizionario ✦ Insieme di associazioni chiave-valore ✦ Implementazioni ✦ Molte delle strutture dati viste finora ✦ Vantaggi e svantaggi ✦ © Alberto Montresor 10
Scarica
