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= 

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

  - Festlegen 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ä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

<language>Javascript</language>
=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 = -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$$