Effizienz von Algorithmen WS13-14
Inhaltsverzeichnis |
1. Effizienz eines Algorithmus
- ein algorithmus ist effizient wenn es ein problem mit möglichst wenig ressourcenaufwand löst.
- Laufzeiteffizienz - Speichereffizienz - "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) - aufwand der einzelschritte
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? - Gibt es einen optimalen Algorithmus?
Probleme - unterschiedliche Betriebssysteme - unterschiedlich schnelle Hardware
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
5. Zeitkomplexität
Man unterscheidet bei der Effizienz zwischen:
- Worst-Case – das schlechtestmögliche Verhalten - Average-Case – das durchschnittliche Verhalten - Best-Case – das bestmögliche Verhalten
6. Lineares Suchen
bestimme die position von x in einer wertefolge
- 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älleT_{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 → R0+ und ∃c ∈ R+ ∃n0 ∈ N ∀n ≥ n0: T(n) ≤ c·f(n)}O(1) - die Laufzeit des algorithmus benötigt immer die selbe Zeit/Speicher
O(N) - die Laufzeit des algorithmus wachst linear in direkter Proportionalität zur Größe der Eingabedaten
O(2^N) - die laufzeit des algorithmus verdoppelt sich für jedes weitere element der Eingabedaten
O(N^2) - die Laufzeit des algorithmus ist direkt proportional zum Quadrat der Größe der Eingabedaten
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 = -4Eigenschaften
- 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