Aus ProgrammingWiki

Inhaltsverzeichnis 1 1. Effizienz eines Algorithmus 2 2. Laufzeit 2.1 effizienz eines programms hängt ab von 3 3. Vergleichen der Laufzeit 4 4. Messen der Laufzeit 5 5. Zeitkomplexität 6 6. Lineares Suchen 7 7. Beispiele effizienter algorithmen 8 8. O-Notation 8.1 Komplexitätsklassen 9 9. Gaußklammer(Abrundungsfunktion) 9.1 Eigenschaften

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

i = 0; while (i < n) && (a[i] != x) { i++; }

- 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)

boolean isFirstElementNull(String[] strings) { if (strings[0] == null) { return true; } return false; }

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

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; }

O($2^N$) - die laufzeit des algorithmus verdoppelt sich für jedes weitere element der Eingabedaten(exponentieller Aufwand)

- anwendung - Optimierungsprobleme

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)); } } }

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)

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; }

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$$