Aufgabe 1: Verständnisfrage zum Master-Theorem¶
Welche der vier Möglichkeiten ist die beste Intepretation von $b^d$ des Master-Theorems 4.1?
- Die Rate mit der die Anzahl der Unterprobleme (für die Rekursionsstufe) wächst.
- Die Rate mit der die Arbeit der ganzen Rekursionsstufe wächst/schrupft.
- Die Rate mit der die Arbeit pro Unterproblem (für die Rekursionsstufe) schrupft.
- Die Rate mit der die Unterproblemgröße (für die Rekursionsstufe) schrupft.
Aufgabe 2: Anwenden der Black-Box Master-Methode¶
$T(n)$ sei die Laufzeit eines Algorithmus in Abhängigkeit von $n$. Bestimmen Sie die kleinste korrekte obere Grenze (O-Notation) der Laufzeiten mit der Black-Box Master.Methode bei folgenden Standard-Rekurrenzen:
- $T(n) \leq 7 \cdot T(n/3) + O(n^2)$
- $T(n) \leq 9 \cdot T(n/3) + O(n^2)$
- $T(n) \leq 5 \cdot T(n/3) + O(n)$
Aufgabe 3: Anwenden der Black-Box Master-Methode für bekannte Algorithmen¶
Bestimmen Sie die Laufzeiten mit der Black-Box Master.Methode für folgende Algorithmen:
KaratsubaBinarySearchPowerV2(siehe letzte Übung)
Geben Sie zuerst jeweils die Werte für die drei Parameter $a,b$ und $d$ an. Bestimmen Sie anschließend die Laufzeitkomplexität mit dem Theorem 4.1 der Master-Methode (Black-Box).
Vergleichen Sie die Laufzeit von Karatsuba mit RectIntMult. Welcher Algorithmus ist schneller?
In [ ]: