AuK/Effizienz von Algorithmen WS13-14

Wiki-Quelltext dieser Seite.

=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 erzeugten Objektcodes

=4=
Vergleichen der Laufzeit

  - Wann ist ein Algorithmus besser als ein anderer?
  - Gibt es einen optimalen Algorithmus?

  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=
O-Notation

beschreibt die Laufzeit eines algorithmus. 

O(1) 
- der 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 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$$

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