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:

  - Festlegung auf Norm nur schwer moglich
  - Ergebnisse lassen sich nur schwer übertragen
  - Speicherbegrenzung

=5. Zeitkomplexität=

die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung eines Problems benötigt, in Abhängigkeit von der Länge der Eingabe


  - 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>
<language>Java</language>
=8. O-Notation=

beschreibt den Aufwand eines algorithmus. 


$$O(f) = {T | T: N → R_0^+ und ∃c ∈ R^+ ∃n_0 ∈ N ∀n ≥ n_0: T(n) ≤ c·f(n)}$$
- Eine Funktion f liegt in O(g), wenn sie ab einem bestimmten "Zeitpunkt" unterhalb von g liegt

O(1) 
- die Laufzeit des algorithmus benötigt immer die selbe Zeit/Speicher

<code id="5260e714332cc">boolean isFirstElementNull(String[] strings) {
    if (strings[0] == null) {
        return true;
    }
    return false;
}</code>

O(N)
- die Laufzeit des algorithmus wachst linear in direkter Proportionalität zur Größe der Eingabedaten

<code id="5260e7143336d">boolean containsValue(int[] values, int value) {
    for (int i = 0; i < values.length; i++) {
        if (value == values[i]) { // always the same time!
            return true;
        }
    }
    return false;
}</code>

O($2^N$)
- die laufzeit des algorithmus verdoppelt sich für jedes weitere element der Eingabedaten

<code id="5260e714333e6">public static void permutation(String str) {
    permutation("", str);
}
 
private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i),
                str.substring(0, i) + str.substring(i+1, n));
        }
    }
}</code>

O($N^2$)
- die Laufzeit des algorithmus ist direkt proportional zum Quadrat der Größe der Eingabedaten

<code id="5260e7143345a">boolean containsDuplicates(int[] values) {
    for (int i = 0; i < values.length; i++) {
        for (int j = 0; j < values.length; j++) {
            if (i == j) { // don't compare self
                continue;
            }
            if (values[i] == values[j]) {
                return true;
            }
        }
    }
    return false;
}</code>

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