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

=5=
Messen der Laufzeit:

  - Implementierung in einer konkreten Sprache/Compiler
  - Rechner/Eingabemenge festlegen

Probleme:

  - Festlegen auf Norm nur schwer moglich
  - Ergebnisse lassen sich nur schwer übertragen
  - 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=
Lineares Suchen
	
  bestimme die position von x in einer wertefolge
	
  - best-case - x ist erstes element         T(min) = 1
  - worst case - x ist letztes element       T(max) = n
  - average-case - erwartungswert über alle möglichen Fälle
		$$T(mit) = 1/n + 2/n + 3/n + ••• + n/n = (1 + 2 + 3 + ••• + n)/n = (n+1)/2$$

=8=
Beispiele effizienter algorithmen

  - Quiksort
  - Heapsort
  - Binäre Suche
  - Boyer-Moore-Algorithmus

=9=
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



=10=
Gaußklammer(Abrundungsfunktion)

Für jede reelle 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$$

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