Strutture dati e algoritmi - Panoramica

La struttura dei dati è un modo sistematico per organizzare i dati al fine di utilizzarli in modo efficiente. I seguenti termini sono i termini di base di una struttura dati.

• Interface- Ogni struttura dati ha un'interfaccia. L'interfaccia rappresenta l'insieme di operazioni supportate da una struttura dati. Un'interfaccia fornisce solo l'elenco delle operazioni supportate, il tipo di parametri che possono accettare e il tipo di ritorno di queste operazioni.

• Implementation- L'implementazione fornisce la rappresentazione interna di una struttura dati. L'implementazione fornisce anche la definizione degli algoritmi utilizzati nelle operazioni della struttura dati.

Caratteristiche di una struttura dati

• Correctness - L'implementazione della struttura dati dovrebbe implementare correttamente la sua interfaccia.

• Time Complexity - Il tempo di esecuzione o il tempo di esecuzione delle operazioni della struttura dati deve essere il più piccolo possibile.

• Space Complexity - L'utilizzo della memoria di un'operazione di struttura dati dovrebbe essere il meno possibile.

Necessità della struttura dei dati

Poiché le applicazioni diventano complesse e ricche di dati, ci sono tre problemi comuni che le applicazioni devono affrontare oggigiorno.

• Data Search- Considera un inventario di 1 milione (10 ⁶ ) articoli di un negozio. Se l'applicazione deve cercare un elemento, deve cercare un elemento in 1 milione (10 ⁶ ) elementi ogni volta che rallenta la ricerca. Man mano che i dati crescono, la ricerca diventerà più lenta.

• Processor speed - La velocità del processore, sebbene molto elevata, si riduce se i dati crescono fino a un miliardo di record.

• Multiple requests - Poiché migliaia di utenti possono cercare i dati contemporaneamente su un server web, anche il server veloce non riesce durante la ricerca dei dati.

Per risolvere i problemi sopra menzionati, le strutture di dati vengono in soccorso. I dati possono essere organizzati in una struttura di dati in modo tale che non sia necessario cercare tutti gli elementi e che i dati richiesti possano essere cercati quasi istantaneamente.

Casi del tempo di esecuzione

Ci sono tre casi che vengono solitamente utilizzati per confrontare il tempo di esecuzione di varie strutture dati in modo relativo.

• Worst Case- Questo è lo scenario in cui una particolare operazione della struttura dati richiede il tempo massimo possibile. Se il tempo del caso peggiore di un'operazione è ƒ (n), questa operazione non richiederà più del tempo ƒ (n) dove ƒ (n) rappresenta la funzione di n.

• Average Case- Questo è lo scenario che descrive il tempo medio di esecuzione di un'operazione di una struttura dati. Se un'operazione richiede ƒ (n) tempo in esecuzione, allora m operazioni richiederanno mƒ (n) tempo.

• Best Case- Questo è lo scenario che descrive il minor tempo possibile di esecuzione di un'operazione di una struttura dati. Se un'operazione richiede ƒ (n) tempo in esecuzione, l'operazione effettiva potrebbe richiedere tempo come numero casuale che sarebbe massimo come ƒ (n).

Terminologia di base

• Data - I dati sono valori o un insieme di valori.

• Data Item - Il dato si riferisce alla singola unità di valori.

• Group Items - Gli elementi di dati suddivisi in elementi secondari sono chiamati elementi di gruppo.

• Elementary Items - Gli elementi di dati che non possono essere divisi sono chiamati elementi elementari.

• Attribute and Entity - Un'entità è quella che contiene determinati attributi o proprietà, a cui possono essere assegnati valori.

• Entity Set - Entità con attributi simili formano un insieme di entità.

• Field - Il campo è una singola unità elementare di informazioni che rappresenta un attributo di un'entità.

• Record - Record è una raccolta di valori di campo di una determinata entità.

• File - File è una raccolta di record delle entità in un determinato set di entità.