Auf dieser Seite wird das Thema Komplexität behandelt.
Gegeben ist ein zu lösendes Problem. Es ist wünschenswert, dass der Algorithmus zur Berechnung der Lösung einen möglichst geringen Aufwand hat. Daher wird der Aufwand des Algorithmus (Komplexität) abgeschätzt . Zur Lösung von Problemen einer bestimmten Klasse gibt es einen Mindestaufwand.
Als Beispiel nutzen wir die sequentielle Suche in Folgen.
Gegeben ist die Zahl b und n Zahlen, z.B. mit A[0...n-1] mit n>0, wobei die Zahlen verschieden sind. Gesucht ist ein Index , falls der Index existiert, sonst ist i = n.
Die Lösung für das Problem ist:
i=0;while(i<n&&b!=A[i])i++;
Der Aufwand der Suche hängt nun von der Eingabe ab, d.h vom gewählten Wert n, den Zahlen A[0],...,A[n] und von b. Es gibt zwei Möglichkeiten, eine erfolgreiche oder eine erfolglose Suche. Eine erfolgreiche Suche haben wir, wenn b=A[i] dann ist S=i+1 Schritte. Ist die Suche jedoch erfolglos, dann ist S=n+1 Schritte. Das Problem ist, dass die Aussage von zu vielen Parametern abhängt und unser Ziel ist eine globale Aussage zu finden, die nur von einer einfachen Größe abhängt, z.B. der Länge n der Folge.
Im schlechtesten Fall wird b erst im letzten Schritt gefunden, d.h. b=A[n-1]. Dann wäre S=n.
Im Mittel wird die Anwendung mit verschiedenen Eingaben wiederholt. Wenn man beobachtet wie oft b an erster, zweiter,..., letzter Stelle gefunden wird, hat man eine Annahme über die Häufigkeit. Läuft der Algorithmus k mal (k>1), so wird b gleich oft an erster, zweiter,....,letzter Stelle gefunden und somit k/n mal an jeder Stelle.
Die Anzahl der Schritte insgesamt für k Suchvorgänge lässt sich folgendermaßen berechnen:
Für eine Suche benötigt man Schritte
Daraus folgt, dass im Mittel ( bei einer Gleichverteilung)
Zur Analyse der Komplexität geben wir eine Funktion als Maß für den Aufwand an. . Das bedeutet f(n)=a bei Problemen der Größe n beträgt der Aufwand a. Die Problemgröße ist der Umfang der Eingabe, wie z.B. die Anzahl der zu sortierenden oder zu durchsuchenden Elemente. Der Aufwand ist die Rechenzeit( Abschätzung der Anzahl der Operationen, wie z.B. Vergleiche) und der Speicherplatz.
Die Aufwandsfunktion ist meist nicht exakt bestimmbar. Daher wird der Aufwand im schlechtesten Fall und im mittleren Fall abgeschätzt und die Größenordnung ungefähr errechnet.
Wie können wir das Wachstum von Funktionen abschätzen und wie verhalten sich die Funktionen zueinander?
Das Ziel ist, die Funktion zu wählen, die nach oben beschränkt.
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3 zu finden.
Auf dieser Seite wird die O-Notation behandelt.
Bei der O-Notation werden die asymptotischen oberen Schranke für Aufwandsfunktion angegeben. Das heißt deren Wachstumsgeschwindigkeit bzw. Größenordnung.
Eine Asymptote ist eine Gerade, der sich eine Kurve bei immer größer werdender Entfernung vom Koordinatenursprung unbegrenzt nähert. Eine einfache Vergleichsfunktion ist für Aufwandsfunktionen mit
Für eine Funktion ist die Menge wie folgt definiert:
Anschaulich formuliert bedeutet das, dass O(f(n)) die Menge aller durch f nach oben beschränkter Funktionen ist und somit die asymptotische obere Schranke ist.
Die Definition veranschaulichst sieht folgendermaßen aus:
Das heißt g wächst nicht schneller als f. Das bedeutet wiederrum ist für genügend große n durch eine Konstante c nach oben beschränkt.
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3.2 zu finden.
Für eine Funktion ist die Menge wie folgt definiert:
Anschaulich formuliert bedeutet das, dass die Menge aller durch f nach unten beschränkter Funktionen ist und somit die asymptotische untere Schranke ist.
Anschaulich formuliert bedeutet das, dass die Menge aller durch f nach unten und oben beschränkter Funktionen und somit die asymptotische untere und obere Schranke ist.
Wir sagen sei
Und wir sagen, ein Algorithmus mit Komplexität f(n) benötigt höchstens polynomielle Rechenzeit, falls es ein Polynom p(n) gibt, mit .
Des weiteren sagen wir, dass ein Algorithmus höchstens exponentielle Rechenzeit benötigt, falls es eine Konstante gibt, mit .
Die Komplexitätsklassen sind:
der konstante Aufwand, das bedeutet der Aufwand ist nicht abhängig von der Eingabe
Nun stellen wir uns die Frage, wie groß bezüglich der Rechenschritte darf, oder kann ein Problem sein, je nach Komplexitätsklasse, wenn die Zeit T begrenzt ist? Wir nehmen an, dass wir pro Schritt eine Rechenzeit von brauchen.
In der folgenden Tabelle steht T für die Zeitbegrenzung und G für die maximale Problemgröße.
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3.3 zu finden.
Aufwandsanalyse von iterativen AlgorithmenBearbeiten
Auf dieser Seite wird der Aufwand von iterativen Algorithmen analysiert.
Als Aufwand wird die Anzahl der durchlaufenen Operationen zur Lösung des Problems bezeichnet ( Zuweisungen, Vergleiche...). Häufig ist der Aufwand abhängig vom Eingabeparameter (Problemgröße). Die Aufwandsklasse sagt, wie der Aufwand in Abhängigkeit von der Problemgröße wächst. Doch wie kann man nun bei beliebigem Java Code die Aufwandsklasse bestimmen?
Hier ist die Aufwandsklasse O(n+log n). In jedem Durchlauf der äußeren Schleife wird m verdoppelt, d.h. sie läuft log n Mal. Die innere Schleife läuft bis n/2, aber nicht jedes Mal, weil i nur ein Mal auf 0 gesetzt wird. Man könnte als Aufwandsklasse auch O(n) sagen, da der Summand log n nicht ins Gewicht fällt.
Zum einen haben wir elementare Anweisungen wie Zuweisungen und Vergleiche. Diese haben einen Aufwand von 1.
Des Weiteren haben wir Sequenzen oder auch geschrieben. Die obere Grenze ist und die untere Grenze ist . Dabei ist der Aufwand, der bei der Ausführung von entsteht.
Ein weiterer Bestandteil ist die Selektion. . Hier ist die obere Grenze und die untere Grenze .
Außerdem haben wir Iterationen . Hierbei ist die obere und die untere Grenze die Anzahl der Schleifendurchläufe, und die untere Grenze . Doch wie ist der Aufwand für eine for-Schleife? Ein Beispiel ist . Die Antwort ist die Abbildung auf eine while-Schleife.
Hier hat die for-Schleife den Aufwand und die Initialisierung und das return wieder . Damit ergibt der sich Gesamtaufwand . Daraus folgt die Aufwandsklasse .
Zu den häufig verwendeten Faustregeln gehört, dass wenn wir keine Schleife haben, der Aufwand konstant ist. Eine weitere ist, dass bei einer Schleife immer ein linearer Aufwand vorliegt. Bei zwei geschachtelten Schleifen haben wir immer einen quadratischen Aufwand. Doch die Faustegeln gelten nicht ohne Ausnahmen. Besonders Acht geben muss man bei Aufwandsbestimmungen für Schleifen, bei mehreren Eingabevariablen, bei Funktionsaufrufen und bei Rekursionen.
Hier wächst die Laufvariable nicht linear an.Daher ist der Aufwand und wir haben die Aufwandsklasse .
Doch gibt es eine allgemeine Methodik zum Bestimmen des Schleifenaufwands?
for(inti=1;i<n;i=2*i){x=x+1;}
Schritt 1: Wie entwickelt sich hier die Laufvariable? Der Startwert i ist 1 und die Veränderung in jedem Schritt ist . Die Laufvariable entwickelt sich somit wie folgt:
Nach dem 1. Durchlauf
Nach dem 2. Durchlauf
Nach dem 3. Durchlauf
Nach dem k. Durchlauf
Schritt 2: Nach wie vielen Durchläufen wird die Schleife abgebrochen?
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3.4 zu finden.
Aufwandsanalyse von rekursiven AlgorithmenBearbeiten
Auf dieser Seite wird der Aufwand von rekursiven Algorithmen untersucht.
Die Frage ist nun, welche Aufwandklasse T(n) beschreibt. Dies könnten alle möglichen Aufwandsklassen sein. Methoden um dieses Problem zu lösen, sind die vollständige Induktion und das Master-Theorem.
Spezialfall Divide and Conquer AlgorithmusBearbeiten
Ein Divide-and-Conquer Algorithmus stellt im Allgemeinen eine einfache, rekursive Version eines Algorithmus dar und hat drei Schritte:
Divide: Unterteile das Problem in eine Zahl von Teilproblemen
Conquer: Löse das Teilproblem rekursiv. Wenn das
Teilproblem klein genug ist, dann löse das Teilproblem direkt (z.B. bei leeren oder einelementigen Listen)
Combine: Die Lösungen der Teilprobleme werden zu einer Gesamtlösung kombiniert.
Merge Sort ist beispielsweise ein Divide and Conquer Algorithmus.
Divide: Zerteile eine Folge mit n Elementen in zwei Folgen mit je n/2 Elementen.
Conquer: Wenn die resultierende Folge 1 oder 0 Elemente enthält, dann ist sie sortiert.Ansonsten wende Merge Sort rekursiv an.
Die Rekursionsgleichung von MergeSort beschreibt den Aufwand für den schlechtesten Fall.
Aber die Annahme, dass n eine geeignete ganze Zahl ist ergibt normalerweise das gleiche Ergebnis wie
eine beliebige Zahl mit Auf- bzw. Abrunden. Dies führt zur einfacheren Rekursionsgleichung:
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3.4 zu finden.
Auf dieser Seite wird die vollständige Induktion behandelt. Es handelt sich hierbei um eine rekursive Beweistechnik aus der Mathematik. Sie ist gut geeignet, um Eigenschaften von rekursiv definierten Funktionen zu beweisen.
Zunächst vermutet man eine Eigenschaft (z.B. Aufwandsklasse einer Rekursionsgleichung). Nun folgt der Induktionsanfang: Eigenschaft hält für ein kleines n. Als nächstes folgt der Induktionsschritt: Die Annahme ist, dass wir es bereits für ein kleineres n gezeigt haben und wenn die Eigenschaft für kleinere n hält, dann hält sie auch für das nächstgrößere n!
Nun wollen wir die obere Grenze für den Aufwand bestimmen. Unsere Vermutung ist, dass . Nun müssen wir zeigen, dass ( siehe Definition der O-Notation). Die vereinfachte Annahme lautet . Hierbei werden keine Spezialfälle behandelt und im Induktionsschritt wird von nach n gegangen.
Induktionsvermutung:
Induktionsschritt: Wir beweisen von
zu zeigende obere Grenze:
Rekursionsgleichung einsetzen:
Induktionsvermutung einsetzen:
Somit ist der Induktionsschritt erfolgreich, wenn .
Induktionsanfang
Wir zeigen die Induktionsvermutung für einen Anfangswert, am einfachsten ist es, dies für den Rekursionsabbruch zu zeigen.
Zu zeigende obere Grenze:
Rekursionsgleichung einsetzen:
Der Induktionsanfang ist erfolgreich, wenn ist. Doch wann können wir zeigen, dass ist? Für den Wert, den wir im Induktionsanfang gezeigt haben, also für und wenn .
Nun wollen wir die obere Grenze für den Aufwand bestimmen. Unsere Vermutung ist, dass . Nun müssen wir zeigen, dass . Die vereinfachte Annahme lautet .
Induktionsvermutung:
Induktionsschritt: Wir beweisen von
Das Problem ist nun, dass wir den Induktionsschritt für positive n zeigen wollen und nicht für negative, daher müssen wir neu ansetzen.
Induktionsvermutung:
Dabei gibt es folgenden Trick: Modifiziere die Induktionsvermutung, in dem ein kleineres Polynom addiert wird.
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.2.5 zu finden.
Auf dieser Seite wird das Master Theorem behandelt.
Die Mastermethode ist ein „Kochrezept“ zur Lösung von
Rekursionsgleichungen der Form:
mit den Konstanten , f(n) ist eine asymptotische, positive Funktion, d.h.
a steht dabei für die Anzahl der Unterprobleme.
n/b ist die Größe eines Unterproblems
T(n/b) ist der Aufwand zum Lösen eines Unterproblems (der Größe n/b)
f(n) ist der Aufwand für das Zerlegen und Kombinieren in bzw. von Unterproblemen
Bei der Mastermethode handelt es sich um ein schnelles Lösungsverfahren zur Bestimmung der
Laufzeitklasse einer gegebenen rekursiv definierten
Funktion. Dabei gibt es 3 gängige Fälle:
Fall 1: Obere Abschätzung
Fall 2: Exakte Abschätzung
Fall 3: Untere Abschätzung
Lässt sich keiner dieser 3 Fälle anwenden, so muss die Komplexität anderweitig bestimmt werden und
wir müssen Voraussetzungen für die Anwendung des
Mastertheorems überprüfen.
Dafür vergleicht man mit . Wir verstehen n/b als . Im Folgenden verwenden wir die verkürzte Notation .
Wenn und die Regularitätsbedingung für eine Konstante und genügend große n erfüllt. Daraus folgt, dass f(n) polynomiell schneller wächst als um einen Faktor und f(n) erfüllt die sogenannte Regularitätsbedingung. Damit haben wir die Lösung .
In jedem Fall vergleichen wir f(n) mit . Intuitiv kann man sagen, dass die Lösung durch die größere Funktion bestimmt wird.
Im zweiten Fall wachsen sie ungefähr gleich schnell. Im ersten und dritten Fall muss f(n) nicht nur kleiner oder größer als sein, sondern auch polynomiell kleiner oder größer um einen Faktor .
Der dritte Fall kann nur angewandt werden, wenn die
Regularitätsbedingung erfüllt ist.
Doch wozu wird die Regularitätsbedingung benötigt? Zur Erinnerung, im dritten Fall dominiert f(n) das Wachstum von T(n). Wir müssen an dieser Stelle sicherstellen, dass auch bei rekursivem Anwenden, also wenn die Argumente kleiner werden, T(n) von f(n) dominiert wird. Veranschaulicht heißt das:
für
Das Wachstum muss durch f(n) dominiert werden und darf f(n) nicht dominieren.
Die Regularitätsbedingung gilt wenn sie für f(n) und g(n) gilt auch für und auch für
Nachweis für
Voraussetzung ist, dass die Regularitätsbedingung für f(n) und g(n) gilt, d.h.:
Für gilt:
man wählt
und
Nachweis für
Voraussetzung ist, dass die Regularitätsbedingung für f(n) und g(n) gilt, d.h.:
Auf der ersten Ebene ist der Aufwand f(n), auf der zweiten Ebene und auf der dritten Ebene . Die Höhe des Baumes beträgt . Die Anzahl der Blätter berechnet sich durch und beträgt somit .
Fall 1:
Das Gewicht wächst geometrisch von der Wurzel zu den Blättern. Die Blätter erhalten einen konstanten Anteil des Gesamtgewichts.
Fall 2:
k ist 0 und das Gewicht ist ungefähr das Gleiche
auf jedem der Ebenen.
Fall 3:
Das Gewicht reduziert sich geometrisch von der Wurzel zu den Blättern. Die Wurzel erhält einen konstanten Anteil am Gesamtgewicht.
Auf dieser Seite wird das Thema Rekursionsbäume behandelt. Das allgemeine Problem ist, dass man zum Abschätzen von der Aufwandsklasse einer Rekursionsgleichung gute Vermutungen braucht. Doch wie kommt man darauf? Ein Ansatz ist die Veranschaulichung durch einen Rekursionsbaum. Die Aufwandsklasse wird dann durch die Rekursionsbaummethode bestimmt. Das ist sehr nützlich, um eine Lösung zu raten, die danach durch eine andere Methode (z.B. Induktion) gezeigt wird. Rekursionsbäume sind besonders anschaulich bei Divide-and-Conquer-Algorithmen.
Die Grundidee ist das wiederholte Einsetzen der
Rekursionsgleichung in sich selbst als Baum dargestellt. Das Ziel ist ein Muster zu erkennen.
Bei einem Rekursionsbaum beschreibt ein Knoten die Kosten eines Teilproblems. Die Blätter sind die Kosten der Basis fällt T(0) und T(1). Der Aufwand bestimmt sich aus der Summe über alle Ebenen.
1. Ebene
2. Ebene
3. Ebene
....
n. Ebene
Der Aufwand berechnet sich nun wie folgt:
Allgemein bestimmt sich der Aufwand T(n) durch die Summe des Aufwands je Ebene und des Aufwands der Blattebene.
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 8.3 zu finden.