michael.eichberg@dhbw.de, Raum 149B
1.0.1
Die Folien sind teilweise inspiriert von oder basierend auf Lehrmaterial von Prof. Dr. Ritterbusch, Prof. Dr. Baumgart oder Prof. Dr. Albers.
Analyse des Aufwands zur Berechnung von Ergebnissen ist wichtig ...
im Design,
in der Auswahl
und der Verwendung von Algorithmen.
Für relevante Algorithmen und Eingangsdaten können Vorhersagen getroffen werden:
Um Zusammenhänge sind zwischen Eingangsdaten und Aufwand zu finden.
Aufwand kann Rechenzeit, Speicherbedarf oder auch Komponentennutzung sein.
Der Rechenaufwand ist häufig zentral und wird hier betrachtet, die Verfahren sind aber auch für weitere Ressourcen anwendbar.
Die Vorhersagen erfolgen über asymptotische Schätzungen
mit Hilfe der Infinitesimalrechnung,
durch Kategorisierung im Sinne des Wachstumsverhaltens,
damit ist oft keine exakte Vorhersage möglich.
Unterschiedliche Systeme sind unterschiedlich schnell, relativ dazu wird es interessant.
Im Folgenden geht es um:
die Beschreibung des asymptotischen Wachstumsverhaltens
die Analyse von iterativen Algorithmen
die Analyse von rekursiv teilenden Algorithmen
Die Infinitesimalrechnung bezeichnet die Differenzial- und Integralrechnung. Es wird mit unendlich kleinen Größen gerechnet.
Der folgende Abschnitt behandelt die dynamische Programmierung, um ein Problem effizient zu lösen. Er zeigt gleichzeitig wie die Wahl des Algorithmus und der Implementierung die Laufzeit dramatisch beeinflussen kann.
Berechnung der Fibonacci-Zahlen
Implementieren Sie eine rekursive Funktion, die die \(n\)-te Fibonacci-Zahl berechnet!
Bis zu welchem \(n\) können Sie die Fibonacci-Zahlen in vernünftiger Zeit berechnen (d. h. < 10 Sekunden) ?
Lösen eines Problems durch Lösen mehrerer kleinerer Teilprobleme, aus denen sich die Lösung für das Ausgangsproblem zusammensetzt.
Mehrfachberechnungen von Lösungen
Speichern einmal berechneter Lösungen (in einer Tabelle) für spätere Zugriffe.
Definition
\(F(0) = 0\)
\(F(1) = 1\).
\(F(n) = F(n-1) + F(n-2)\)
\(F(n)\) als stehende Formel:
Aufrufbaum
Rekursive Beschreibung des Problems P
Bestimmung einer Menge \(T\), die alle Teilprobleme von \(P\) enthält, auf die bei der Lösung von \(P\) – auch in tieferen Rekursionsstufen – zurückgegriffen wird.
Bestimmung einer Reihenfolge \(T_0 , \ldots, T_k\) der Probleme in \(T\), so dass bei der Lösung von \(T_i\) nur auf Probleme \(T_j\) mit \(j < i\) zurückgegriffen wird.
Sukzessive Berechnung und Speicherung von Lösungen für \(T_0 ,...,T_k\).
Rekursive Definition der Fibonacci-Zahlen nach gegebener Gleichung.
\(T = { f(0),..., f(n-1)}\)
\(T_i = f(i), i = 0,...,n – 1\)
Berechnung von \(fib(i)\) benötigt von den früheren Problemen nur die zwei letzten Teillösungen \(fib(i – 1)\) und \(fib(i – 2)\) für \(i \geq 2\).
Lösung mit linearer Laufzeit und konstantem Speicherbedarf
1procedure fib (n : integer) : integer2f_n_m2 := 0; f_n_m1 :=13for k := 2 to n do4f_n := f_n_m1 + f_n_m25f_n_m2 := f_n_m16f_n_m1 := f_n7if n ≤ 1 then return n8else return f_n
Lösung mit Memoisierung (Memoization)
Berechne jeden Wert genau einmal, speichere ihn in einem Array F[0...n]:
1procedure fib (n : integer) : integer2F[0] := 0; F[1] := 1;3for i := 2 to n do4F[i] := ∞ // Initialisierung5return lookupfib(n)67procedure lookupfib (n : integer) : integer8if F[n] = ∞ then9F[n] := lookupfib(n-1) + lookupfib(n-2)10return F[n]
Fibonacci-Zahl effizient berechnen
Implementieren Sie den Pseudocode der ersten Lösung zur Berechnung der Fibonacci-Zahlen.
Bis zur welcher Fibonacci-Zahl können Sie die Berechnung nun durchführen?
Im Allgemeinen werden Laufzeiten oder Aufwände in Abhängigkeit von einer Eingangsgröße als Folge beschrieben:
Folgenglieder
Beispiel: (\(a_n\)) : \(a_1 = 2, a_2 = 3, a_3 = 7, a_4 = 11, ...\)
Rekursive Definition
Beispiel: (\(c_n\)) : \(c_1 = 1, c_2 = 1, c_{n+2} = c_n + c_{n+1}\; für\; n \in \mathbb(N)\)
Explizite Definition
Beispiel: (\(b_n\)) : \(b_n = n^2\) für \(n \in~\mathbb{N}\)
Eine rekursive Definition ist eine Definition, die sich auf sich selbst bezieht. Häufiger schwieriger zu analysieren. Die explizite Definition ist eine direkte Zuweisung und meist die beste Wahl.
Die explizite Definition von Laufzeiten ist zur Auswertung vorzuziehen.
Die rekursive Definition tritt oft bei rekursiven Verfahren auf, und sollte dann in eine explizite Definition umgerechnet werden.
Berechnung der Anzahl der Schritte zum Lösen der Türme von Hanoi.
Türme von Hanoi mit 3 Scheiben.
Die Türme von Hanoi (ChatGPT)
Die Türme von Hanoi sind ein klassisches mathematisches Puzzle. Es besteht aus drei Stäben und einer bestimmten Anzahl von unterschiedlich großen Scheiben, die anfangs alle in absteigender Reihenfolge auf einem Stab gestapelt sind – der größte unten und der kleinste oben.
Das Ziel des Spiels ist es, alle Scheiben auf einen anderen Stab zu bewegen, wobei folgende Regeln gelten:
Es darf immer nur eine Scheibe auf einmal bewegt werden.
Eine größere Scheibe darf nie auf einer kleineren liegen.
Alle Scheiben müssen auf den dritten Stab bewegt werden, indem sie über den mittleren Stab verschoben werden.
Für die Lösung sind für jeden Ring \(n\) die folgenden \(a_n\) Schritte erforderlich:
Alle \(n-1\) kleineren Ringe über Ring \(n\) müssen mit \(a_{n-1}\) Schritten auf den Hilfsstab.
Der Ring \(n\) kommt auf den Zielstab mit einem Schritt.
Alle \(n-1\) Ringe vom Hilfsstab müssen mit \(a_{n-1}\) Schritten auf den Zielstab.
Bei nur einem Ring ist \(a_1 = 1\) und sonst \(a_n = a_{n-1} + 1+ a_{n-1} = 2a_{n-1} + 1\).
Also: \(a_1 = 1\), \(a_2 = 2·1+ 1= 3\), \(a_3 = 2·3+ 1= 7\), \(a_4 = 2·7+ 1= 15\), ...
Damit liegt nahe, dass der Aufwand (1,3,7,15,...) dem Zusammenhang \(a_n = 2^n-1\) entspricht.
Beweis durch vollständige Induktion
Induktionsanfang \(n = 1\): \(a_1 = 2^n -1 = 2^1-1 = 1\)
Induktionsvoraussetzung: \(a_{n-1} = 2^{n-1}-1\) und \(a_{n} = 2a_{n-1} + 1\)
Induktionsschritt (\(n-1 \rightarrow n\)):
\(a_{n} = 2·(2^{n-1}-1)+1\)
\(\quad\, = 2^{n}-2+1\)
\(\quad\, = 2^{n}-1\)
Damit ist die Vermutung bestätigt.
Betrachten wir die Folge (\(a_n\)) mit \(a_n = {(-1)^n \over n} + 2\), \(n \in \mathbb{N}\):
Entwicklung der Folge:
Die Folge konvergiert zu 2, da für ein gegebenes \(\varepsilon > 0\) ein \(N\) existiert so dass \(|a_n-a|<\varepsilon \):
wenn \(n > {1 \over \varepsilon }\) ist.
D. h. \(a_n \rightarrow 2\) oder \(lim_{n\rightarrow \infty } a_n = 2\)
Die Folge \(a_n = {n^2 + 1 \over n^3}\) konvergiert gegen 0, da:
Die Folge konvergiert gegen 0, da der Zähler gegen 0 strebt (\(\lim_{{n \to \infty}} {( 1/n)} = 0\) und \(\lim_{{n \to \infty}} {( 1/n^3)} = 0\)) und der Nenner konstant ist.
Die allgemeine Vorgehensweise ist es, die größte Potenz im Zähler und Nenner zu finden und dann diese auszuklammern. Im zweiten Schritt kürzen wir dann. In diesem Fall ist es \(n^3\).
D. h. das Ziel ist es den Ausdruck so umzuformen, dass der Grenzwert direkt abgelesen werden kann. Dies ist inbesondere dann der Fall, wenn \(n\) nur noch im Nenner oder Zähler steht.
Wir möchten \(f(x) = \frac{\ln(x)}{x^{2/3}}\) für \(x \to \infty\) untersuchen.
Das vereinfacht sich zu:
Die Regel von L'Hôpital ermöglicht es Grenzwerte von Ausdrücken des Typs \(\frac{0}{0}\) oder \(\frac{\infty}{\infty}\) zu berechnen. In diesem Fall nehmen wir die Ableitungen des Zählers und des Nenners.
Die Regel besagt:
Falls \(\lim_{x \to a} \frac{f(x)}{g(x)}\) den unbestimmten Ausdruck \(\frac{0}{0}\) oder \(\frac{\infty}{\infty}\) ergibt, dann gilt:
sofern der Grenzwert auf der rechten Seite existiert oder unendlich ist.
Erste Folge - zum Aufwärmen
Zeigen Sie, dass die Folge \(a_n = {n^2 \over n^2 + 1}\) konvergiert und bestimmen Sie den Grenzwert.
Zweite Folge
Bestimmen Sie den Grenzwert der Folge, wenn er denn existiert: \(b_n = {1 - n + n^2 \over n(n+1)}\).
Folge mit Wurzel
Bestimmen Sie den Grenzwert \(\lim_{n\rightarrow \infty } \sqrt{n^2 + n} - n\).
Hier könnte die dritte Binomische Formel (\((a-b)(a + b) = a^2 -b^2\)) hilfreich sein.
Um eine Potenz aus einer Wurzel zu bekommen, hilft ggf. das Wurzelgesetz \(\sqrt{a} \cdot \sqrt{b} = \sqrt{a \cdot b}\).
Beispiel: \(\sqrt{x^4 + x^2} = \sqrt{x^4 (1 + 1/x ^2)} = \sqrt{x^4} \cdot \sqrt{(1 + 1/x ^2)} = x^2 \cdot \sqrt{(1 + 1/x ^2)}\).
Folge mit mehreren Termen
Berechnen Sie den Grenzwert Folge \(b_n = {n^2 -1 \over n + 3 } - {n^2 + 1 \over n - 1}\) falls er existiert.
Zwei Wurzeln
Bestimmen Sie den Grenzwert \(\lim_{n\rightarrow \infty } \sqrt{n^2 + 1} - \sqrt{n^2 + 4n}\).
Es gilt der folgende Zusammenhang für die Mengen \(\mathcal{O}(g)\)[1], \(\Omega (g)\) und \(\Theta (g)\):
Wenn eine Funktion \(f\) in der Menge \(O(g)\) (d. h. \(f \in O(g)\)) ist, dann wächst die Funktion \(g\) schneller als die Funktion \(f\). Typischerweise ist der Grenzwert von \(f(n)/g(n)\) für \(n \to \infty\) in diesem Falle 0.
Die Verwendung der O-Notation zur Beschreibung der Komplexität von Algorithmen wurde von Donald E. Knuth eingeführt.
Insbesondere für die obere Abschätzung \(O(g)\) gibt es eine alternative Schreibweise:
D. h. ab einem Wert \(n_0\) liegt die Komplexität der Funktion \(f\) unter der \(c_0\)-fachen Komplexität der Funktion \(g\).
Beispiel: \(f(n) = 4n + 7 \in O(n)\)
\(4n + 7 \leq c_0· n \Leftrightarrow n· (4- c_0) \leq -7\)
Wähle: \(c_0 = 5\) und \(n_0 = 7\) sowie \(g(n) = n\).
Häufige Vergleichsfunktionen sind zum Beispiel Monome wie \(n^k\) für \(k \in \mathbb{N}_0\).
Asymptotische Laufzeitabschätzungen können zu Missverständnissen führen:
Asymptotische Abschätzungen werden nur für steigende Problemgrößen genauer, für kleine Problemstellungen liegt oft eine ganz andere Situation vor.
Asymptotisch nach oben abschätzende Aussagen mit \(O(g)\)-Notation können die tatsächliche Laufzeit beliebig hoch überschätzen, auch wenn möglichst scharfe Abschätzungen erwünscht sein sollten, gibt es diese teilweise nicht in beliebiger Genauigkeit, oder sind nicht praktikabel.
Nur Abschätzungen von gleicher Ordnung \(\Theta (g)\) können direkt verglichen werden, oder wenn zusätzlich zu \(O(g)\) auch \(\Omega (h)\) Abschätzungen vorliegen.
Gegenseitige asymptotische Abschätzung I
Bestimmen Sie welche Funktionen sich gegenseitig asymptotisch abschätzen:
\(f_1(x) = \sqrt[3]{x},\; f_2(x) = e^{-1+ln\, x} , f_3(x) = {x \over ln(x) + 1}\).
D. h. berechnen Sie:
Denken Sie daran, dass die erste Ableitung von \(f(x) = ln(x)\) die Funktion \(f'(x)= {1 \over x}\) ist.
Gegenseitige asymptotische Abschätzung II
Vergleichen Sie: \(f_1(x) = e^{2ln(x)+1}\) und \(f_2(x) = {x^3+1 \over x}\).
Gegenseitige asymptotische Abschätzung III
Vergleichen Sie: \(f_1(x) = 2^{1+2x}\) und \(f_2(x) = 4^x + 2^x\).
Algorithmen sind Verfahren, die gegebene Ausprägungen von Problemen in endlich vielen Schritten lösen können.
Dabei muss jeder Schritt
ausführbar und
reproduzierbar sein.
Es gibt aber oft viele Methoden die Probleme zu lösen:
Daher ist es wichtig, Eigenschaften von Algorithmen zu analysieren!
Insbesondere z.B.
Zeitaufwand und
Speicherbedarf
in Abhängigkeit von der Problemgröße.
Problemumfang (Problemgröße) n
Konkrete Beispiele für Problemgrößen:
Konkreter Wert von \(n\): \(f (n)\)
Stellenanzahl des Eingabewertes (der Eingabewerte) → \(f (z_1z_2 . . . z_n) (z_i \in { 0, . . . , 9 })\)
Anzahl der Eingabewerte: \(f(x_1, x_2, . . . , x_n)\)
Tatsächlicher Zeitaufwand hängt vom ausführenden Rechnersystem ab.
Beeindruckende Entwicklung der Rechentechnik.
Größere Probleme können gelöst werden.
Langsamere Algorithmen bleiben langsamer auch auf schnellen Systemen.
Eine möglichst sinnvolle Annahme eines Rechnersystems gesucht:
Von-Neumann System
mit einer Recheneinheit
genaue Geschwindigkeit nicht relevant.
Die Komplexität eines Problems zu bestimmen ist oft ausgesprochen schwierig, da man hierfür den besten Algorithmus kennen muss. Es stellt sich dann weiterhin die Frage wie man beweist, dass der beste Algorithmus vorliegt.
Bei vielen Komplexitätsanalysen steht die Zeitkomplexität im Vordergrund.
Die Zeitkomplexität misst nicht konkrete Ausführungszeiten (z. B. 1456 ms), da die Ausführungszeit von sehr vielen Randbedingungen abhängig ist, die direkt nichts mit demAlgorithmus zu tun haben, z. B.:
Prozessortyp und Taktfrequenz
Größe des Hauptspeichers
Zugriffszeiten der Peripheriegeräte
Betriebssystem → wird z. B. ein virtueller Speicher unterstützt
Compiler- oder Interpreter-Version
Systemlast zum Zeitpunkt der Ausführung
Klasse |
Eigenschaft |
|---|---|
\(O(1)\) |
Die Rechenzeit ist unabhängig von der Problemgröße |
\(O(\log n)\) |
Die Rechenzeit wächst logarithmisch (zur Basis 2) mit der Problemgröße |
\(O(n)\) |
Die Rechenzeit wächst linear mit der Problemgröße |
\(O(n \cdot \log n)\) |
Die Rechenzeit wächst linear logarithmisch mit der Problemgröße |
\(O(n^2)\) |
Die Rechenzeit wächst quadratisch mit der Problemgröße |
\(O(n^3)\) |
Die Rechenzeit wächst kubisch mit der Problemgröße |
\(O(2^n)\) |
Die Rechenzeit wächst exponentiell (zur Basis 2) mit der Problemgröße |
\(O(n!)\) |
Die Rechenzeit wächst entsprechend der Fakultätsfunktion mit der Problemgröße |
\(O(1)\)
Liegt typischerweise dann vor, wenn das Programm nur einmal linear durchlaufen wird.
Es liegt keine Abhängigkeit von der Problemgröße vor, d. h. beispielsweise keine Schleifen in Abhängigkeit von \(n\).
Beispiel:
Die Position eines Datensatzes auf einem Datenträger kann mit konstanten Aufwand berechnet werden.
\(O(\log n)\)
Beispiel:
Binäre Suche; d. h. in einem sortierten Array mit \(n\) Zahlen eine Zahl suchen.
\(O(n)\)
Beispiel:
Invertieren eines Bildes oder sequentielle Suche in einem unsortierten Array.
\(O(n \cdot \log n)\)
Beispiel:
Bessere Sortierverfahren wie z. B. Quicksort.
\(O(n^2)\)
Häufig bei zwei ineinander geschachtelten Schleifen.
Beispiel:
Einfache Sortierverfahren wie z. B. Bubble-Sort oder die Matrixaddition.
\(O(n^3)\)
Häufig bei drei ineinander geschachtelten Schleifen.
Beispiel:
Die Matrixmultiplikation.
\(M(m, t)\) ist eine Matrix mit m Zeilen und t Spalten.
\(C(m, t) = A(m, n)· B(n, t)\) mit
\(c_{i,j} = \sum_{k = 1}^n a_{i,k}· b_{k,j}\qquad i = 1, . . . , m \qquad j = 1, . . . , t\)
\(O(2^n)\)
Typischerweise der Fall, wenn für eine Menge mit n Elementen alle Teilmengen berechnet und verarbeitet werden müssen.
Beispiel:
Rucksackproblem (Knapsack Problem)
Ein Rucksack besitzt eine maximale Tragfähigkeit und \(n\) Gegenstände unterschiedlichen Gewichts liegen vor, deren Gesamtgewicht über der Tragfähigkeit des Rucksacks liegt. Ziel ist es jetzt eine Teilmenge von Gegenständen zu finden, so dass der Rucksack optimal gefüllt wird.
\(O(n!)\)
Typischerweise der Fall, wenn für eine Menge von \(n\) Elementen alle Permutationen dieser Elemente zu berechnen und zu verarbeiten sind.
Beispiel:
Problem des Handlungsreisenden (Traveling Salesman Problem (TSP))
Gegeben sind \(n\) Städte, die alle durch Straßen direkt miteinander verbunden sind und für jede Direktverbindung ist deren Länge bekannt.
Gesucht ist die kürzeste Rundreise, bei der jede Stadt genau einmal besucht wird.
Sei die Problemgröße \(n = 128\):
Klasse |
Laufzeit |
|---|---|
\(O(\log_2\, n)\) |
\(1,75\,ns\) |
\(O(n)\) |
\(32\,ns\) |
\(O(n \cdot \log_2\, n)\) |
\(224\,ns\) |
\(O(n^2)\) |
\(4,096\,µs\) |
\(O(n^3)\) |
\(524,288\,µs\) |
\(O(2^n)\) |
\(2,70 \cdot 10^{21}\,a\) |
\(O(3^n)\) |
\(9,35 \cdot 10^{43}\,a\) |
\(O(n!)\) |
\(3,06 \cdot 10^{198}\,a\) |
Dies zeigt, dass Algorithmen mit einer Komplexität von \(O(n^3)\) oder höher für große bzw. nicht-triviale Problemgrößen nicht praktikabel sind.
Elementare Operation |
Anzahl der Rechenschritte |
|---|---|
elementare Arithmetik: + ,- , * , /, etc. |
1 |
elementare logische Operationen: &&, ||, !, etc. |
1 |
Ein- und Ausgabe |
1 |
Wertzuweisung |
1 |
return, break, continue |
1 |
Kontrollstrukturen |
Anzahl der Rechenschritte |
Methodenaufruf |
1 + Komplexität der Methode |
Fallunterscheidung |
Komplexität des logischen Ausdrucks + Maximum der Komplexität der Rechenschritte der Zweige |
Schleife |
Annahme: \(m\) Durchläufe: Komplexität der Initialisierung + \(m\) mal die Komplexität des Schleifenkörpers + Komplexität aller Schleifenfortschaltungen |
def ist_primzahl(n):
prim = True # Wertzuweisung: 1
i = 2 # Wertzuweisung: 1
if n < 2: # Vergleich: 1
prim = False # Wertzuweisung: 1
else: # Durchläufe: n-2 * (
while prim and i < n: # Vergleiche, und: 3
if n % i == 0: # modulo, Vergleich: 2
prim = False # Wertzuweisung: 1
i += 1 # Inkrement: 1
# )
# letzte Bedingungsprüfung 3
return prim # Befehl: 1Im schlechtesten Fall, d. h. es gilt \(i==n\) nach der while-Schleife, werden \(7 + (n- 2)· 7 = 7· n- 7\) Rechenschritte benötigt. Die Anzahl der Rechenschritte hängt somit linear vom Eingabewert \(n\) ab.
Beachte, dass in keinem Falle alle Instruktionen ausgeführt werden.
Insertion-Sort
Vergleichbar zum Ziehen von Karten: die neue Karte wird an der richtigen Stelle eingeschoben.
def insertion_sort(A):
for i in range(1, len(A)):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = keyAlgorithmus: Insertion-Sort(A, n) [Pseudocode] |
Zeit |
Anzahl |
|
|---|---|---|---|
1: |
for i = 2...n do |
c1 |
\(n\) |
2: |
key = A[i] |
c2 |
\(n-1\) |
3: |
j= i−1 |
c3 |
\(n-1\) |
4: |
while j > 0 and A[j] > key do |
c4 |
\(\sum_{i=2}^n t_i\) |
5: |
A[j + 1] = A[j] |
c5 |
\(\sum_{i=2}^n (t_i-1)\) |
6: |
j= j - 1 |
c6 |
\(\sum_{i=2}^n (t_i-1)\) |
7: |
A[j + 1] = key |
c7 |
\(n-1\) |
\(c_x\) sind die konstanten Kosten für die jeweilige Operation. Wir abstrahieren diese als \(c = max(c_1,...c_7)\).
\(t_i\) ist die Anzahl der Schritte, die für das Einsortieren der n-ten Karte benötigt wird. Dies hängt davon ab, wie die Liste vorliegt.
Abschätzung der Laufzeit \(T(n)\) nach oben:
Jetzt können drei Fälle unterschieden werden:
die Liste ist bereits sortiert, d. h. \(t_i = 1\)
die Liste ist umgekehrt sortiert, d. h. \(t_i = i\)
die Liste ist zufällig sortiert, d. h. \(t_i = {i+1 \over 2}\)
Im schlimmsten Fall, d. h. die Liste ist umgekehrt sortiert, ergibt sich:
nach Anwendung der Summenformel:
Im besten Fall, d. h. die Liste ist bereits sortiert, ergibt sich:
In Hinblick auf den Zeitaufwand gilt:
Der Insertion-Sort-Algorithmus hat eine quadratische Komplexität, d. h. die Laufzeit wächst quadratisch mit der Problemgröße. Er hat die Komplexität \(O(n^2)\).
Bestimmung der asymptotischen Laufzeit eines Algorithmus
Die Funktion \(p(n)\) hat die Laufzeit \(T_p(n) = c_p \cdot n^2\) und \(q(n)\) die Laufzeit \(T_q(n) = c_q \cdot \log(n)\).
1Algorithmus COMPUTE(n)2p(n);3for j = 1...n do4for k = 1...j do5q(n);6end7end
Bestimmen Sie die asymptotische Laufzeit des Algorithmus in Abhängigkeit von \(n\) durch zeilenweise Analyse.
„Naive“ Power Funktion
Bestimmen Sie die algorithmische asymptotische Komplexität des folgenden Algorithmus durch Analyse jeder einzelnen Zeile. Jede Zeile kann für sich mit konstantem Zeitaufwand abgeschätzt werden. Bestimmen Sie die Laufzeitkomplexität für den schlimmstmöglichen Fall in Abhängigkeit von \(k\) für eine nicht-negative Ganzzahl \(n\) mit \(k\) Bits.
(Beispiel: die Zahl \(n = 7_d\) benötigt drei Bits \(n= 111_b\), die Zahl \(4d\) benötigt zwar auch drei Bits \(100_b\) aber dennoch weniger Rechenschritte.).
1Algorithmus Power(x,n)2r = 13for i = 1...n do4r = r * x5return r
Effizientere Power Funktion
Bestimmen Sie die algorithmische asymptotische Komplexität des folgenden Algorithmus durch Analyse jeder einzelnen Zeile. Jede Zeile kann für sich mit konstantem Zeitaufwand abgeschätzt werden. Bestimmen Sie die Laufzeitkomplexität mit Indikator \(t_i\) für gesetzte Bits in \(n\) für den schlimmstmöglichen Fall in Abhängigkeit von \(k\) für eine nicht-negative Ganzzahl \(n\) mit \(k\) Bits.
(D. h. \(t_i = 1\), wenn der i-te Bit von \(n\) gesetzt ist, sonst ist \(t_i = 0\); sei \(n = 5_d = 101_b\) dann ist \(t_1 = 1, t_2 = 0, t_3 = 1\)).
1Algorithmus BinPower(x,n)2r = 13while n > 0 do4if n mod 2== 1 then5r = r * x6n = (n-1)/27else8n = n/29x = x *x10return r
1gW = [ (1, 1), (3, 4), (5, 8), (2, 3) ] # [(Gewicht, Wert)...]23def bestWertRekursiv(n):4best = 05for i in range(len(gW)):6(gewt,wert) = gW[i]7if n >= gewt:8test = wert + bestWertRekursiv(n - gewt)9if test > best:10best = test11return best1213print(bestWertRekursiv(5)) # max. Traglast ist hier zu Beginn n = 5
Für Komplexität nehmen wir jetzt die häufigste Aktion her; hier die Additionen.
Bei der Rekursion ergibt sich (\(m\) = Anzahl der verschiedenen Objekte):
Im schlimmsten Fall sind alle \(g_i = 1\).
Pro Aufruf \(m\) weitere Aufrufe.
(D. h. auf erster Ebene haben wir \(m\) Additionen, auf der zweiten Ebene \(m^2\) Additionen, usw.)
Erklärungen
Grobe Idee: Wir gehen in der Methode bestWertRek über alle Elemente und probieren aus ob wir diese einmal in den Rucksack packen können, d. h. die (verbleibende) Traglast ausreicht. Falls ja, dann führen wir einen rekursiven Aufruf durch bei dem wir die Traglast entsprechende reduziert haben.
Details: Für jedes Element entscheiden wir, ob es noch in den Rucksack passt (Zeile 7). Falls ja, dann wird der Wert des Elements addiert und die Traglast um das Gewicht des Elements reduziert (Zeile 8: n - gewt). Anschließend wird rekursiv der bester Wert für den kleineren Rucksacks berechnet.
Grundsätzliche Idee der iterativen Lösung
Gehe über alle Objekte. Berechne in jedem Schleifendurchlauf i bei Hinzunahme von Teil i das jeweils das beste Ergebnis für alle Kapazitäten bis inklusive n.
Beispiel
Verfügbare Objekte (\((Gewicht,Wert)\)): \(A = \{(1,1),(3,4),(5,8),(2,3)\}\). Sei die maximale Traglast \(n = 7\):
j\i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|---|---|---|---|---|---|---|---|---|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
0 |
1 |
2 |
4 |
5 |
6 |
8 |
9 |
2 |
0 |
1 |
2 |
4 |
5 |
8 |
9 |
10 |
3 |
0 |
1 |
3 |
4 |
6 |
8 |
9 |
11 |
Implementierung
1gW = [ (1, 1), (3, 4), (5, 8), (2, 3) ] # (Gewicht, Wert)23def bestWertIterativ(n):4best = [0] * (n + 1) # best[i] = bester Wert für Traglast i5for i in range(len(gW)):6(gewt, wert) = gW[i]7for j in range(gewt, n + 1):8test = best[j - gewt] + wert9if test > best[j]:10best[j] = test1112return best[n]1314print(bestWertIterativ(5)) # max. Traglast ist hier zu Beginn n = 5
start = time.time() r = f() end = time.time() print("It took" + str((end-start))) return r
Bei der Iterationen ergibt sich:
Zwei Schleifen über \(m\) und \(n\):
Erklärungen
Grobe Idee: Wir gehen in der Methode bestWertIterativ über alle Objekte (Zeile 5). In der inneren Schleife (Zeile 7) iterieren wir über die Traglasten, die das Objekt – ggf. auch mehrfach – aufnehmen könnten (range(gewt, n + 1)). Für jede dieser Traglasten prüfen wir ob es vorteilhaft ist das Objekt in den Rucksack zu packen. Falls ja, dann wird der aktuell beste Wert für die Traglast aktualisiert.
D. h. wir legen zum Beispiel ein Objekt mit dem Gewicht 2 bei einer verbleibenden Traglast von 5 ggf. (implizit) mehrfach in den Rucksack dadurch, dass wir bereits den besten Wert für die kleineren Traglasten kennen.
Die iterative Variante ist wegen der vermiedenen Berechnung gleicher Werte – aufgrund der Verwendung von dynamischer Programmierung – praktisch immer schneller. Dies könnte bei Rekursion ggf. mit Caching erreicht werden.
Wieso ist das Rucksackproblem dann aber als NP-vollständig klassifiziert?
Die Analyse erfolgte nicht über die Wortlänge (als Eingabegröße); d. h. \(n\) (Kapazität bzw. Tragkraft) entspricht nicht der Wortlänge. Ein Binärwort \(n\) mit \(k\) Zeichen hat zum Beispiel bis zu \(2^k-1\) Werte.
Die Wortlänge eines Problems bezeichnet hier die Anzahl der Bits, die benötigt werden, um die Eingabe eines Problems darzustellen. Sie ist ein Maß dafür, wie groß oder komplex die Darstellung der Eingabedaten ist.
Die iterative Variante mit dynamischer Programmierung hat eine Laufzeit von O(m⋅n) wobei n hier die Kapazität in Gewichtseinheiten ist, nicht die Wortlänge. Wenn n exponentiell groß ist, wird der Algorithmus ineffizient, da die Eingabegröße \(\lceil log_2 N\rceil \) viel kleiner ist als N selbst. (D. h. wenn die Kapazität 10 ist, dann brauchen wir 4 Bits, um die Kapazität darzustellen, wenn die Kapazität jedoch 1000 (100 mal größer) ist, dann brauchen wir 10 Bits (d. h. nur 2,5 mal so viele Bits.)
Standardverfahren zur Analyse rekursiver Algorithmen:
Anwendung der Verfahren zur Analyse iterativer Algorithmen um die Rekurrenzgleichung zu bestimmen.
Eine Anzahl von Werten ausrechnen und auf sinnvollen Zusammenhang schließen.
Beweis des Zusammenhangs mit vollständiger Induktion.
Dieses Verfahren haben wir bei den Türmen von Hanoi angewandt.
Teilende Verfahren, bzw. Divide-and-Conquer-Algorithmen, sind typischerweise sehr effizient.
Wird beispielsweise das Problem immer halbiert, ist also \(a_{2n} = a_n + 1\) und ist \(a_1 = 1\), dann würde für die Folgenglieder gelten \(a_1 = 1, a_2 = 2, a_4 = 3, a_8 = 4, a_{16} = 5, ...\).
Verallgemeinert: \(a_n = \log_2(n) +1\).
Herleitung:
\(a_1 = \log_2(1) + 1 = 0 + 1\)
\(a_{2n} = a_n + 1 = \log_2(n) + 1 + 1 = \log_2(n) + \log_2(2) + 1 = \log_2(2n) + 1\)
Ein Beispiel ist binäre Suche nach einem Namen im Telefonbuch oder nach einer zu erratenden Zahl.
Bei der Herleitung wurde (wieder) vollständige Induktion angewandt und die Logarithmusgesetze genutzt: \(\log(a) + \log(b) = \log(a \cdot b)\) sowie \(\log_bb= 1\).
In vielen Fällen geben rekursiv teilende Algorithmen Grund zur Hoffnung, dass die Laufzeit einen relevanten logarithmischen Anteil hat.
Häufig können die Rekurrenz-Gleichungen rekursiv teilender Algorithmen in folgende Form gebracht werden:
Sei:
\(a\): die Anzahl der rekursiven Aufrufe,
\({n \over b}\): die Größe jedes rekursiven Unterproblems wobei \(b\) die Anzahl der Teile ist in die das Problem geteilt wird,
\(f(n)\): der Aufwand während der Ausführung.
In diesem Fall können drei Fälle unterschieden identifiziert werden:
Ist der Aufwand \(f(n)\) vernachlässigbar gegenüber dem Aufwand der weiteren Aufrufe, so ist ein rein durch die Rekursion bestimmtes Verhalten zu erwarten.
Entspricht der Aufwand \(f (n)\) genau dem Aufwand der weiteren Aufrufe, so vervielfältigt sich der Aufwand gegenüber dem 1. Fall, bleibt aber in der gleichen Größenordnung.
Ist der Aufwand \(f (n)\) größer als der Aufwand der verbleibenden Aufrufe, so wird der Aufwand asymptotisch von \(f (n)\) dominiert.
Beispiel für den 1. Fall
Bei \(a = 1\) und \(b= 2\) — wie bei der binären Suche — ist somit logarithmisches Verhalten zu erwarten. Wird hingegen ein \(b= 2\) halbiertes Feld \(a = 4\) viermal aufgerufen, so ist ein quadratisches Verhalten zu erwarten.
Das Master-Theorem ist ein Werkzeug zur Analyse der Zeitkomplexität von rekursiven Algorithmen, die mit Hilfe von Rekurrenzgleichungen der Form \(T(n) = a \cdot T\left({n \over b}\right) + f(n)\) beschrieben werden können.
Anwendungsgebiet sind insbesondere Teile-und-Herrsche Algorithmen.
Das Master-Theorem hat drei Fälle, die auf dem Vergleich zwischen \(f(n)\) und \(n^{\log_b a}\) basieren und die asymptotische Komplexität von \(T(n)\) bestimmen. Wobei \(n^{\log_b a}\) die Laufzeit für die Rekursion selbst beschreibt:
Seien \(a >0\) und \(b >1\) Konstanten und \(f : \mathbb{N} \rightarrow \mathbb{N}\):
Wenn \(f(n) \in O(n^{\log_b a - \epsilon})\) für ein \(\epsilon > 0\) gilt – d. h. wenn \(f(n)\) langsamer wächst als \(n^{\log_b a}\) – dann dominiert die Rekursion, und es gilt: \(T(n) \in \Theta(n^{\log_b a})\).
Wenn \(f(n) \in \Theta(n^{\log_b a} \cdot (\log n)^k)\) für ein \(k \geq 0\) gilt – d. h. wenn \(f(n)\) und \(n^{\log_b a} \cdot (\log n)^k\) gleich schnell wachsen – dann tragen beide Teile zur Gesamtkomplexität bei, und es gilt: \(T(n) \in \Theta(n^{\log_b a} \cdot (\log n)^{k+1})\).
Wenn \(f(n) \in \Omega(n^{\log_b a + \epsilon})\) für ein \(\epsilon > 0\) gilt und weiterhin gilt \(af(n/b) \leq c f(n)\) für eine Konstante \(c < 1\) und ein hinreichend großes \(n\) – d. h. wenn also \(f(n)\) schneller wächst als \(n^{\log_b a}\) – dann dominiert \(f(n)\) die Komplexität, und es gilt: \(T(n) \in \Theta(f(n))\).
Viele Sortieralgorithmen sind zum Beispiel Teile-und-Herrsche Algorithmen.
Im Mastertheorem erfolgt der Vergleich ggf. mit \(n^{(\log_ba)\pm\epsilon}\) und nicht mit \(n^{\log_b (a\pm\epsilon)}\).
\(T (n) = 2T (n/2) + n \log_2 n\)
\(a = 2\), \(b = 2\) und \(n^{\log_2 2} = n\)
Es liegt Fall 2 vor, da \(f(n) = n \cdot (\log_2n)^{k=1} \in \Theta(n^{\log_b a} \cdot (\log n))\).
Die Laufzeit beträgt somit \(T(n) = \Theta(n \cdot (\log_2 n)^2)\).
Der Wechsel der Basis des Logarithmus ist möglich, da sich die Basis nur um einen konstanten Faktor unterscheidet:
\(\log_\textcolor{blue}{a} \textcolor{red}{x} = \frac{ 1 }{ \log_b \textcolor{blue}{a}} \cdot \log_b \textcolor{red}{x}\)
\(T (n) = 9T (n/3) + 2n\)
\(a = 9\), \(b = 3\) und \(n^{\log_3 9} = n^2\)
Es liegt Fall 1 vor, da \(f(n) = 2n \in O(n^{\log_3 9 - \epsilon})\).
Die Laufzeit beträgt somit \(T(n) = \Theta(n^2)\).
\(T (n) = 2T (n/3) + n\)
\(a = 2\), \(b = 3\) und \(n^{\log_3 2}\), \(log_32 \approx 0,63 < 1\)
Es liegt Fall 3 vor, da \(f(n) = 2n \in \Omega(n^{\log_3 2 + \epsilon})\) und
\(af(n/b) = 2n/3 \leq c \cdot n\) für \(1 > c \geq 2/3\).
Die Laufzeit beträgt somit \(T(n) = \Theta(n)\).
Das Master-Theorem hilft also, die asymptotische Komplexität von Algorithmen schnell zu bestimmen, ohne dass eine detaillierte Analyse der Rekurrenz erforderlich ist.
f(n) ist konstant
Gegeben sei: \(T (n) = 2T (n/4) + 1\)
Bestimmen Sie die Laufzeit des Algorithmus mit Hilfe des Master-Theorems.
f(n) ist die Quadratwurzel
Gegeben sei: \(T (n) = 3T (n/9) + \sqrt{n}\)
Bestimmen Sie die Laufzeit des Algorithmus mit Hilfe des Master-Theorems.
a=1 und f(n) sind konstant
Gegeben sei: \(T (n) = T (n/2) + 1\)
Bestimmen Sie die Laufzeit des Algorithmus mit Hilfe des Master-Theorems.
Anwendung des Master-Theorems auf Mergesort
Der Mergesort-Algorithmus ist ein rekursiver Algorithmus, der ein Array in zwei Hälften teilt, die Hälften sortiert – wenn sie nicht trivial sind – und dann die sortierten Hälften zusammenführt. Das Zusammenführen der Hälften hat einen Aufwand von \(n\) und das Teilen des Arrays hat einen konstanten Aufwand.
Bestimmen Sie die Rekurrenzgleichung für den Mergesort-Algorithmus.
Bestimmen Sie die Laufzeit des Mergesort-Algorithmus mit Hilfe des Master-Theorems.