Introduction to informatics for Students of Mathematics - Exam.pdf

Aufgabe 1)

Betrachte den folgenden Algorithmus in Python, der ein Array durchsucht und feststellt, ob ein bestimmtes Element darin enthalten ist:

def lineare_suche(arr, x):    for i in range(len(arr)):        if arr[i] == x:            return i    return -1

Analysiere die Komplexität dieses Algorithmus hinsichtlich der Zeit- und Speicherkomplexität.

a)

Teilaufgabe 1: Bestimme die Zeitkomplexität des Algorithmus im Worst-Case und erkläre, wie Du zu diesem Ergebnis kommst. Verwende dabei die Landau-Notation und gehe sowohl auf die Anzahl der Vergleiche als auch auf die Schleifenanzahl ein.

Lösung:

Teilaufgabe 1: Bestimme die Zeitkomplexität des Algorithmus im Worst-Case und erkläre, wie Du zu diesem Ergebnis kommst. Verwende dabei die Landau-Notation und gehe sowohl auf die Anzahl der Vergleiche als auch auf die Schleifenanzahl ein.

Um die Zeitkomplexität des gegebenen Algorithmus im Worst-Case zu bestimmen, analysieren wir sowohl die Anzahl der Vergleiche als auch die Anzahl der Schleifen.

• Der Algorithmus durchsucht ein Array arr der Länge n nach einem bestimmten Element x. Dies bedeutet, dass der Algorithmus jedes Element im Array einmal überprüfen muss.
• Im Worst-Case (schlechtesten Fall) ist das gesuchte Element x entweder nicht im Array enthalten oder befindet sich am letzten Platz des Arrays.
• In diesem Fall durchläuft die Schleife for i in range(len(arr)) alle n Elemente des Arrays.
• Innerhalb der Schleife wird für jedes Element ein Vergleich durchgeführt: if arr[i] == x.
• Im Worst-Case werden daher n Vergleiche durchgeführt, da die Schleife genau n Iterationen benötigt, um das gesamte Array zu durchsuchen.

Daher beträgt die Zeitkomplexität im Worst-Case O(n), wobei n die Länge des Arrays ist.

• In Landau-Notation schreiben wir den Aufwand für die Anzahl der Vergleiche als O(n), was bedeutet, dass die Zeitkomplexität linear in Bezug auf die Eingabegröße ist.

Zusammengefasst:

• Schleifenanzahl: Nahezu n Iterationen im Worst-Case.
• Vergleichsanzahl: n Vergleiche im Worst-Case.
• Zeitkomplexität im Worst-Case: O(n).

b)

Teilaufgabe 2: Analysiere die Speicherkomplexität des Algorithmus. Welche Rolle spielt die Eingabegröße für den Speicherbedarf des Algorithmus? Begründe Deine Antwort ausführlich.

Lösung:

Teilaufgabe 2: Analysiere die Speicherkomplexität des Algorithmus. Welche Rolle spielt die Eingabegröße für den Speicherbedarf des Algorithmus? Begründe Deine Antwort ausführlich.

Um die Speicherkomplexität des gegebenen Algorithmus zu analysieren, betrachten wir, wie viel zusätzlicher Speicher während der Ausführung des Algorithmus benötigt wird.

• Der Algorithmus untersucht ein Array arr der Länge n und sucht nach einem bestimmten Element x.
• Es werden keine zusätzlichen Datenstrukturen wie Arrays, Listen oder andere Speicher in großer Anzahl verwendet.
• Die einzigen zusätzlichen Speicherverwendungen sind die Variablen i im for-Schleifenindex sowie die temporäre Variable für den Vergleich arr[i] == x. Diese zusätzlichen Speicherverwendungen sind konstant und unabhängig von der Eingabegröße n.

Somit verbraucht der Algorithmus nur konstanten zusätzlichen Speicher, unabhängig von der Größe des Arrays:

• Variablen: Die Variablen i und temporäre Vergleichsvariablen sind notwendig und deren Anzahl ist konstant.
• Eingabegröße: Der Speicherbedarf für das Array arr hängt nur von der Eingabe ab und nicht von der Funktionsweise des Algorithmus.

Dies führt zur Speicherkomplexität von O(1), die konstant ist. Dies bedeutet, dass der Speicherbedarf des Algorithmus unabhängig von der Eingabegröße n ist und keine zusätzlichen Speicherplatzanforderungen jenseits der erforderlichen Variablen und temporären Werte bestehen.

• Zusätzlicher Speicher: Konstanter Speicher für Variablen.
• Speicherkomplexität: O(1).

Zusammengefasst:

• Speicherkomplexität: Der Speicherbedarf des Algorithmus ist konstant und unabhängig von der Eingabegröße, daher O(1).

c)

Teilaufgabe 3: Setze Dich mit den Konzepten Best-Case und Average-Case auseinander und wende diese auf den gegebenen Algorithmus an. Bestimme die entsprechenden Komplexitäten und vergleiche sie mit dem Worst-Case.

Lösung:

Teilaufgabe 3: Setze Dich mit den Konzepten Best-Case und Average-Case auseinander und wende diese auf den gegebenen Algorithmus an. Bestimme die entsprechenden Komplexitäten und vergleiche sie mit dem Worst-Case.

Um die Best-Case und Average-Case Komplexitäten des Algorithmus zu bestimmen, betrachten wir die verschiedenen Szenarien, in denen die lineare Suche angewendet wird.

• Best-Case: Der Best-Case tritt ein, wenn das gesuchte Element x sich an der ersten Position im Array befindet. Das bedeutet, dass der Algorithmus das Element sofort findet und nur einen Vergleich benötigt:
  • Die Schleife wird nur einmal durchlaufen.
  • Die Anzahl der Vergleiche beträgt 1.
  • Daher ist die Zeitkomplexität im Best-Case O(1).
• Average-Case: Der Average-Case (Durchschnittsfall) nimmt an, dass das gesuchte Element x sich an einer zufälligen Position im Array befinden kann. Im Durchschnitt müsste der Algorithmus die Hälfte des Arrays durchsuchen, um das Element zu finden:
  • Die Schleife wird im Durchschnitt n/2 Mal durchlaufen.
  • Die Anzahl der Vergleiche beträgt durchschnittlich n/2.
  • Nehmen wir die Mittelwertbetrachtung an, so ergibt sich für die Zeitkomplexität im Average-Case: O(n).

Da die Durchschnittslänge und die Gesamtzahl der durchgeführten Operationen direkt proportional zur Länge des Arrays sind, ist die Average-Case Komplexität linear.

• Worst-Case: Der Worst-Case tritt ein, wenn das gesuchte Element x entweder nicht im Array enthalten ist oder sich an der letzten Position befindet:
  • Die Schleife wird n-mal durchlaufen.
  • Die Anzahl der Vergleiche beträgt n.
  • Daher ist die Zeitkomplexität im Worst-Case O(n).

Zusammenfassend haben wir die Komplexitäten des Algorithmus:

• Best-Case: O(1).
• Average-Case: O(n).
• Worst-Case: O(n).

Beim Vergleich dieser Komplexitäten sehen wir, dass der Algorithmus im Worst-Case und Average-Case gleichbleibende lineare Zeitkomplexität aufweist, während der Best-Case konstant ist.

Aufgabe 2)

Sortieralgorithmen wie Quicksort und Mergesort sind von zentraler Bedeutung in der Informatik, um Daten effizient zu ordnen. Beide Algorithmen verfolgen einen 'Divide-and-Conquer'-Ansatz, jedoch unterscheiden sie sich in ihrer Herangehensweise und Leistungsfähigkeit unter unterschiedlichen Bedingungen. Quicksort wählt ein Pivot-Element und teilt das Array basierend auf diesem in zwei Teillisten auf, die dann rekursiv sortiert werden. Die Best-Case-Komplexität von Quicksort beträgt \(O(n \log n)\), die Worst-Case-Komplexität \(O(n^2)\) bei schlechtem Pivot. Mergesort hingegen teilt das Array in zwei Hälften, sortiert diese rekursiv und führt sie anschließend zusammen. Die Komplexität von Mergesort ist stets \(O(n \log n)\).

a)

Implementiere den Quicksort-Algorithmus in Python und erkläre jeden Schritt des Algorithmus in Deinem Code. Achte darauf, die Wahl des Pivot-Elements zu kommentieren und erkläre, wie das Array in zwei Teillisten aufgeteilt wird.

def quicksort(arr):    if len(arr) <= 1:        return arr    pivot = arr[len(arr) // 2]  # Pivot-Element wählen    left = [x for x in arr if x < pivot]  # Elemente kleiner als Pivot    middle = [x for x in arr if x == pivot]  # Elemente gleich Pivot    right = [x for x in arr if x > pivot]  # Elemente größer als Pivot    return quicksort(left) + middle + quicksort(right)  # Rekursive Anwendung und Zusammenführung

Lösung:

Hier ist der implementierte Quicksort-Algorithmus in Python, inklusive ausführlicher Erklärungen zu jedem Schritt und Kommentaren im Code:

def quicksort(arr):    # Wenn das Array nur ein oder kein Element enthält, ist es bereits sortiert    if len(arr) <= 1:        return arr    # Wahl des Pivot-Elements: Wir nehmen das mittlere Element des Arrays    pivot = arr[len(arr) // 2]  # Ein ausgewogenes Pivot-Element    # Teile des Arrays basierend auf dem Pivot-Element    left = [x for x in arr if x < pivot]  # Elemente kleiner als Pivot    middle = [x for x in arr if x == pivot]  # Elemente gleich dem Pivot    right = [x for x in arr if x > pivot]  # Elemente größer als Pivot    # Rekursive Anwendung von Quicksort auf die Teil-Arrays und Zusammenführung der Ergebnisse    return quicksort(left) + middle + quicksort(right)

• Bedingung: Wenn das Array nur ein oder weniger Elemente enthält, ist es per Definition bereits sortiert, daher geben wir es direkt zurück.
• Pivot-Element wählen: Hier wählen wir das mittlere Element des Arrays als Pivot-Element. Dies hilft, eine mögliche ungleiche Teilung des Arrays zu vermeiden und ist ein gängiger Ansatz.
• Teilen des Arrays: Wir teilen das Array in drei Teillisten, basierend auf ihrem Verhältnis zum Pivot-Element:
  • left: Enthält alle Elemente, die kleiner als das Pivot-Element sind.
  • middle: Enthält alle Elemente, die gleich dem Pivot-Element sind.
  • right: Enthält alle Elemente, die größer als das Pivot-Element sind.
• Rekursiver Aufruf und Zusammenführung: Wir wenden Quicksort rekursiv auf die left und right Teillisten an. Anschließend vereinen wir die sortierten Teillisten zusammen mit den Pivot-Elementen, um das endgültige sortierte Array zu erhalten.

b)

Berechne für ein Array mit n Elementen sowohl die durchschnittliche Komplexität als auch die Worst-Case-Komplexität von Mergesort und diskutiere, warum Mergesort eine stabile Sortiermethode ist. Verwende dazu die folgenden Gleichungen und formuliere die Herleitung:

• Rekursive Gleichung für Mergesort: \(T(n) = 2T(\frac{n}{2}) + O(n)\)
• Für den Durchschnittfall: \(T(n) = O(n \log n)\)
• Für den Schlechtestfall: \(T(n) = O(n \log n)\)

Lösung:

Um die Komplexität von Mergesort sowohl im Durchschnitt als auch im Worst-Case zu berechnen und zu verstehen, warum Mergesort eine stabile Sortiermethode ist, betrachten wir die gegebenen Gleichungen und Konzepte genauer.

• Rekursive Gleichung für Mergesort: Die Rekursionsgleichung für Mergesort lautet: \(T(n) = 2T(\frac{n}{2}) + O(n)\) Diese Gleichung beschreibt, wie die Zeitkomplexität von Mergesort entsteht:
• Mergesort teilt das Array in zwei gleich große Hälften, daher der Term 2T(\frac{n}{2}).
• Danach fügt es diese Hälften in linearer Zeit wieder zusammen, was durch O(n) dargestellt wird.

• Durchschnittliche Komplexität: Für den Durchschnittsfall können wir das Master-Theorem verwenden, um die oben genannte Rekursionsgleichung zu lösen: \(T(n) = 2T(\frac{n}{2}) + O(n)\) Das Master-Theorem für Rekursionsgleichungen der Form \(T(n) = aT(\frac{n}{b}) + f(n)\) besagt:
• Wenn \(f(n) = O(n^c)\) für eine Konstantze \(c\), dann:
• Gegeben:
• Wenn \(a = 2\), \(b = 2\) und \(f(n) = n\), dann gilt \(a = b^c\).
• Das bedeutet, dass \(T(n) = O(n \log n)\).
• Somit ergibt sich für den Durchschnittsfall die Komplexität: \(T(n)= O(n \log n)\)

• Worst-Case-Komplexität: Für den schlechten Fall wird dieselbe Gleichung verwendet und auf dieselbe Art und Weise gelöst. Da Mergesort in jeder Rekursionsebene das Array vollständig teilt und wieder zusammenführt, bleibt die Komplexität im schlechten Fall dieselbe: \(T(n) = O(n \log n)\)

• Stabilität von Mergesort: Mergesort ist eine stabile Sortiermethode, da es bei der Zusammenführung die Reihenfolge gleicher Elemente beibehält. Dies bedeutet, dass Mergesort zwei Elemente mit gleichen Werten in der Reihenfolge beibehält, in der sie im Input erscheinen. Während des Merge-Schritts wird sorgfältig darauf geachtet, Elemente von left oder right entsprechend ihrer Position zu wählen. Dies ist vor allem im Zusammenhang mit Stabilität und Performance von Vorteil, insbesondere wenn die Vergleiche auf andere Schlüssel angewendet werden:
• Mergesort führt eine stabile Sortierung durch, indem es sicherstellt, dass bei der Zusammenführung von Arrays immer zuerst das linke Element gewählt wird, wenn zwei Elemente gleich sind.

Aufgabe 3)

Gegeben ist der folgende ungerichtete Graph:

• Knoten: {A, B, C, D, E, F}
• Kanten: {(A, B), (A, C), (B, D), (C, E), (D, F), (E, F)}

a)

Führe eine Breitensuche (BFS) beginnend am Knoten A durch. Gib die Reihenfolge der besuchten Knoten an.

Lösung:

Um eine Breitensuche (Breadth-First Search, BFS) auf dem gegebenen Graphen zu machen, gehen wir Schritt für Schritt vor. BFS verwendet eine Queue (Warteschlange), um den nächsten Knoten zu besuchen. Wir beginnen bei Knoten A und fügen nachfolgend alle benachbarten Knoten in die Queue ein. Danach besuchen wir die Knoten in der Reihenfolge, in der sie in die Queue eingefügt wurden.

• Initialisierung: Beginnend mit dem Startknoten A.

Queue: [A]Visited: []

• Schritt 1: Besuche Knoten A. Füge alle benachbarten Knoten (B und C) in die Queue ein.

Queue: [B, C]Visited: [A]

• Schritt 2: Besuche Knoten B. Füge den benachbarten Knoten D in die Queue ein.

Queue: [C, D]Visited: [A, B]

• Schritt 3: Besuche Knoten C. Füge den benachbarten Knoten E in die Queue ein.

Queue: [D, E]Visited: [A, B, C]

• Schritt 4: Besuche Knoten D. Füge den benachbarten Knoten F in die Queue ein.

Queue: [E, F]Visited: [A, B, C, D]

• Schritt 5: Besuche Knoten E. (F ist bereits in der Queue)

Queue: [F]Visited: [A, B, C, D, E]

• Schritt 6: Besuche Knoten F. (Es gibt keine neuen benachbarten Knoten, da alle bereits besucht wurden)

Queue: []Visited: [A, B, C, D, E, F]

Die Reihenfolge der besuchten Knoten ist somit:

• A
• B
• C
• D
• E
• F

b)

Führe eine Tiefensuche (DFS) beginnend am Knoten A durch. Gib die Reihenfolge der besuchten Knoten an. Nutze dabei die iterative Methode (mit Stack).

Lösung:

Um eine Tiefensuche (Depth-First Search, DFS) auf dem gegebenen Graphen zu machen, verwenden wir die iterative Methode mit einem Stack. Die DFS besucht hierbei möglichst tief in den Graphen hinein, bevor es zurückgeht und andere Abzweigungen erkundet.

• Initialisierung: Beginnend mit dem Startknoten A.

Stack: [A]Visited: []

• Schritt 1: Besuche Knoten A. Füge alle benachbarten Knoten (B und C) in den Stack ein.

Stack: [C, B]Visited: [A]

• Schritt 2: Besuche Knoten B. Füge den benachbarten Knoten D in den Stack ein.

Stack: [C, D]Visited: [A, B]

• Schritt 3: Besuche Knoten D. Füge den benachbarten Knoten F in den Stack ein.

Stack: [C, F]Visited: [A, B, D]

• Schritt 4: Besuche Knoten F. (Es gibt keine neuen benachbarten Knoten, da alle bereits im Stack oder besucht sind)

Stack: [C]Visited: [A, B, D, F]

• Schritt 5: Besuche Knoten C. Füge den benachbarten Knoten E in den Stack ein.

Stack: [E]Visited: [A, B, D, F, C]

• Schritt 6: Besuche Knoten E. (F ist bereits besucht)

Stack: []Visited: [A, B, D, F, C, E]

Die Reihenfolge der besuchten Knoten ist somit:

• A
• B
• D
• F
• C
• E

c)

Zeige, dass die Komplexität der BFS und der DFS für den gegebenen Graphen jeweils bei \[O(V + E)\] liegt, wobei \ V \ die Anzahl der Knoten und \ E \ die Anzahl der Kanten im Graphen ist. Begründe Deine Antwort.

Lösung:

Um zu zeigen, dass die Komplexität der BFS und der DFS für den gegebenen Graphen jeweils bei \(O(V + E)\) liegt, wobei \(V\) die Anzahl der Knoten und \(E\) die Anzahl der Kanten im Graphen ist, müssen wir die Schritte beider Algorithmen und deren Zeitaufwand analysieren:

BFS (Breitensuche)

• Initialisierung: Das Hinzufügen des Startknotens zur Queue kostet \(O(1)\).
• Jeder Knoten wird genau einmal besucht: Jeder Knoten wird in die Queue eingefügt und einmal daraus entfernt, was jeweils \(O(1)\) kostet. Bei \(V\) Knoten ergibt sich somit ein Aufwand von \(O(V)\).
• Besuch aller benachbarten Kanten: Jeder Knoten hat Kanten, die zu anderen Knoten führen. Da der Graph ungerichtet ist, wird jede Kante höchstens zweimal (einmal von jedem Ende) betrachtet. Bei \(E\) Kanten ergibt das einen Aufwand von \(O(E)\).

Zusammengefasst ergibt dies:

Gesamtkomplexität = \(O(1) + O(V) + O(E) = O(V + E)\)

DFS (Tiefensuche)

• Initialisierung: Das Hinzufügen des Startknotens zum Stack kostet \(O(1)\).
• Jeder Knoten wird genau einmal besucht: Jeder Knoten wird in den Stack eingefügt und einmal daraus entfernt, was jeweils \(O(1)\) kostet. Bei \(V\) Knoten ergibt sich somit ein Aufwand von \(O(V)\).
• Besuch aller benachbarten Kanten: Jeder Knoten hat Kanten, die zu anderen Knoten führen. Da der Graph ungerichtet ist, wird jede Kante höchstens zweimal (einmal von jedem Ende) betrachtet. Bei \(E\) Kanten ergibt das einen Aufwand von \(O(E)\).

Zusammengefasst ergibt dies:

Gesamtkomplexität = \(O(1) + O(V) + O(E) = O(V + E)\)

Somit liegt die Komplexität sowohl für die BFS als auch für die DFS bei \(O(V + E)\), wobei \(V\) die Anzahl der Knoten und \(E\) die Anzahl der Kanten im Graphen ist.

d)

Betrachte einen ungewichteten Graphen mit den gleichen Knoten und Kanten. Bestimme den kürzesten Weg von A nach F mittels BFS und gib den Pfad an.

Lösung:

Um den kürzesten Weg von Knoten A nach Knoten F in einem ungewichteten Graphen mittels der Breitensuche (BFS) zu bestimmen, folgen wir den Schritten der BFS. BFS ist besonders geeignet für das Finden des kürzesten Pfades in ungewichteten Graphen, da sie Knoten in der Reihenfolge ihrer Entfernung vom Startknoten untersucht.

Schritte zur Bestimmung des kürzesten Weges mittels BFS:

Zusätzlich zur Queue verwenden wir ein Dictionary, um die Vorgänger jedes Knotens zu speichern. Dies ermöglicht es uns, den Pfad zurückzuverfolgen, sobald wir Knoten F erreicht haben.

• Initialisierung: Startknoten A zur Queue hinzufügen und Vorgänger von A auf None setzen.

Queue: [A]Visited: [A]Predecessors: {A: None}

• Schritt 1: Besuche Knoten A. Füge alle benachbarten Knoten (B und C) in die Queue ein und setze ihren Vorgänger auf A.

Queue: [B, C]Visited: {A, B, C}Predecessors: {A: None, B: A, C: A}

• Schritt 2: Besuche Knoten B. Füge den benachbarten Knoten D in die Queue ein und setze seinen Vorgänger auf B.

Queue: [C, D]Visited: {A, B, C, D}Predecessors: {A: None, B: A, C: A, D: B}

• Schritt 3: Besuche Knoten C. Füge den benachbarten Knoten E in die Queue ein und setze seinen Vorgänger auf C.

Queue: [D, E]Visited: {A, B, C, D, E}Predecessors: {A: None, B: A, C: A, D: B, E: C}

• Schritt 4: Besuche Knoten D. Füge den benachbarten Knoten F in die Queue ein und setze seinen Vorgänger auf D.

Queue: [E, F]Visited: {A, B, C, D, E, F}Predecessors: {A: None, B: A, C: A, D: B, E: C, F: D}

• Schritt 5: Besuche Knoten E. (F ist bereits in der Queue)

Queue: [F]Visited: {A, B, C, D, E, F}Predecessors: {A: None, B: A, C: A, D: B, E: C, F: D}

• Schritt 6: Besuche Knoten F. (Ziel erreicht)

Queue: []Visited: {A, B, C, D, E, F}Predecessors: {A: None, B: A, C: A, D: B, E: C, F: D}

Pfad von A nach F zurückverfolgen:

Wir können den kürzesten Pfad von F nach A durch das Dictionary der Vorgänger zurückverfolgen:

• F -> D -> B -> A

Dann kehren wir den Pfad um, um den kürzesten Weg von A nach F zu erhalten:

• A -> B -> D -> F

Der kürzeste Weg von A nach F ist somit: A -> B -> D -> F

Aufgabe 4)

Gegeben sei eine rekursive Implementierung zur Berechnung der Fibonacci-Zahlen in Python. Die Fibonacci-Zahlen sind folgendermaßen definiert:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) für n > 1

def fib(n):    if n == 0:        return 0    elif n == 1:        return 1    else:        return fib(n-1) + fib(n-2)

b)

Implementiere eine Verbesserung der gegebenen rekursiven Funktion mittels Memoization in Python. Erkläre, wie sich diese Änderung auf die Zeitkomplexität auswirkt.

Lösung:

Verbesserung der rekursiven Fibonacci-Funktion mittels Memoization

Memoization ist eine Technik zur Leistungsverbesserung rekursiver Funktionen, indem Zwischenergebnisse gespeichert und wiederverwendet werden, anstatt sie mehrfach zu berechnen. Dies kann die Zeitkomplexität drastisch reduzieren.

Hier ist die verbesserte Implementierung der Fibonacci-Funktion in Python mithilfe von Memoization:

def fib_memo(n, memo={}):    if n in memo:        return memo[n]    if n == 0:        memo[0] = 0        return 0    elif n == 1:        memo[1] = 1        return 1    else:        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)        return memo[n]

Erklärung der Memoization-Verbesserung

• Ein Dictionary memo wird verwendet, um bereits berechnete Ergebnisse zu speichern.
• Bei jedem Aufruf der Funktion wird zunächst geprüft, ob das Ergebnis bereits im memo vorhanden ist.
• Falls nicht, wird das Ergebnis berechnet, im memo-Dictionary gespeichert und dann zurückgegeben.

Auswirkungen auf die Zeitkomplexität

Bei der ursprünglichen rekursiven Implementierung beträgt die Zeitkomplexität O(2^n), da viele Berechnungen mehrfach durchgeführt werden, wie bereits in der vorherigen Analyse gezeigt.

Durch die Verwendung von Memoization wird jede Fibonacci-Zahl jedoch nur einmal berechnet. Danach wird das zuvor berechnete Ergebnis direkt aus dem memo-Dictionary abgerufen:

• Die Anzahl der Berechnungen ist linear proportional zu n, da jede Fibonacci-Zahl von 0 bis n nur einmal berechnet wird.
• Dadurch reduziert sich die Zeitkomplexität auf O(n), da jede Fibonacci-Zahl nur einmal berechnet und gespeichert wird.

Zusätzlich benötigen wir O(n) Speicherplatz zur Speicherung der Zwischenwerte im Dictionary memo.

Zusammengefasst haben wir durch Einsatz von Memoization die Zeitkomplexität der Fibonacci-Berechnung von exponentiell O(2^n) auf linear O(n) reduziert.

c)

Zeige anhand der iterativen Implementierung die Berechnung der 10. Fibonacci-Zahl. Definiere eine Python-Funktion, die dies tut und diskutiere die Unterschiede in Bezug auf Zeit- und Speicherkomplexität im Vergleich zur rekursiven Implementierung.

Lösung:

Iterative Implementierung der Fibonacci-Zahlen

Die iterative Methode zur Berechnung der Fibonacci-Zahlen vermeidet Rekursion und damit die mit Rekursion verbundene Stack-Overhead. Hier ist die Python-Funktion zur Berechnung der 10. Fibonacci-Zahl:

def fib_iterative(n):    if n == 0:        return 0    elif n == 1:        return 1    a, b = 0, 1    for _ in range(2, n+1):        a, b = b, a + b    return b# Berechnung der 10. Fibonacci-Zahlprint(fib_iterative(10))  # Ausgabe: 55

Unterschiede in Bezug auf Zeit- und Speicherkomplexität

Zeitkomplexität:

• Rekursive Implementierung ohne Memoization: Die Zeitkomplexität beträgt O(2^n), da viele Berechnungen mehrfach durchgeführt werden.
• Rekursive Implementierung mit Memoization: Die Zeitkomplexität beträgt O(n), da jede Fibonacci-Zahl von 0 bis n nur einmal berechnet wird.
• Iterative Implementierung: Die Zeitkomplexität beträgt ebenfalls O(n), da genau n Iterationen benötigt werden, um die n-te Fibonacci-Zahl zu berechnen.

Speicherkomplexität:

• Rekursive Implementierung ohne Memoization: Die Speicherkomplexität beträgt O(n) aufgrund des Speicherbedarfs des Rekursionsstapels.
• Rekursive Implementierung mit Memoization: Die Speicherkomplexität beträgt O(n), da wir ein Dictionary zur Speicherung der Zwischenergebnisse verwenden.
• Iterative Implementierung: Die Speicherkomplexität beträgt O(1), da nur eine konstante Menge an zusätzlichem Speicher für die Variablen a und b benötigt wird.

Zusammengefasst bietet die iterative Implementierung eine sehr effiziente Lösung sowohl hinsichtlich Zeit- als auch Speicherkomplexität.