2 Algorithmenanalyse und Komplexitätstheorie¶

Willkommen zur zweiten Einheit unseres Kurses “Fortgeschrittene Mathematik und Computergestützte Algorithmen”. Nachdem wir uns in der letzten Einheit mit den Grundlagen des algorithmischen Denkens beschäftigt haben, werden wir uns heute einem zentralen Konzept im Umgang mit Algorithmen widmen: Der Analyse von Algorithmen und ihrer Komplexität. Für uns bedeutet das konkret, die Effizienz verschiedener Algorithmen und Lösungsstrategien besser bewerten und vergleichen zu können.

Nach dem Studium dieser Einheit sollten Sie zumindest folgende drei der wichtigsten Punkte hier verstehen:

• Die Bedeutung der Algorithmenanalyse für praktische Anwendungen
• Die asymptotische Notation (was bedeutet Big-O?)
• Die Zeit- und Speicherkomplexität verschiedener Algorithmen nachvollziehen und vergleichen können

2.1 Wozu überhaupt Algorithmenanalyse betreiben?¶

2.1.1 Die Bedeutung effizienter Algorithmen in realen Anwendungen¶

Stellen Sie sich vor, Sie entwickeln eine Anwendung, die täglich von Millionen von Menschen genutzt wird – vielleicht eine Suchmaschine, eine medizinische App oder eineN persönlicheN KI-BeraterIn. Dafür implementieren Sie die nötigen Algorithmen. Jede Operation, die einer dieser Algorithmen dabei ausführt, wird millionenfach wiederholt – mindestens. In diesem Kontext ist der Unterschied zwischen einem effizienten und einem ineffizienten Algorithmus enorm:

• Ressourcenverbrauch: Ein ineffizienter Algorithmus führt zu erhöhten Betriebskosten, da mehr Rechenleistung und Speicher benötigt werden.
• Skalierbarkeit: Mit wachsender Datenmenge (z.B. der Anzahl der NutzerInnen und damit der verwendeten Rechnerfarm) kann ein ineffizienter Algorithmus schnell unpraktikabel werden.
• Energieverbrauch: Effizientere Algorithmen benötigen durch weniger Rechenleistung auch weniger Energie.
• Benutzererfahrung: Langsame Algorithmen führen zu längeren Wartezeiten für die BenutzerInnen, und das schadet dem Nutzen und der Beliebtheit Ihrer Anwendung.

2.1.2 Ressourcenbeschränkungen: Zeit und Speicher¶

Bei der Analyse von Algorithmen betrachten wir hauptsächlich zwei Ressourcen:

Zeit (Zeitkomplexität):

• Wie lange dauert es, bis der Algorithmus seine Aufgabe erledigt hat?
• Wie verhält sich diese Zeit, wenn die Eingabegröße wächst?

Speicher (Speicherkomplexität):

• Wie viel Speicherplatz benötigt der Algorithmus während der Ausführung?
• Wie wächst dieser Speicherbedarf mit zunehmender Eingabegröße?

Mit “Eingabegröße” ist hier so etwas gemeint wie die Länge $N$ der Liste, die sortiert werden soll, die Dimensionen $N\times N$ einer Matrix, die invertiert oder diagonalisiert werden soll, die Größe $N$ der Trainings-Datenmenge für ein Machine-Learning-Projekt, oder die Anzahl $N$ der geplanten Durchläufe einer Monte-Carlo-Simulation.

Beide Ressourcen, also sowohl Zeit als auch Speicher, sind in der Praxis begrenzt und meist besteht ein Trade-off zwischen ihnen: Ein schnellerer Algorithmus benötigt häufig mehr Speicher und umgekehrt. Die Kunst des Algorithmendesigns besteht also darin, den optimalen Kompromiss für den jeweiligen Anwendungsfall zu finden.

2.1.3 Warum Skalieren Algorithmen mit wachsender Datenmenge oder Dimension?¶

Ein fundamentales Konzept der Algorithmenanalyse ist das sogenannte Skalierungsverhalten: Wie verändert sich der Ressourcenbedarf eines Algorithmus, wenn die Eingabegröße $N$ wächst?

Betrachten wir dazu ein einfaches Beispiel und betrachten die Zeit, die zwei verschiedene Algorithmen für die Verarbeitung der gleichen Aufgabe brauchen:

• Ein Algorithmus A benötigt 100 mal $N$ Millisekunden für die Verarbeitung.
• Ein Algorithmus B benötigt 2 mal $N^2$ Millisekunden für die Verarbeitung.

Bei kleinen Werten von n mag Algorithmus B schneller erscheinen:

• Für $N$ = 5: Algorithmus A benötigt 500 ms, Algorithmus B benötigt 50 ms.
• Für $N$ = 10: Algorithmus A benötigt 1000 ms, Algorithmus B benötigt 200 ms.

Aber bei größeren Werten von $N$ wird der Unterschied dramatisch:

• Für $N$ = 1000: Algorithmus A benötigt 100 000 ms (100 Sekunden), während Algorithmus B 2 000 000 ms (über 30 Minuten) benötigt.
• Für $N$ = 100 000: Algorithmus A benötigt 10 000 000 ms (ca. 116 Tage), während Algorithmus B 20 000 000 000 ms (ca. 634 Jahre) benötigt.

Dieses Beispiel verdeutlicht, warum wir uns in der Algorithmenanalyse vor allem für das asymptotische Verhalten interessieren – also wie sich die Laufzeit oder der Speicherbedarf für sehr große Eingabemengen verhält. Ein Algorithmus, der für kleine Datenmengen optimal erscheint, kann für größere Datenmengen völlig unpraktikabel werden.

Im nächsten Abschnitt werden wir sehen, wie wir dieses Skalierungsverhalten mit Hilfe der asymptotischen Notation formal beschreiben können.

2.2 Grundlagen der asymptotischen Notation¶

2.2.1 Die Idee hinter der Analyse von Skalierung und Asymptotik¶

Um zu verstehen, warum wir so etwas wie eine asymptotische Notation überhaupt verwenden, müssen wir zunächst das Konzept der Skalierung betrachten. In der Praxis interessiert uns eigentlich meistens nicht, wie ein Algorithmus für eine spezifische Eingabegröße abschneidet, sondern wie sich seine Leistung verändert, wenn die Eingabegröße wächst.

Wenn man z.B. aus $N$ Datenpunkten $2 N$ Datenpunkte macht, was passiert dann? Und was passiert bei $1000 N$ Datenpunkten? Darum geht es hier. Wenn man so etwas weiß, kann man abgesehen von der Asymptotik auch ganz schnell einfache Laufzeit- und Speicherbedarf-Abschätzungen für den verwendeten Code machen.

Die asymptotische Analyse konzentriert sich zunächst auf das Verhalten von Funktionen, wenn die Eingabe unbegrenzt wächst. Mit anderen Worten: Wir betrachten das Verhalten, wenn $N\rightarrow\infty$. Dabei ignorieren wir konstante Faktoren und niedrigere Terme, da diese für sehr große Eingaben vernachlässigbar werden.

Warum ignorieren wir Konstanten?

Stellen Sie sich vor, wir haben zwei Algorithmen:

• Algorithmus A mit Laufzeit 5$N$
• Algorithmus B mit Laufzeit 2$N$ + 3000

Für kleine Werte von $N$ ($N$ < 1000) ist Algorithmus A schneller. Aber sobald $N$ viel größer wird, wird der konstante Term 3000 im Vergleich zum Term 2$N$ immer unbedeutender. Für sehr große $N$ ist Algorithmus B im Prinzip effizienter, da 2$N$ langsamer wächst als 5$N$.

In der asymptotischen Analyse würden wir aber beide als $O(N)$ betrachten, also linear wachsend, und der eigentliche Unterschied liegt im jeweiligen Faktor (5 vs. 2), der für theoretische Überlegungen allerdings oft weniger relevant ist als das grundlegende Wachstumsverhalten. Das ist wieder unmittelbar bei einem Vergleich von z.B. $N$ und 10 $N$ einsichtig: Beide Varianten brauchen im Vergleich 10-mal so viel Ressourcen, unabhängig vom Faktor.

Lassen Sie uns das kurz illustrieren:

2.2.2 Die Big-O-Notation für die Asymptotik einer Funktion¶

Die Big-O-Notation ist die gebräuchlichste Methode, um die obere Schranke der Laufzeit oder des Speicherbedarfs eines Algorithmus auf einfache Weise zu beschreiben. Dabei schreibt man z.B. $O(N)$ um auszudrücken, dass die Funktion für $N\rightarrow\infty$ wie $N$ ansteigt. Die Bedeutung dieser Schreibweise ist vor allem, dass – in diesem konkreten Beispiel – im Limes gegen unendlich der am stärksten ansteigende Term linear ($N$) ist. Man schreibt in die Klammer also immer den dominanten Term im jeweiligen Grenzfall auf.

Beispiel: Die Funktion $f(N) = 3N^2 + 2N + 1$ ist $O(N^2)$, denn der quadratische Term dominiert für große $N$. Die folgende Grafik veranschaulicht dieses Konzept. Dabei wird eine zweite Funktion $g(N)$ angenommen, die im asymptotischen Fall die Funktion von oben begrenzt. Die Achsen sind in diesem Fall logarithmisch, damit man besser sieht, wie beide Funktionen asymptotisch parallel laufen.

Damit haben wir nun das grundlegende Verständnis für die Notation verschiedener Arten der Zeitkomplexität:

Einige Arten von Zeitkomplexität in dieser Notation (von effizient zu ineffizient):

• $O(1)$: Konstante Zeit als Funktion von $N$ (z.B. Berechnung von $(-1)^N$)
• $O(log N)$: Logarithmische Zeit (z.B. Binäre Suche – finden der Position eines bestimmten Werts in einem sortierten Array der Länge $N$)
• $O(N)$: Lineare Zeit (z.B. finden des Maximums eines unsortierten Arrays der Länge $N$)
• $O(N \log^k N)$: Quasilineare Zeit, $k$ ist eine positive Konstante (z.B. verschiedene Sortierungsalgorithmen von Arrays der Länge $N$)
• $O(N^2)$: Quadratische Zeit (z.B. weitere Sortierungsalgorithmen)
• $O(N^3)$: Kubische Zeit (z.B. normale Multiplikation von zwei $N\times N$-Matrizen)
• $O(poly(N))$: Polynomiale Zeit (z.B. lineare Optimierung)
• $2^{O(poly(N))}$: Exponentielle Zeit, der allgemeine Exponent ist im Prinzip auch hier ein Polynom in $N$ (z.B. brute-force Analyse der Matrix-Ketten-Multiplikation für $N$ Matrizen)
• $2^{O(N \log N)}$: Faktorielle Zeit, das entspricht der Asymptotik von $N!$ (z.B. brute-force Lösung des Traveling-Salesman-Problems für $N$ Orte)

Sie müssen sich hier nicht unbedingt die einzelnen Beispiele merken, aber Sie sollten diese Arten von Zeitkomplexität kennen und ein paar davon im Gedächtnis behalten.

2.2.3 Best-Case, Average-Case und Worst-Case-Analyse¶

Grundsätzlich unterscheidet man bei der Analyse von Algorithmen verschiedene Szenarien, die ich hier nur kurz und der Vollständigkeit halber erwähne:

Best-Case:

• Das günstigste Szenario für den Algorithmus.
• Beispiel: Bei der linearen Suche ist der Best-Case, wenn das gesuchte Element an erster Stelle steht ($O(1)$).
• In der Praxis ist das aber selten relevant, da man nicht davon ausgehen kann, dass das gesuchte Element tatsächlich immer an der ersten Stelle steht.

Average-Case:

• Die durchschnittliche Leistung über alle möglichen Eingaben.
• Da hier ein echtes Durchprobieren auch schon einer brute-force-Lösung gleichkommt, basieren diese Einschätzungen oft auf probabilistischen Annahmen.
• Beispiel: Bei der linearen Suche ist der Average-Case, dass man im Durchschnitt die Hälfte der Elemente durchsuchen muss ($O(N/2) = O(N)$).

Worst-Case:

• Das ungünstigste Szenario für den Algorithmus, und für uns das interessanteste.
• Beispiel: Bei der linearen Suche ist der Worst-Case, wenn das gesuchte Element an der letzter Stelle steht, an der man sucht, oder nicht vorhanden ist ($O(N)$).
• In der Praxis ist das vor allem deshalb am relevantesten, da dieser Fall eine Art Garantie für eine gute Abschätzung der maximalen Ressourcennutzung gibt.

In den meisten Fällen konzentrieren wir uns also auf die Worst-Case-Analyse, da sie eine obere Schranke für die Leistung des Algorithmus garantiert. Die Average-Case-Analysen kann in einigen speziellen Fällen, insbesondere bei randomisierten Algorithmen, ebenfalls interessant sein.

2.3 Kurze Einführung in die Zeitkomplexität¶

2.3.1 Bestimmung der dominanten Terme für den Zeitbedarf eines Algorithmus¶

Um die Zeitkomplexität eines Algorithmus zu bestimmen, muss man also die dominanten Terme identifizieren, die das Wachstumsverhalten bestimmen. Im Allgemeinen gehen Sie dabei wie folgt vor:

1. Identifizieren Sie die grundlegenden Operationen im Algorithmus (z.B. Vergleiche, arithmetische Operationen).
2. Zählen Sie, wie oft diese Operationen ausgeführt werden, abhängig von der Eingabegröße $N$.
3. Drücken Sie die Gesamtanzahl der Operationen als Funktion von $N$ aus.
4. Behalten Sie nur den Term mit dem höchsten Wachstum (also den dominanten Term) und ignorieren Sie Konstanten.

Ein Beispiel dafür, den dominanten Term in einem Polynom zu finden, haben wir bereits weiter oben gesehen. Im Folgenden betrachten wir nun ein paar typische Algorithmen-Strukturen.

2.3.2 Analyse von Schleifen und verschachtelten Schleifen¶

Schleifen sind oft die Hauptursache für die Zeitkomplexität eines Algorithmus. Zugleich sind sie außerdem recht geradlinig und direkt einzuschätzen. Hier folgen die wichtigsten Beispiele, als Python-Snippets dargestellt von Claude 3.7 Sonnet:

Einfache Schleife:

for i in range(n):
    # Konstante Zeit Operation

Diese Schleife hat eine Zeitkomplexität von $O(N)$, da die innere Operation $N$-mal ausgeführt wird.

Verschachtelte Schleifen:

for i in range(n):
    for j in range(n):
        # Konstante Zeit Operation

Diese verschachtelten Schleifen haben eine Zeitkomplexität von $O(N^2)$, da die innere Operation $N \times N = N^2$ mal ausgeführt wird.

Verschachtelte Schleifen mit unterschiedlichen Grenzen:

for i in range(n):
    for j in range(i):
        # Konstante Zeit Operation

In diesem Fall wird die innere Schleife 0 + 1 + 2 + … + $(N-1) = N(N-1)/2$ mal durchlaufen, was ebenfalls zu einer Zeitkomplexität von $O(N^2)$ führt.

Logarithmische Schleifen:

i = 1
while i < n:
    # Konstante Zeit Operation
    i = i * 2

Hier verdoppelt sich $i$ in jedem Schritt, sodass die Schleife $\log_2(N)$ mal durchlaufen wird, was zu einer Zeitkomplexität von $O(\log N)$ führt.

2.3.3 Visualisierung verschiedener Zeitkomplexitäten¶

Die obige Visualisierung zeigt deutlich, wie unterschiedlich diese Arten der Zeitkomplexität skalieren. Während Algorithmen mit konstanter, logarithmischer oder linearer Laufzeit auch für große Eingaben praktikabel bleiben, werden Algorithmen mit quadratischer, kubischer oder gar exponentieller Laufzeit schnell unpraktikabel.

2.3.5 Einfache Beispiele für solche Arten von Zeitkomplexität¶

Lassen Sie uns für jede Zeitkomplexität ein konkretes Beispiel betrachten. Sie finden hier jeweils kurze Programm-Vorschläge von Claude 3.7 Sonnet:

$O(1)$ – Konstante Zeit:

def get_first_element(array):
    """Gibt das erste Element eines Arrays zurück."""
    if len(array) > 0:
        return array[0]
    else:
        return None

Die Laufzeit ist unabhängig von der Größe des Arrays, da wir immer nur auf das erste Element zugreifen.

$O(\log N)$ – Logarithmische Zeit:

def binary_search(sorted_array, target):
    """Binäre Suche nach einem Element in einem sortierten Array."""
    left, right = 0, len(sorted_array) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if sorted_array[mid] == target:
            return mid
        elif sorted_array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # Element nicht gefunden

Bei jedem Schritt halbieren wir den Suchbereich, was zu einer logarithmischen Laufzeit führt.

$O(N)$ – Lineare Zeit:

def linear_search(array, target):
    """Lineare Suche nach einem Element in einem Array."""
    for i, element in enumerate(array):
        if element == target:
            return i
    return -1  # Element nicht gefunden

Im schlimmsten Fall müssen wir das gesamte Array durchlaufen, was zu einer linearen Laufzeit führt.

$O(N \log N)$ – Quasilineare Zeit:

def merge_sort(array):
    """Sortiert ein Array mit dem Mergesort-Algorithmus."""
    if len(array) <= 1:
        return array
        
    # Teilen
    mid = len(array) // 2
    left_half = merge_sort(array[:mid])
    right_half = merge_sort(array[mid:])
    
    # Zusammenführen
    return merge(left_half, right_half)

def merge(left, right):
    """Führt zwei sortierte Arrays zusammen."""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Mergesort teilt das Array rekursiv in Hälften ($O(\log N)$ Ebenen) und führt auf jeder Ebene $O(N)$ Arbeit durch, was zu einer Gesamtkomplexität von $O(N \log N)$ führt.

$O(N^2)$ – Quadratische Zeit:

def bubble_sort(array):
    """Sortiert ein Array mit dem Bubblesort-Algorithmus."""
    n = len(array)
    for i in range(n):
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

Bubblesort verwendet zwei verschachtelte Schleifen, was zu einer quadratischen Laufzeit führt.

$O(N^3)$ – Kubische Zeit:

def naive_matrix_multiply(A, B):
    """Multipliziert zwei n×n-Matrizen A und B mit dem naiven Algorithmus."""
    n = len(A)
    C = [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
                
    return C

Die naive Matrixmultiplikation verwendet drei verschachtelte Schleifen, was zu einer kubischen Laufzeit führt.

$O(2^N)$ – Exponentielle Zeit:

def fibonacci_recursive(n):
    """Berechnet die n-te Fibonacci-Zahl rekursiv."""
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

Diese naive rekursive Implementation der Fibonacci-Folge hat eine exponentielle Laufzeit, da jeder Aufruf zu zwei weiteren Aufrufen führt (ohne Memoization).

$O(N!)$ – Faktorielle Zeit:

def generate_all_permutations(elements):
    """Generiert alle Permutationen einer Liste von Elementen."""
    if len(elements) <= 1:
        return [elements]
    
    all_permutations = []
    for i in range(len(elements)):
        # Wähle ein Element als erstes Element
        current = elements[i]
        # Erstelle Liste der verbleibenden Elemente
        remaining = elements[:i] + elements[i+1:]
        
        # Generiere alle Permutationen der verbleibenden Elemente
        for p in generate_all_permutations(remaining):
            # Füge das aktuelle Element am Anfang hinzu
            all_permutations.append([current] + p)
            
    return all_permutations

Für jedes der n Elemente generieren wir alle Permutationen der verbleibenden n-1 Elemente, was zu einer faktoriellen Laufzeit führt.

2.4 Kurze Einführung in die Speicherkomplexität¶

Während die Zeitkomplexität angibt, wie lange ein Algorithmus benötigt, beschreibt die Speicherkomplexität, wie viel Speicherplatz er während der Ausführung in Anspruch nimmt. Dein Einfluss von oder Probleme mit der Speicherkomplexität merkt man beim Behandeln von einfachen Beispielen oder Aufgaben meist überhaupt nicht. Das liegt daran, dass moderne Computer für egal welche Implementierung einfacher Problemstellungen jedenfalls genügend Arbeitsspeicher haben, um mit der Ausführung des Programms ohne weiteres klarzukommen.

Während man zunächst also nicht über Speicher nachdenkt, geht einem eine längere Laufzeit viel eher auf die Nerven, und man beginnt, über Laufzeitoptimierung nachzudenken. Dabei kommt es dann allerdings recht schnell zu einer Verlagerung von wiederholten Ausführungen bestimmter Operationen zum Speichern und wieder-Abrufen bereits berechneter Resultate, was den Speicherbedarf erhöht. Ein anderer Grund für Speicherbedarf ist die Verwendung optimierter Programmbibliotheken wie z.B. Numpy, die bereits auf Laufzeit optimierte Funktionen und Klassen zur Verfügung stellen, die dann aber auch erhöhten Speicherbedarf haben.

Sehen wir uns nun also auch den benötigten Speicher genauer an. Wir verwenden wieder die Big-O-Notation zur Beschreibung.

2.4.1 Analyse des Speicherbedarfs eines Algorithmus¶

Bei der Analyse des Speicherbedarfs berücksichtigen wir:

1. Eingabegröße: Wie viel Speicher wird für die Eingabedaten benötigt?
2. Hilfsvariablen: Welche zusätzlichen Datenstrukturen werden während der Ausführung verwendet?
3. Rekursionstiefe: Bei rekursiven Algorithmen müssen wir den Stapelspeicher (Stack) berücksichtigen.

Betrachten wir einige Beispiele (nochmals), wieder gecodet von Claude 3.7 Sonnet:

Beispiel 1: In-Place-Sortieralgorithmus (Bubble Sort)

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

Bubble Sort verändert das Array direkt (in-place) und benötigt nur konstanten zusätzlichen Speicher für die Schleifenvariablen und den temporären Austausch. Die Speicherkomplexität ist daher $O(1)$, wenn wir den Speicher für die Eingabe nicht berücksichtigen.

Beispiel 2: Merge Sort

def merge_sort(array):
    if len(array) <= 1:
        return array
        
    mid = len(array) // 2
    left_half = merge_sort(array[:mid])
    right_half = merge_sort(array[mid:])
    
    return merge(left_half, right_half)

Merge Sort erstellt bei jedem rekursiven Aufruf neue Teilarrays und benötigt zusätzlichen Speicher für die Zusammenführung. Die Speicherkomplexität ist $O(N)$, da wir im schlimmsten Fall $O(N)$ zusätzlichen Speicher benötigen. Durch die Rekursion hat Merge Sort auch eine Stapeltiefe von $O(\log N)$.

Beispiel 3: Erstellen einer Adjazenzmatrix für einen Graphen

def create_adjacency_matrix(n, edges):
    """
    Erstellt eine Adjazenzmatrix für einen Graphen mit n Knoten und den gegebenen Kanten.
    
    Args:
        n: Anzahl der Knoten im Graphen
        edges: Liste von Tupeln (u, v), die Kanten zwischen Knoten u und v darstellen
        
    Returns:
        Eine n x n Adjazenzmatrix
    """
    matrix = [[0 for _ in range(n)] for _ in range(n)]
    
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1  # Für einen ungerichteten Graphen
        
    return matrix

Die Adjazenzmatrix benötigt $O(N^2)$ Speicher, da wir eine $N\times N$-Matrix erstellen müssen, unabhängig von der Anzahl der Kanten.

2.4.2 Zusammenhang zwischen Zeit- und Speicherkomplexität¶

Zeit- und Speicherkomplexität sind oft, aber nicht immer, miteinander verbunden. Einige Beobachtungen:

1. Datenstrukturen beeinflussen beide Komplexitäten:

   • Eine geschickte Wahl der Datenstruktur kann sowohl die Zeit- als auch die Speicherkomplexität verbessern.
   • Beispiel: Hashtabellen bieten $O(1)$-Zeit Zugriff auf Kosten eines höheren Speicherbedarfs. Die konstante Zeitkomplexität ergibt sich aus der konstanten Zeit, in der die Hash-Funktion aus der Eingabe jenen Index erzeugt, unter dem die gesuchte Information in einer Tabelle gespeichert ist. Auch der Index-gesteuerte Zugriff auf die Tabelle dauert $O(1)$. Der damit verbundene Speicherbedarf ist proportional zur Größe der Tabelle.

2. Vorberechnung und Zwischenspeicherung:

   • Durch das Speichern von Zwischenergebnissen (Memoisation) können wir die Zeitkomplexität auf Kosten der Speicherkomplexität reduzieren.
   • Beispiel: Beim nach-und-nach-Berechnen aller Primzahlen kann man als mögliche Faktoren anstatt aller Zahlen, die kleiner als die zu überprüfende Zahl sind, nur bereits gefundene Primzahlen in Betracht ziehen.

3. Rekursive vs. iterative Implementierungen:

   • Rekursive Algorithmen können eleganter sein, benötigen aber mehr Stapelspeicher.
   • Iterative Algorithmen haben eine bessere Speicherkomplexität.

2.4.3 Trade-offs zwischen Zeit und Speicher¶

In der Praxis müssen wir oft Kompromisse zwischen Zeit- und Speicherkomplexität eingehen. Hier sind zwei typische Beispiele, gecodet von Claude 3.7 Sonnet:

Beispiel 1: Fibonacci-Zahlen

In der Folge der Fibonacci-Zahlen erhält man die nächste Zahl, indem man die beiden vorangegangenen Zahlen addiert. Die Folge beginnt mit 1, 1, 2, 3, 5, … Hier sehen wir uns drei verschiedene Ansätze an, um diese Zahlen zu berechnen.

Rekursive Implementierung (schlechte Zeit, guter Speicher):

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

• Zeitkomplexität: $O(2^N)$ (exponentiell):

  • Für jede Berechnung von fibonacci_recursive(n) werden zwei weitere rekursive Aufrufe getätigt (n-1 und n-2)
  • Dies führt zu einem rekursiven Aufrufbaum mit annähernd $2^N$ Knoten
  • Das exponentielle Wachstum wird also durch viele redundante Berechnungen verursacht (z.B. wird fibonacci_recursive(3) mehrfach berechnet)

• Speicherkomplexität: $O(N)$ (für den Rekursionsstack):

  • Die maximale Tiefe der Rekursion beträgt $N$, da wir immer bis zu fibonacci_recursive(0) heruntersteigen
  • Dabei wird der gesamte Baum der nötigen Berechnungen in der Rekursion der Reihe nach abgearbeitet, allerdings immer eine Verzweigung bis ganz zum Ende (fibonacci_recursive(0))
  • Daher bleibt die Speicherkomplexität linear mit $O(N)$, weil der längste Verzweigungspfad die Länge $N$ hat.

Dynamische Programmierung mit Memoisation (gute Zeit, mittlerer Speicher):

def fibonacci_memoized(n, memo=None):
    if memo is None:
        memo = {}  # benützt ein Dictionary
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    return memo[n]

• Zeitkomplexität: $O(N)$:

  • Jede Fibonacci-Zahl von 0 bis $N$ wird exakt einmal berechnet und im memo-Dictionary gespeichert
  • Alle nachfolgenden Anfragen für diesen Wert werden einfach aus dem Dictionary abgerufen (das sind jeweils $O(1)$ Operation)
  • Die Berechnung jeder Fibonacci-Zahl erfordert eine konstante Anzahl von Operationen plus zwei Rekursionsaufrufe
  • Da jeder rekursive Aufruf für einen bestimmten Wert von $N$ durch die Memoization nur einmal tatsächlich ausgeführt wird, beträgt die Gesamtzahl der Operationen $O(N)$

• Speicherkomplexität: $O(N)$:

  • Das memo-Dictionary speichert bis zu $N+1$ Schlüssel-Wert-Paare (für alle Fibonacci-Zahlen von 0 bis $N$)
  • Durch die Rekursion muss man im schlimmsten Fall immer noch bis zu $N$ Schritte tief gehen
  • Daher ist die Gesamtspeicherkomplexität $O(N)$ für die Memoisation plus $O(N)$ für den Rekursionspfad, insgesamt also $O(N)$

Dynamische Programmierung mit Tabulation (gute Zeit, guter Speicher):

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

• Zeitkomplexität: $O(N)$:

  • Der Algorithmus verwendet eine einzelne Schleife, die $N-1$ mal durchlaufen wird (von 2 bis $N$)
  • Jede Iteration führt eine konstante Anzahl von Operationen durch (Zuweisung und Addition)
  • Daher beträgt die Gesamtzeitkomplexität $O(N)$

• Speicherkomplexität: $O(1)$:

  • Unabhängig von der Größe von $N$ werden nur zwei Variablen (a und b) verwendet, um die letzten beiden Fibonacci-Zahlen zu speichern
  • Es gibt keinen Rekursionspfad und keine Datenstruktur, die mit $N$ wächst, obwohl man auch hier alle in der Schleife berechneten Zahlen speichern könnte. Die Tabelle hätte dann die Länge $N$, wobei sie in dieser optimierten Implementierung nur die Länge 2 hat (a und b).
  • Daher bleibt der Speicherbedarf konstant bei $O(1)$
  • Dies macht diesen Ansatz besonders speichereffizient für große Werte von $N$

Beispiel 2: Suchalgorithmen

Die Suche nach einem bestimmten Element in einer Menge oder in einer ähnlichen Datenstruktur ist eins der zentralen Probleme in der Informatik. Daher tauchen Suchalgorithmen immer wieder als Beispiele auf, nicht zuletzt deshalb, weils sie im Laufe der Zeit sehr gründlich untersucht und optimiert worden sind. Hier noch eine kurze Gegenüberstellung zweier typischer Varianten, gecodet von Claude 3.7 Sonnet.

Lineare Suche (schlechte Zeit, kein zusätzlicher Speicher):

def linear_search(array, target):
    for i, element in enumerate(array):
        if element == target:
            return i
    return -1

• Zeitkomplexität: $O(N)$:

  • Im schlimmsten Fall müssen wir jeden einzelnen Eintrag im Array überprüfen, bis wir das Zielelement finden oder das Ende des Arrays erreichen
  • Die Anzahl der Vergleiche ist direkt proportional zur Größe des Arrays ($N$)
  • Durchschnittlich müssen wir $N/2$ Elemente überprüfen, wenn das gesuchte Element zufällig im Array verteilt ist
  • Im besten Fall (Element ist am Anfang) benötigen wir nur einen Vergleich: $O(1)$
  • Da wir bei der Big-O-Notation den schlimmsten Fall betrachten, ist die Zeitkomplexität $O(N)$

• Speicherkomplexität: $O(1)$:

  • Wir benötigen nur konstanten zusätzlichen Speicher unabhängig von der Eingabegröße
  • Es werden nur die Laufvariablen i und element während der Iteration verwendet
  • Keine zusätzlichen Datenstrukturen werden erstellt oder erweitert
  • Der Speicherverbrauch – abgesehen vom Array selbst – bleibt konstant, egal wie groß das Array ist

Hashmap-basierte Suche (hervorragende Zeit, zusätzlicher Speicher):

def hashmap_search(array, target):
    # Vorverarbeitung
    hashmap = {element: i for i, element in enumerate(array)}
    
    # Suche
    if target in hashmap:
        return hashmap[target]
    else:
        return -1

• Zeitkomplexität: $O(1)$ für die Suche (nach $O(N)$ Vorverarbeitung):

  • Die Vorverarbeitung erfordert $O(N)$ Zeit, da wir jedes Element im Array durchlaufen müssen, um die Hashmap zu erstellen
  • Die Dictionary-Comprehension {element: i for i, element in enumerate(array)} benötigt $N$ Operationen
  • Das Einfügen in die Hashmap hat eine durchschnittliche Zeitkomplexität von $O(1)$ pro Element
  • Die anschließende Suche nach dem target-Element in der Hashmap ist eine $O(1)$-Operation im Durchschnittsfall
  • Der Ausdruck target in hashmap nutzt den Hash-Wert des Zielobjekts, um direkt auf den entsprechenden Index in der Hashmap zuzugreifen

• Speicherkomplexität: $O(N)$:

• Wir erstellen eine Hashmap, die jeden Wert aus dem ursprünglichen Array als Schlüssel enthält

  • Die Hashmap speichert $N$ Schlüssel-Wert-Paare (jedes Element und seinen Index)
  • Der Speicherverbrauch wächst linear mit der Größe des Eingabe-Arrays
  • In Python-Dictionaries wird etwas zusätzlicher Speicher für die Hash-Tabellen-Infrastruktur benötigt

Diese Beispiele zeigen, dass wir oft zwischen Zeit und Speicher abwägen müssen. Die optimale Wahl hängt von den spezifischen Anforderungen der Anwendung ab:

• In speicherbeschränkten Umgebungen (z.B. eingebettete Systeme) können wir Zeit für Speicher opfern.
• In Anwendungen, die schnell reagieren müssen (z.B. Echtzeitsysteme), können wir Speicher für Zeit opfern.
• In Anwendungen mit sehr großen Datenmengen müssen wir möglicherweise beides optimieren.

2.5 Benchmarking und empirische Analyse¶

Die theoretische Komplexitätsanalyse ist ein mächtiges Werkzeug, um das asymptotische Verhalten von Algorithmen zu verstehen. In der Praxis ist es allerdings wesentlich wichtiger, die tatsächliche Laufzeit und den Speicherbedarf der Algorithmen einfach zu messen. Dafür verwenden wir verschiedene Benchmarking-Techniken.

2.5.1 Laufzeitmessung in Python¶

Python bietet verschiedene Möglichkeiten zur Laufzeitmessung, hier sind Beispiel-Code-Snippets von Claude 3.7 Sonnet:

1. Das time-Modul für einfache Zeitmessungen:

import time

start_time = time.time()
# Code, dessen Laufzeit gemessen werden soll
result = some_algorithm(data)
end_time = time.time()

print(f"Laufzeit: {end_time - start_time:.6f} Sekunden")

2. Das timeit-Modul für präzisere Messungen:

import timeit

# Code wird als String vorbereitet
code_to_measure = """
result = some_algorithm(data)
"""

# Setup-Code (wird nachher ausgeführt, aber nicht gemessen), ein extra String
setup_code = """
from my_module import some_algorithm
data = [i for i in range(1000)]
"""

# Führe den Code mehrmals aus und nimm den Durchschnitt
execution_time = timeit.timeit(code_to_measure, setup=setup_code, number=100)
print(f"Durchschnittliche Laufzeit über 100 Durchläufe: {execution_time / 100:.6f} Sekunden")

3. Das cProfile-Modul für detaillierte Profiling-Informationen:

import cProfile

# Profiling eines Funktionsaufrufs
cProfile.run('some_algorithm(data)')

4. Zeitdekoratoren für wiederholte Messungen:

Die vorangegangenen Code-Beispiele demonstrieren, wie wir die Laufzeit von Algorithmen in Python messen und können. Diese empirischen Messungen sind ein wichtiger Bestandteil der Algorithmenanalyse, denn sie ermöglichen es uns, die theoretischen Vorhersagen der asymptotischen Analyse zu überprüfen und zu validieren.

2.5.2 Visualisierung empirischer Performancedaten¶

Die Visualisierung von Performancedaten hilft dabei, ganz einfach Trends und Muster in den Laufzeiten zu erkennen. In den Code-Beispielen haben wir verschiedene Sortieralgorithmen theoretisch verglichen; jetzt ist es Zeit, konkrete Laufzeiten in Abhängigkeit von der Eingabegröße zu visualisieren. Dabei achten wir auf folgende Aspekte:

• Das tatsächliche Wachstumsverhalten eines Algorithmus
• Algorithmen miteinander zu vergleichen
• Schwellenwerte zu identifizieren, ab denen ein Algorithmus einem anderen überlegen ist
• Unerwartete Effekte und Fluktuationen, die eine genauere Untersuchung nahelegen

Typische Visualisierungen in der Algorithmenanalyse sind z.B.

1. Liniendiagramme: Sehen wir gleich. Sie zeigen die Laufzeit oder den Speicherbedarf in Abhängigkeit von der Eingabegröße
2. Log-Log-Plots: Sehen wir auch gleich. Besonders nützlich für die Visualisierung von Potenzgesetzen (z.B. $O(N^2)$ entspricht im Log-Log-Plot einer Geraden mit Steigung 2) und asymptotischem Verhalten
3. Heatmaps: Eine Art, mehrdimensionale Plots zu erzeugen. Nützlich zum Vergleich mehrerer Algorithmen über verschiedene Eingabegrößen oder Datenverteilungen

2.5.3 Vergleich theoretischer und praktischer Performance¶

Die theoretische Analyse gibt uns Einblick in das asymptotische Verhalten eines Algorithmus, aber in der Praxis können andere Faktoren eine wichtige Rolle spielen. Wie schon angedeutet, kann es sein, dass man z.B. in den Messergebnissen irgendwelche unerwarteten oder seltsamen Dinge sieht. Andererseits gibt es auch vorhersehbare Faktoren, die Unterschiede von erwarteten zu tatsächlichen Werten verursachen. Hier folgt eine Liste der typischen Dinge, die man im Kopf behalten sollte:

1. Konstante Faktoren: In der Big-O-Notation ignorieren wir konstante Faktoren, aber in der Praxis können sie einen erheblichen Unterschied machen.

   • Beispiel: So einen Unterschied haben wir bereits ganz am Anfang gesehen, wo zwei linear skalierende Zeit-Abhängigkeiten sehr verschieden waren.

2. Overhead: Die theoretische Analyse berücksichtigt oft nicht den Overhead für die Initialisierung von Datenstrukturen oder für Funktionsaufrufe.

   • Beispiel: Rekursive Implementierungen haben durch den Funktionsaufruf-Overhead oft eine schlechtere praktische Performance als ihre iterativen Gegenstücke.

3. Cacheverhalten: Moderne CPUs verwenden Caches, um häufig genutzte Daten schnell verfügbar zu haben. Algorithmen, die eine gute Cache-Nutzung aufweisen, können in der Praxis viel schneller sein.

   • Beispiel: Arrays (Stichwort Numpy) bieten bessere Cache-Nutzung als verknüpfte Listen, was zu besserer Performance führen kann, selbst wenn die theoretische Komplexität gleich ist.

4. Optimierungen durch den Compiler/Interpreter: Moderne Compiler und Interpreter führen viele Optimierungen durch, die das Laufzeitverhalten verbessern können.

   • Beispiel: Pythons Timsort-Algorithmus passt sich an Muster in den Daten an und kann in bestimmten Fällen besser abschneiden als seine theoretische $O(N \log N)$ Komplexität vermuten lässt.

2.5.4 Verschiedene Implementierungen desselben Algorithmus¶

Oft gibt es mehrere Möglichkeiten, einen Algorithmus zu implementieren, und diese können sich erheblich in ihrer Performance unterscheiden. In der Praxis geht man oft nach dem Prinzip des “Rapid Prototypings” vor, indem man zunächst einfach irgendeine Implementierung des Algorithmus programmiert – die Hauptsache dabei ist, dass das Programm korrekt läuft und das Problem im Prinzip gelöst wird. Erst danach geht man Schritt für Schritt durch mögliche Optimierungen und verbessert die Performance durch bessere Implementierungen immer weiter.

Hier sind die wichtigsten Aspekte solch verschiedener Implementierungen:

1. Rekursiv vs. Iterativ: Rekursive Implementierungen sind oft eleganter und leichter zu verstehen, während iterative Implementierungen effizienter sein können.

2. Verschiedene Datenstrukturen: Die Wahl der Datenstruktur kann einen erheblichen Einfluss auf die Performance haben.

3. Inplace vs. Out-of-place: Algorithmen, die ihre Eingabe direkt modifizieren (inplace), benötigen oft weniger Speicher, können aber in manchen Situationen auch weniger flexibel sein.

4. Andere Herangehensweise: Manchmal hat eine neue Implementierung eines Algorithmus eine komplett neue und bessere Herangehensweise an das Problem als Grundlage. Praktisch für jedes Problem kann man sich z.B. eine brute-force Lösungsstrategie ausdenken. In der Praxis ist das aber von vornherein auch die am wenigsten optimierte Variante für einen Lösungsalgorithmus, und eine gute Idee kann eine Lösung (oder zumindest eine Näherungslösung, dazu gleich noch mehr) in greifbare Nähe rücken.

2.5.5 Optimierung von Code mithilfe von Komplexitätsanalyse¶

Die Komplexitätsanalyse kann natürlich auch dabei helfen, Engpässe im verwendeten Code zu identifizieren und zu optimieren, zum Beispiel:

1. Identifizierung von Bottlenecks: Durch die Analyse der Komplexität verschiedener Teile eines Algorithmus können wir die teuersten Operationen identifizieren. Diese werden “Bottlenecks”, also “Flaschenhals” genannt, weil sie diejenigen Teile des Programms sind, die den Datendurchsatz am stärktsten bremsen.

2. Algorithmische Verbesserungen: Wenn sich herausstellt, dass Teile des Codes auf ineffiziente Weise umgesetzt sind, dann kann man natürlich solche Blöcke durch effizientere Versionen ersetzen.

3. Datenstruktur-Optimierungen: Das gleiche gilt für die verwendeten Datenstrukturen. Wenn es auf Optimierung ankommt, dann lohnt es sich, die verwendeten Datenstrukturen der Reihe nach in Frage zu stellen und gegebenenfalls zu ersetzen.

4. Speicher-Zeit-Tradeoffs: Je nach Situation und verewendeter Hardware sollte man die Möglichkeit im Hinterkopf behalten, die Optimierung von Laufzeit auf Speicher zu verlagern oder umgekehrt.

2.5.6 Approximationsalgorithmen für schwierige Probleme¶

Zum Schluss möchte ich noch auf eine mir sehr wichtige Sache hinweisen: Gerade bei sehr schwierig zu Lösenden Problemen ist es in der Praxis unerlässlich, über seinen theoretischen Schatten zu springen und eine Näherungslösung statt der echten absolut besten Lösung zu suchen. Das Gute dabei ist, dass das sehr oft für die praktische Anwendung, um die es geht, völlig ausreichend ist.

Für einige Probleme sind gar keine effizienten Algorithmen bekannt, die eine exakte Lösung liefern. In solchen Fällen muss man de facto auf Näherungen zurückgreifen. Es ist auch interessant zu wissen, dass es bei sehr komplexen Problemen (z.B. dem Training von LLMs) sehr viele Lösungen gibt, die “beinahe optimal” sind, d.h. der tatsächlich optimalen Lösung fast beliebig nahe kommen. So eine beinahe optimale Lösung bereits zu finden ist oft viel einfacher als nach der tatsächlich optimalen Lösung überhaupt erst zu suchen.

Hier sind die wichtigsten Varianten im Überblick:

1. Approximationsalgorithmen: Diese Algorithmen finden eine Lösung, die garantiert innerhalb eines bestimmten Faktors vom Optimum liegt.

   • Beispiel: Für das Travelling Salesman Problem gibt es einen 2-Approximationsalgorithmus, der eine Tour findet, die höchstens doppelt so lang ist wie die optimale Tour.

2. Heuristiken: Diese Algorithmen finden oft gute Lösungen, bieten aber keine formalen Garantien für die Qualität der Lösung.

   • Beispiel: Genetische Algorithmen oder Simulated Annealing können gute Lösungen für Optimierungsprobleme finden, garantieren aber nicht, dass das globale Optimum gefunden wird.

3. Randomisierte Algorithmen: Diese Algorithmen treffen zufällige Entscheidungen und können mit hoher Wahrscheinlichkeit gute Lösungen finden.

   • Beispiel: Der Randomized Quicksort wählt das Pivotelement (an dem die zu sortierende Liste rekursiv geteilt wird) zufällig, was zu einer erwarteten Laufzeit von $O(N \log N)$ führt.

Die empirische Analyse solcher Algorithmen ist besonders wichtig, da ihre theoretischen Garantien oft nur Worst-Case-Szenarien abdecken, während sie in der Praxis oft viel besser abschneiden.

2.6 Übungsaufgabe: Möglichkeiten für die Berechnung von Pi¶

Da wir diese Woche “Pi-day” feiern (den 14.3., also 03/14), ist es unsere moralische Pflicht, verschiedene Möglichkeiten zur Berechnung dieser berühmten Zahl zu erkunden. Sie können das ganz für sich oder in Zusammenarbeit mit dem LLM Ihrer Wahl tun. Ich schlage folgende Schritte vor:

• Diskutieren/Erfahren Sie, welche Verfahren man verwenden kann, um Pi zu berechnen
• Wählen Sie davon zwei Verfahren aus, die Sie interessant finden
• Implementieren Sie beide (jeweils separat) in Python
• Testen Sie die Effizienz Ihrer beiden Implementationen in Abhängigkeit von der Anzahl der gewünschten Nachkommastellen von Pi als Eingabegröße
• Visualisieren Sie Ihre Testergebnisse
• Interpretieren Sie die Resultate und Visualisierung. Was stellen Sie fest?

Viel Vergnügen!

2.7 Zusammenfassung der wichtigsten Punkte dieser Einheit¶

In dieser Einheit haben wir uns mit einem der fundamentalsten Konzepte der Informatik beschäftigt: der Analyse von Algorithmen und ihrer Komplexität. Wir haben gelernt, wie wir die Effizienz eines Algorithmus sowohl theoretisch als auch empirisch, also in der Praxis, testen und bewerten können.

Was wir diesmal diskutiert haben, ist in erster Linie grundlegend für die Beschäftigung mit Algorithmen per se. Ich möchte diese Denkansätze und Inhalte aber insbesondere als Horizont-Erweiterung für Sie verstanden wissen. Das bedeutet, Sie sollten nicht komplett plan- und ahnungslos sein, wenn es um die theoretische Komplexitätsanalyse von Algorithmen und deren Implementierungen geht. Das ist allerdings nicht das Hauptthema bei der Beschäftigung mit Algorithmen in unserer Lehrveranstaltung, sondern es geht mir hauptsächlich darum, wie Sie in Zukunft konkrete Probleme mit Computerunterstützung lösen können.

Daher nehmen Sie bitte vor allem die folgenden Dinge aus dieser Einheit mit:

1. Die Bedeutung der Algorithmenanalyse

   • Effiziente Algorithmen sparen Ressourcen (Zeit, Speicher, Energie, Nerven)
   • Mit den wachsenden Datenmengen unserer Zeit wird diese Effizienz immer wichtiger
   • Die Algorithmenanalyse hilft uns, fundierte Entscheidungen bei der Auswahl von Algorithmen zu treffen, aber auch dabei, Schwachstellen zu finden und auszumerzen/zu optimieren

2. Asymptotische Notation

   • Die Big-O-Notation beschreibt eine obere Schranke für das Wachstum eines Algorithmus bei wachsender Eingabegröße
   • Wir konzentrieren uns auf das Verhalten für große Eingabegrößen und ignorieren konstante Faktoren und nicht-dominante Terme
   • Diese Notation erlaubt es, im betrachteten Grenzfall verschiedene Algorithmen und deren Implementationen einfach zu vergleichen

3. Zeitkomplexität

   • Hier gibt es verschiedenste Verhalten, die wir uns beispielhaft angesehen haben
   • Merken Sie sich ein paar der genannten Fälle, z.B. $O(1)$ , $O(\log N)$, $O(N)$, etc., sowie die dazu gehörenden Bezeichnungen
   • Besonders wichtig für die Bestimmung der Zeitkomplexität ist die Analyse von Schleifen und rekursiven Aufrufen

4. Speicherkomplexität

   • Die zentrale Frage lautet: Wie viel zusätzlichen Speicher (zusätzlich zur Eingabegröße) benötigt ein Algorithmus?
   • Oft gibt es Trade-offs zwischen Zeit- und Speicherkomplexität
   • Wir verwenden die gleichen Komplexitäts-Bezeichnungen wie bei der Zeitkomplexität
   • Z.B. In-Place-Algorithmen oder clevere Konstrukte minimieren den zusätzlichen Speicherbedarf

5. Empirische Analyse

   • Die tatsächliche Leistung kann durch Faktoren beeinflusst werden, die in der theoretischen Analyse nicht berücksichtigt werden
   • Benchmarking und Visualisierung helfen, die praktische Leistung zu verstehen
   • Theoretische und empirische Analyse ergänzen sich also