AuK/Effizienz von Algorithmen WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
=1. Effizienz eines Algorithmus=
- ein algorithmus ist effizient wenn es ein problem mit möglichst wenig ressourcenaufwand löst.
- Laufzeiteffizienz - Das Programm soll möglichst schnell laufen
- steht die Laufzeit im akzeptablen Verhältniss zur Aufgabe?
- Speichereffizienz - Code und Daten sollen möglichst kompakt sein
- wird der Speicherplatz effizient genutzt?
- "kognitive Effizienz"
=2. Laufzeit=
- die anzahl der elementaren Operationen, die der algorithmus durchläuft , um eine Eingabe zu bearbeiten
Laufzeit (T) ist abhängig von
- Problemgröße (n)
- T ist Funktion von n: T(n)
- aufwand der einzelschritte
- abhängig vom übersetzer und von der Hardware
==effizienz eines programms hängt ab von==
- komplexität des algorithmus
- umsetzung des algorithmus in das programm
- effizienz des erzeugten Objektcodes
=3. Vergleichen der Laufzeit=
- Wann ist ein Algorithmus besser als ein anderer?
- Wie bewerten/vergleichen wir Algorithmen?
- Was sind gute/schlechte Algorithmen?
- Gibt es einen optimalen Algorithmus?
Laufzeit messen und vergleichen?
Probleme
- unterschiedliche Betriebssysteme
- unterschiedlich schnelle Hardware
- unterschiedliche Eingabedarstellungen/Datenstrukturen
=4. Messen der Laufzeit=
- Implementierung in einer konkreten Sprache/Compiler
- Rechner/Eingabemenge festlegen
Probleme:
- Festlegung auf Norm nur schwer moglich
- Ergebnisse lassen sich nur schwer übertragen
- Speicherbegrenzung
- Aussage über Skalierung basiert auf Vermutung
Messen und Vergleichen der Laufzeiten ist nicht praktikabel oder sinnvoll!
=5. Zeitkomplexität=
die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung eines Problems benötigt, in Abhängigkeit von der Länge der Eingabe
- Worst-Case – das schlechtestmögliche Verhalten - ist eine obere Schranke für die maximale Anzahl der Schritte,die ein Algorithmus benötigt,um Eingaben der
Größe n zu bearbeiten
- Average-Case – das durchschnittliche Verhalten - ist die mittlere Anzahl von Schritten,die ein Algorithmus benötigt,um eine Eingabe der Größe n zu bearbeiten - vorraussetzung: arithmetischer Mittelwert
Probleme:
- Worüber bildet man den Durchschnitt?
- Sind alle Eingaben der Länge n gleich wahrscheinlich?
- Technisch oft sehr viel schwieriger durchzuführen als die worst-case Analyse
- Best-Case – das bestmögliche Verhalten
=6. Lineares Suchen=
bestimme die position von x in einer wertefolge
<code id="526153d541a62">i = 0;
while (i < n) && (a[i] != x) {
i++;
}</code>
- best-case - x ist erstes element $T_{min} (n) = 1$
- worst case - x ist letztes element $T_{max}(n) = n$
- average-case - erwartungswert über alle möglichen Fälle
$T_{mit}(n) = 1/n + 2/n + 3/n + ••• + n/n = (1 + 2 + 3 + ••• + n)/n = (n+1)/2$
=7. Beispiele effizienter algorithmen=
- Quiksort
- Heapsort
- Binäre Suche
- Boyer-Moore-Algorithmus
=8. O-Notation=
beschreibt den Aufwand eines algorithmus.
$$O(f) = {T | T: N → R_0^+ und ∃c ∈ R^+ ∃n_0 ∈ N ∀n ≥ n_0: T(n) ≤ c·f(n)}$$
- Eine Funktion f liegt in O(f), wenn sie ab einem bestimmten "Zeitpunkt" unterhalb von f liegt
==Komplexitätsklassen==
O(1)
- die Laufzeit des algorithmus benötigt immer die selbe Zeit/Speicher(konstanter Aufwand)
- anwendung - Suchverfahren für Tabellen (Hashing)
<code id="5260e714332cc">boolean isFirstElementNull(String[] strings) {
if (strings[0] == null) {
return true;
}
return false;
}</code>
O(N)
- die Laufzeit des algorithmus wachst linear in direkter Proportionalität zur Größe der Eingabedaten(linearer Aufwand)
- anwendung - Sequenzielle Suche, Suche in Texten
<code id="5260e7143336d">boolean containsValue(int[] values, int value) {
for (int i = 0; i < values.length; i++) {
if (value == values[i]) { // always the same time!
return true;
}
}
return false;
}</code>
O($2^N$)
- die laufzeit des algorithmus verdoppelt sich für jedes weitere element der Eingabedaten(exponentieller Aufwand)
- anwendung - Optimierungsprobleme
<code id="5260e714333e6">public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
System.out.println(prefix);
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i),
str.substring(0, i) + str.substring(i+1, n));
}
}
}</code>
O($N^2$)
- die Laufzeit des algorithmus ist direkt proportional zum Quadrat der Größe der Eingabedaten(quadratischer Aufwand)
- anwendung - dynamische Optimierungsverfahren, Multiplikation Matrix-Vektor (einfach)
<code id="5260e7143345a">boolean containsDuplicates(int[] values) {
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < values.length; j++) {
if (i == j) { // don't compare self
continue;
}
if (values[i] == values[j]) {
return true;
}
}
}
return false;
}</code>
=9. Gaußklammer(Abrundungsfunktion)=
Für jede Zahl x ist $\lfloor x \rfloor$ die größte ganze Zahl, die kleiner oder gleich x ist
beispiele
$$\lfloor 5,7 \rfloor = 5$$
$$\lfloor 1,3 \rfloor = 1$$
$$\lfloor -3,4 \rfloor = -4$$
==Eigenschaften==
- für jede ganze Zahl $k$ und jede reelle Zahl $x$
$$\lfloor x+k \rfloor = \lfloor x \rfloor + k$$
$$\lfloor 3,44 + 2 \rfloor = \lfloor 3,44 \rfloor + 2$$
$$5 = 5$$
- für alle reellen Zahlen $x$, $y$
$$\lfloor x \rfloor + \lfloor y\rfloor \le \lfloor x + y \rfloor \le \lfloor x \rfloor + \lfloor y \rfloor + 1$$
$$\lfloor 4,7 \rfloor + \lfloor 2,4 \rfloor \le \lfloor 4,7 + 2,4 \rfloor \le \lfloor 4,7 \rfloor + \lfloor 2,4 \rfloor + 1$$
$$6 \le 7 \le 7$$
- für jede ganze Zahl $k$ und jede natürliche Zahl $n$
$$\left\lfloor \frac{k}{n} \right\rfloor \ge \frac{k-n+1}{n}$$
$$\left\lfloor \frac{10}{5} \right\rfloor \ge \frac{10-5+1}{5}$$
$$2 \ge 1,2$$
-ist $m$ eine ganze Zahl und $n$ eine natürliche Zahl
$$\left\lfloor\frac{x+m}{n}\right\rfloor = \left\lfloor\frac{\lfloor x\rfloor +m}{n}\right\rfloor$$
$$\left\lfloor\frac{3,1+7}{2}\right\rfloor = \left\lfloor\frac{\lfloor 3,1\rfloor +7}{2}\right\rfloor$$
$$5 = 5$$