Komplexität

Question 1

Einflussfaktoren für den Zeit- und Speicherplatzbedarf eines Algorithmus

Answer 1

1. Anzahl und Größe der Eingabedaten (“Problemgröße”) [#Knoten]
2. Komplexität des Algorithmus/ der Aufgabe [for-Schleife n-mal durchlaufen]
3. Eigenschaften der zur Ausführung eingesetzten Rechenanlage (z.B. Schnelligkeit, Befehlssatz)

⇒ bei Art der Rechenanlage häufig abstrakte Maschinen zur Komplexitätsberechnung

Question 2

Komplexität

Answer 2

• wie viel Zeit
• wie viel Speicherplatz benötigt ein Algo zur Ausführung für eine gegebene Problemgröße

⇒ unabhängig von Problemgröße/Rechenanlage

⇒ möglichst effiziente Alogrithmen, also von geringer Komplexität

⇒ hier immer Zeitkomplexität

Question 3

Idealisierende Annahmen

Answer 3

• Jede Elementaroperation (Zuweisung, Addition, Subtraktion, Multiplikation, Vergleichen etc.) = 1 Rechenschritt
• Aufwändige Operationen (z.B. Matrizenmultiplikation) nicht verfügbar bzw. durch einfachere Operationen zu realisieren.
• Einheitliche Größe der betrachteten Daten, Darstellung in jeweils einer Speicherzelle

Question 4

Elementaroperationen (ELOP)

Answer 4

Question 5

typische Komplexitätsfunktionen (aufsteigend)

Answer 5

• O(log₂ n): Logarithmische Komplexität
• O(n): Lineare Komplexität
• O(n log₂ n): Leicht überlineare Komplexität
• O(n²): Quadratische Komplexität
• O(n³): Kubische Komplexität
• O(2^n): Exponentielle Komplexität

Question 6

„Groß-Oh-Notation“

Answer 6

beschreibt Wachstum von Funktionen für große n bzw. das Verhalten von n -> unendlich.

Question 7

Große/kleine Problemauspräungen

Answer 7

Große Problemauspräungen

• Aussagen meist relativ genau zutreffend
• Konstante Summanden unwichtig
• Höchste Potenz entscheidend

Kleine Problemauspräungen

• Konstante Faktoren mit hoher Bedeutung
• Aussage der Groß-Oh-Notation i.a. sehr unpräzise

Question 8

Komplexität - Mengen

Answer 8

Question 9

Bekannte Problemklassen - Sortierverfahren

Answer 9

Einfüge Sort

• O(n²)

Quicksort

• T_max O(n²)
• T_avg O(n log₂ n)

Heapsort

• T_max = T_avg O(n log₂ n)

Algorithmen, die “Vergleichen & Vertauschen”

• T_max = T_avg O(n log₂ n)

Shakersort

• T_min O(n)
• T_max O(n²)

Question 10

Bekannte Problemklassen

Answer 10

DFS/BFS: O(|E| + |N|), da jeder Knoten/Kante höchst. 1x in jeder Richtung durchlaufen

Statische DS: Direkter Zugriff auf Feldelemente: O(1)

Hamiltonscher Zyklus: O(m!) [komplexer als Eulerkreisproblem]