Datenstrukturen & Algorithmen - Übersicht
Die Datenstruktur ist eine systematische Methode zum Organisieren von Daten, um sie effizient zu nutzen. Die folgenden Begriffe sind die Grundbegriffe einer Datenstruktur.
Interface- Jede Datenstruktur hat eine Schnittstelle. Die Schnittstelle repräsentiert die Menge von Operationen, die eine Datenstruktur unterstützt. Eine Schnittstelle enthält nur die Liste der unterstützten Operationen, den Typ der Parameter, die sie akzeptieren können, und den Typ dieser Operationen.
Implementation- Die Implementierung bietet die interne Darstellung einer Datenstruktur. Die Implementierung liefert auch die Definition der Algorithmen, die in den Operationen der Datenstruktur verwendet werden.
Eigenschaften einer Datenstruktur
Correctness - Die Implementierung der Datenstruktur sollte die Schnittstelle korrekt implementieren.
Time Complexity - Die Laufzeit oder die Ausführungszeit von Operationen der Datenstruktur muss so klein wie möglich sein.
Space Complexity - Die Speichernutzung einer Datenstrukturoperation sollte so gering wie möglich sein.
Bedarf an Datenstruktur
Da Anwendungen immer komplexer und datenreicher werden, gibt es drei häufige Probleme, mit denen Anwendungen heutzutage konfrontiert sind.
Data Search- Betrachten Sie einen Bestand von 1 Million (10 6 ) Artikeln eines Geschäfts. Wenn die Anwendung einen Artikel durchsuchen soll, muss sie jedes Mal, wenn die Suche verlangsamt wird, einen Artikel in 1 Million (10 6 ) Artikeln suchen. Wenn die Daten wachsen, wird die Suche langsamer.
Processor speed - Obwohl die Prozessorgeschwindigkeit sehr hoch ist, ist sie begrenzt, wenn die Daten auf Milliarden Datensätze anwachsen.
Multiple requests - Da Tausende von Benutzern gleichzeitig auf einem Webserver nach Daten suchen können, fällt selbst der schnelle Server beim Durchsuchen der Daten aus.
Um die oben genannten Probleme zu lösen, werden Datenstrukturen gerettet. Daten können in einer Datenstruktur so organisiert werden, dass möglicherweise nicht alle Elemente durchsucht werden müssen und die erforderlichen Daten fast sofort durchsucht werden können.
Ausführungszeitfälle
Es gibt drei Fälle, die normalerweise verwendet werden, um die Ausführungszeit verschiedener Datenstrukturen relativ zu vergleichen.
Worst Case- Dies ist das Szenario, in dem eine bestimmte Datenstrukturoperation maximal so lange dauert. Wenn die Worst-Case-Zeit einer Operation ƒ (n) ist, dauert diese Operation nicht länger als ƒ (n), wobei ƒ (n) die Funktion von n darstellt.
Average Case- Dies ist das Szenario, das die durchschnittliche Ausführungszeit einer Operation einer Datenstruktur darstellt. Wenn eine Operation bei der Ausführung ƒ (n) Zeit benötigt, benötigen m Operationen mƒ (n) Zeit.
Best Case- Dies ist das Szenario, das die geringstmögliche Ausführungszeit einer Operation einer Datenstruktur darstellt. Wenn eine Operation bei der Ausführung ƒ (n) Zeit benötigt, kann die tatsächliche Operation Zeit als Zufallszahl benötigen, die maximal ƒ (n) betragen würde.
Grundbegriffe
Data - Daten sind Werte oder Wertesätze.
Data Item - Datenelement bezieht sich auf eine einzelne Werteinheit.
Group Items - Datenelemente, die in Unterelemente unterteilt sind, werden als Gruppenelemente bezeichnet.
Elementary Items - Datenelemente, die nicht geteilt werden können, werden als Elementarelemente bezeichnet.
Attribute and Entity - Eine Entität ist eine Entität, die bestimmte Attribute oder Eigenschaften enthält, denen Werte zugewiesen werden können.
Entity Set - Entitäten mit ähnlichen Attributen bilden einen Entitätssatz.
Field - Feld ist eine einzelne elementare Informationseinheit, die ein Attribut einer Entität darstellt.
Record - Datensatz ist eine Sammlung von Feldwerten einer bestimmten Entität.
File - Datei ist eine Sammlung von Datensätzen der Entitäten in einem bestimmten Entitätssatz.