|
|
Si può rappresentare un insieme con una lista, non ordinata, i cui elementi sono quelli dell’ insieme. In questo modo, l’ insieme non deve necessariamente essere compreso tra 0 ed n-1 come nel caso degli insiemi con vettore booleano. Inoltre l’ occupazione di memoria dell’ insieme cresce linearmente col numero degli elementi effettivamente presenti nell’ insieme. Le operazioni su insiemi si riducono cosi a procedure che scandiscono liste, inserendovi o cancellandovi elementi. In questo caso gli operatori “appartiene”, “inserisci” e “cancella” hanno complessità O(n) , in quanto occorre scandire interamente la lista. Addirittura supposto che un insieme B abbia m elementi e un insieme A n elementi, la complessità degli operatori “unione”, “intersezione” e “differenza” risulta O(n m) visto che per ogni oggetto in A occorre scandire interamente la lista B. Tutto ciò fa delle liste non ordinate uno strumento inefficiente per realizzare una struttura dati di tipo insieme. Se sugli elementi dell’insieme è invece definita una relazione di ordinamento totale (es. “<”), l’insieme può essere rappresentato con una lista ordinata per valori crescenti degli elementi. I vantaggi di questa realizzazione sono che operatori in O(n m) con liste non ordinate, migliorano la complessità a O(n + m), che risulta essere ottima in quanto il problema della fusione di due sequenze ordinate ha complessità Omega(n + m).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.