Motivazione

L’aumentare della potenza di calcolo e delle strumentazioni tecniche hanno portato alla sempre maggior produzione di dati.

Ad esempio:

• database
• information retrieval
• bioinformatica
• etc

A cosa siamo interessati?

• Gestione di tali dati
• Indicizzazione e interrogazione
• Compressione

Una veloce catalogazione

Possiamo catalogare (in modo non esaustivo) le strutture dati in base alla quantità di bit necessari a memorizzare (tramite una certa rappresentazione in memoria) dei dati.

Definiamo $\mathcal Z =$ numero di bit (teoricamente) ottimale per memorizzare un certo dato

• strutture dati implicite: $\mathcal Z + \mathcal O(1)$ bit (es: $\mathcal Z + 14$ bit)
• strutture dati succinte: $\mathcal Z + o(\mathcal Z)$ bit (es: $\mathcal Z + \log \mathcal Z$ o $\mathcal Z + \sqrt \mathcal Z$ bit)
  • spazio richiesto “vicino” al bound teorico ($o(Z)$ bit aggiuntivi)
  • tempo: richiesto per le operazioni “comparabile” a quello che si avrebbe senza vincoli sullo spazio
• strutture dati compatte: $O(\mathcal Z)$ bit

Si ricorda che, avendo $x_9 = +\infin$,

$$ \text{se }\lim_{x\rarr x_0}\frac{f(x)}{g(x)} = 0 \implies f(x) = o_{x_0}(g(x)) $$