Bewertung von Algorithmen

• Komplexität:
  • Größe der Eingabe sei beschrieben durch Parameter n
  • Beispiele für n
    • Zahl der Stellen der Eingabezahlen
    • Anzahl der zu bearbeitenden Werte
    • Zahl der Knoten in einem Graphen
  • Komplexität = Wachstum des Aufwands bei wachsendem n
  • Aufwand z.B.
    • Rechenzeit
    • Speicherbedarf
    • Ein-/Ausgabe-Operationen
  • genauer Aufwand von Rechnertyp, Betriebssystem u.v.a abhängig
  • Bestimmung der Komplexität
    • meistens nur wichtigster Term für großes n
    • teilweise erheblicher mathematischer Aufwand erforderlich
  • Beispiel "Addition zweier großer Zahlen":
    • Zeitaufwand ~ n
    • geschrieben O(n)
  • Beispiel "Multiplikation großer Zahlen":
    • Zeitaufwand ~ n²
    • geschrieben O(n²)
  • hängt manchmal von den speziellen Eingabewerten ab
• Zeitaufwand beim Sortieren:
  • Bubblesort
    • minimal 1 Durchgang (Liste ist schon sortiert) → O(n)
    • maximal n Durchgänge (kleinstes Element unten) → O(n²)
    • Mittelwert über alle Reihenfolgen: O(n²)
  • Quicksort
    • hängt von guter Wahl des "mittleren Elements" ab
    • schlechtester Fall: O(n²)
    • mittlerer Fall: O(n log(n))
  • Vergleich der Größenordnungen, wenn 10⁶ Schritte 1s brauchen:

    • n	Zeit bei n log(n)	Zeit bei n2
      102	0.5 ms	10 ms
      103	6.9 ms	1 s
      104	92 ms	1.7 m
      105	1.2 s	2.8 h
      106	13.8 s	11.6 d

  • direkter Vergleich im Applet mit Zufallszahlen
    • Bubblesort-Applet
    • Quicksort-Applet
• Zeitaufwand der Matrix-Multiplikation:
  • betrachten nur nxn-Matizen
  • untergliedert in
    • Zahl der Multiplikationen M(n)
    • Zahl der Additionen A(n)
  • bestimmbar aus Rekursionsbeziehungen für M(2^h+1) und A(2^h+1)
  • direktes Verfahren
    • 
  • Strassen-Algorithmus
    • 
  • für große Matrizen
    • höhere Potenz 3 überwiegt größeren Vorfaktor
    • → Strassen ist schneller
• Strassen-Algorithmus in der Praxis:
  • benötigt zusätzlichen Speicherplatz und Verwaltungsaufwand für Zwischenergebnisse
  • Verhalten abhängig von Aufwand einer Multiplikation gegenüber einer Addition
  • frühere Abschätzung: lohnt sich erst ab n > 10000!
  • Tricks zur Verbesserung [3]
    • Rekursion bei kleinen Matrizen abbrechen und direkt multiplizieren
    • besserer Umgang mit Speicherplatz
    • geschicktes Verwalten der "ungeraden" Zeilen/Spalten
  • damit Strassen-Algorithmus schneller ab n > 1000
• Aufgaben:
  • Aufgabe 1