Imparare gli algoritmi

Capitolo 8. Avvolgere il tutto

Questo lavoro è stato tradotto utilizzando l'AI. Siamo lieti di ricevere il tuo feedback e i tuoi commenti: [e-mail]

Il mio obiettivo in questo libro è stato quello di introdurti agli algoritmi fondamentali e ai tipi di dati essenziali utilizzati in informatica. Devi sapere come implementare in modo efficiente i seguenti tipi di dati per massimizzare le prestazioni del tuo codice:

Borsa

Un elenco collegato garantisce prestazioni O(1) quando si aggiunge un valore. Se scegli di utilizzare un array, allora devi impiegare un ridimensionamento geometrico per estendere le dimensioni dell'array in modo da garantire prestazioni O(1) ammortizzate sul suo utilizzo medio (anche se continuerai a incorrere in prestazioni O(N) runtime sugli eventi di ridimensionamento poco frequenti). Nota che un sacchetto non consente di rimuovere i valori e non impedisce l'aggiunta di valori duplicati.

Pila

Una lista collegata può memorizzare i valori in uno stack, quindi push() e pop()hanno prestazioni runtime O(1). La pila registra top della pila per spingere e rimuovere i valori.

Coda

Una lista collegata può memorizzare in modo efficiente una coda, quindi enqueue() edequeue() hanno prestazioni di runtime O(1). La coda registra il nodo first e il nodo last nell'elenco collegato per aggiungere e rimuovere in modo efficiente i valori dalla coda.

Tabella dei simboli

L'approccio di indirizzamento aperto per le tabelle di simboli è sorprendentemente ...