Analyse der Komplexität verschiedener Datenstrukturen

9.1 Komplexität von Arrays, Listen, Hash-Tabellen.

Die Analyse der Komplexität von Datenstrukturen konzentriert sich auf die Bewertung der Laufzeit und des Speicherbedarfs zur Durchführung verschiedener Operationen (z.B. Einfügen, Löschen, Suchen). Das Verständnis der Komplexität hilft Entwicklern dabei, die am besten geeigneten Datenstrukturen für bestimmte Aufgaben auszuwählen und somit die Ressourcen effizient zu nutzen.

1. Arrays:

• Zugriff per Index: O(1)
• Elementsuche: O(n)
• Elementeinfügen: O(n) (im schlechtesten Fall, Einfügen in die Mitte des Arrays)
• Elementlöschen: O(n) (im schlechtesten Fall, Löschen aus der Mitte des Arrays)
• Speicher: O(n)

Nutzungsbeispiel: Arrays sind effektiv für Szenarien, die schnellen Zugriff per Index erfordern, wie Tabellen und Zeitreihen.

2. Verkettete Listen (Linked Lists):

• Zugriff per Index: O(n)
• Elementsuche: O(n)
• Elementeinfügen: O(1) (wenn Position bekannt ist)
• Elementlöschen: O(1) (wenn Position bekannt ist)
• Speicher: O(n)

Nutzungsbeispiel: Verkettete Listen sind nützlich, wenn häufiges Hinzufügen oder Entfernen von Elementen erforderlich ist, z.B. zur Implementierung von Warteschlangen und Stacks.

3. Hash-Tabellen (Hash Tables):

• Elementsuche: O(1) (im Durchschnitt)
• Elementeinfügen: O(1) (im Durchschnitt)
• Elementlöschen: O(1) (im Durchschnitt)
• Speicher: O(n)

Nutzungsbeispiel: Hash-Tabellen sind effektiv für die Implementierung von Dictionaries und Key-Value-Datenbanken.

9.2 Komplexität von Bäumen und Graphen.

1. Binäre Suchbäume (Binary Search Trees, BST):

• Elementsuche: O(log n) (im Durchschnitt)
• Elementeinfügen: O(log n) (im Durchschnitt)
• Elementlöschen: O(log n) (im Durchschnitt)
• Speicher: O(n)

Nutzungsbeispiel: Suchbäume werden in Datenbanken und Datenstrukturen wie Sets und Maps eingesetzt.

2. Graphen (Graphs):

• Breitensuche (BFS): O(V + E)
• Tiefensuche (DFS): O(V + E)
• Kürzester Pfad (Dijkstra): O(V^2) oder O(E + V log V) für Adjazenzlisten
• Speicher: O(V + E)

Nutzungsbeispiel: Graphen werden in Netzwerkrouting, sozialen Netzwerken, Verbindungsanalyse und Graphdatenbanken genutzt.

9.3 Auswahl der passenden Datenstruktur

Wie wählt man Datenstrukturen anhand der Komplexitätsanalyse aus?

Merkmale der Aufgabe:

Bestimme, welche Operationen am häufigsten und kritischsten für deine Aufgabe sind (Suchen, Einfügen, Löschen).

Datengröße:

Berücksichtige die Datengröße und die verfügbaren Ressourcen. Für kleine Datenmengen kannst du einfache Strukturen wie Arrays und verkettete Listen verwenden.

Leistungsanforderungen:

Bestimme, was bei deiner Aufgabe wichtiger ist: die Laufzeit der Operationen oder der Speicherverbrauch.

Speicheranforderungen:

Wenn der Speicher begrenzt ist, wähle Datenstrukturen mit geringer Speicherkomplexität.

Beispiele für die Optimierung realer Aufgaben hinsichtlich der zeitlichen und räumlichen Komplexität

Verwendung passender Datenstrukturen:

Beispiel: Für häufige Suchoperationen verwende Hash-Tabellen, und für häufige Einfüge-/Löschoperationen — verkettete Listen.

Reduzierung der Anzahl von Operationen:

Beispiel: Optimierung von Schleifen und Ausschluss unnötiger Berechnungen, Verwendung von Memoisierung und dynamischem Programmieren.

Parallele Datenverarbeitung:

Beispiel: Verwendung von Multithreading oder verteilten Systemen zur Verarbeitung großer Datenmengen.

9.4 Beispiele fertiger Aufgaben zur Analyse von Datenstrukturen.

Praktische Aufgaben zur Analyse und Optimierung realer Probleme

Aufgabe 1: Optimierung der Suche in einem Array

Du hast ein Array mit 10 Millionen Zahlen. Optimiere den Algorithmus zur Suche eines Elements.

Lösung:

Verwende binäre Suche für ein sortiertes Array.

Aufgabe 2: Optimierung der Arbeit mit einer verketteten Liste

Du hast eine verkettete Liste und musst häufig Elemente einfügen und löschen.

Lösung:

Verwende eine doppelt verkettete Liste zur Optimierung von Einfügen und Löschen.

Aufgabe 3: Datenverarbeitung in einer Hash-Tabelle

Implementiere ein Dictionary mit schnellem Datenzugriff.

Lösung:

Verwende eine Hash-Tabelle für Einfüge-, Lösch- und Suchoperationen mit einer Laufzeitkomplexität von O(1).

Aufgabe 4: Graphdurchlauf

Finde den kürzesten Weg im Graph eines Straßennetzes.

Lösung:

Verwende den Dijkstra-Algorithmus mit einer Laufzeitkomplexität von O(V^2) für die Adjazenzmatrix oder O(E + V log V) für die Adjazenzliste.