Komplexitätsmaße

• Problem: Sprache L, Alphabet $\Sigma$, $\forall x\in \Sigma^*$:
  • Hält die Maschine nach endl. Zeit und gibt eine Antwort?
    
    $\left. \begin{array} {l} x \in L: \text{Antwort ``ja``}\\ x \not \in L: \text{Antwort ``nein``} \end{array} \right\}$ Maschine entscheidet L
    
    f(x), Maschine berechnet f (partielle Funktion)
    
  • Entweder
    • hält die Maschine nach endl. Zeit und sagt ``ja`` oder
    • die Maschine hält nicht oder hält und sagt ``nein``. Falls $\forall x\in L$, o.B.d.A. das nicht vorkommt, $\Rightarrow$ Maschine akzeptiert L
      
• Wie werden die Kosten berechnet? Betrachte Eingaben x der Länge n
  • worst-case Komplexität:

    $$\text{C}(n):= \max\{\text{Komplexit\uml {a}t}(x);\ \vert x\vert=n\}$$

  • durchschnittliche Komplexität (average complexity):

    $$\text{C}(n):= \frac{1}{\vert\Sigma^n\vert}\sum_{\vert x\vert=n} \text{Komplexit\uml {a}t}(x)$$

    allgemeiner: Wahrscheinlichkeitsmaß $\mu$

    $$\text{C}(n):= \sum_{x \in \Sigma^n} \mu(x) \cdot \text{Komplexit\uml {a}t}(x)$$

  • amortisierte Komplexität:
    durchschnittliche Kosten der Operationen in Folgen
    worst-case über alle Folgen von Operationen
  • probabilistische oder randomisierte Komplexität:
    Algorithmus hat Zufallsbits zur Verfügung. Erwartete Laufzeit (über alle Zufallsfolgen) für feste Eingabe x, dann worst-case für alle |x|=n.
• Ressourcen
  • Rechenzeit
  • Speicherplatz
  • Anzahl von Vergleichen
  • Anzahl von Multiplikationen
  • Schaltkreisgröße
  • Programmgröße
  • Schachtelungstiefe von Laufschleifen
• Kosteneinheiten:
  • uniformes Kostenmodell
  • logarithmisches Kostenmodell: Kosten $\sim$ Länge der Operanden
  Beispiel:
  
  

  
  		 r:=2
  		 for i=1 to n do r=r2 od
  		 ($\Rightarrow r^{2^n}$)  
  

  Zeit:
  • uniform: n-Schritte
  • logarithmisch: $1+2+4+\dots+2^n = n^{n-1}+1 = \mathcal{O}(2^n)$
  Platz:
  • uniform: 1
  • logarithmisch: 2ⁿ