Algoritmi/Le tabelle di simboli

Indice del libro

tabella di simboli (o dizionario) = struttura dati formata da record, ovvero struct con dati aggregati di cui uno è la chiave.

Si può estrarre la chiave dal record e stabilire se una chiave è minore o uguale a un'altra determinando una relazione d'ordine.

Algoritmi di ricerca

modifica

Gli algoritmi di ricerca, cioè le implementazioni delle tabelle di simboli, possono avere strutture lineari, ad albero o a tabella di hash.

Strutture lineari

modifica
  • array: ordinati o non ordinati;
  • liste: ordinate o non ordinate;
  • tabelle ad accesso diretto: l'insieme K contenente tutti i dati memorizzati è un sottoinsieme dell'insieme universo U:
    • vantaggio: ogni dato in un suo sottoinsieme K ha un indice → l'accesso è diretto (ricerca indicizzata per chiave);
    • svantaggio: il vettore dovrà avere un numero di celle pari alla cardinalità di U → rimangono delle celle vuote → spreco di memoria lineare nel numero di dati, soprattutto se la cardinalità di K è molto minore di quella di U.

Strutture ad albero

modifica
  • alberi binari di ricerca (BST): efficienti;
  • alberi bilanciati: (es. RB-tree) garantiscono che le operazioni siano sempre di complessità logaritmica e non degenerino in lineari.

Operazioni

modifica
  • data una chiave → inserimento di un nuovo elemento
  • data una chiave → ricerca di un elemento[1]
  • data una chiave → cancellazione di elemento specificato
  • dato un numero k → selezione del k-esimo elemento più piccolo
  • ordinamento della tabella di simboli in base alla chiave
  • unione di due tabelle di simboli

Complessità di caso peggiore

modifica

La complessità dell'inserimento di un nuovo elemento all'interno di una lista o di un array varia a seconda se gli elementi sono ordinati:

  • non ordinati: l'inserimento ha un costo unitario (per es. inserimento sempre in testa);
  • ordinati: l'inserimento ha un costo lineare, perché bisogna inserire il nuovo elemento mantenendo l'ordinamento:
    • array: bisogna spostare tutti gli elementi di una cella per far spazio al nuovo elemento;
    • liste: l'inserimento implica una ricerca per scansione.

La ricerca binaria si deve effettuare su un array ordinato → può essere inefficiente se l'array varia molto e bisogna ordinarlo spesso.

Complessità di caso medio

modifica

Nel caso medio:

  • le operazioni sulle strutture lineari sono quasi sempre lineari nel numero dei dati;
  • le operazioni sulle strutture ad albero sono quasi sempre logaritmiche nel numero dei dati (nel caso peggiore sono lineari);
  • le operazioni sulle tabelle di hash hanno costo unitario, ma senza spreco di memoria come nelle tabelle ad accesso diretto.
  1. Si distinguono le ricerche con successo (hit) e quelle con insuccesso (miss).