Effizienz von Algorithmen WS13-14
Aus ProgrammingWiki
Archivierte Version vom 2013-10-11T14:12:23+00:00. Aktuelle Version
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
T(n) - 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
3
effizienz eines programms hängt ab von
- komplexität des algorithmus - umsetzung des algorithmus in das programm - effizienz des vom Übersetzer erzeugten Objektcodes
4
Messen und Vergleichen der Laufzeit
- Wann ist ein Algorithmus besser als ein anderer? - Was sind gute/schlechte Algorithmen? - Gibt es einen optimalen Algorithmus? - Laufzeit messen und vergleichen ???
Probleme - unterschiedliche Betriebssysteme - unterschiedlich schnelle Hardware - unterschiedliche Eingabedarstellungen
5
Messen der Laufzeit:
- Implementieren in einer konkreten Sprache/Compiler. - Festgelegt bei Ausfuhrung: Rechner/Eingabemenge.
Probleme:
- Festlegen auf Norm nur schwer moglich. - Ergebnisse lassen sich nur schwer ubertragen. - Aussage uber Skalierung basiert auf Vermutung. - Speicherbegrenzung
6
Man unterscheidet bei der Effizienz zwischen:
- Worst-Case – das schlechtestmögliche Verhalten - Average-Case – das durchschnittliche Verhalten - Best-Case – das bestmögliche Verhalten
7
Beispiele effizienter algorithmen
- Quiksort - Heapsort - Binäre Suche - Boyer-Moore-Algorithmus
8
Gaußklammer(Abrundungsfunktion)
Für jede reelle Zahl x ist [x] die größte ganze Zahl, die kleiner oder gleich x ist
beispiele
\lfloor 5,7 \rfloor = 5 \lfloor 1,3 \rfloor = 1
9
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-sind m \in \Z und n \in \N, so gilt
\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