Skip to Content

Rechenregeln für die Aufwandsbestimmung

Die Rechenregeln für die Aufwände von Algorithmen erlauben dem Entwickler die Komplexitätsklasse eine Algorithmus abzuschätzen.

Hierzu geht der Entwickler in zwei Schritten vor:

  1. Man bestimmt die Anzahl der auszuführenden Befehle eine Algorithmus in Abhängigkeit von den zu verarbeitenden Datenelementen n
  2. Man vereinfacht den Term mit dem Gesamtaufwand derart, dass der Term und jeder Teilterm in der gleichen Komplexitätsklasse bleibt

Am Ende bleibt dann ein einfacher Ausdruck für die Komplexitätsklasse übrig.

Klassen von Komplexität

  • konstant: O(1)
  • logarithmisch: O(log(n))
  • linear: O(n)
  • jenseits von linear: O(n*log(n))
  • polynomial: O(n2), O(n3), O(n4) etc.
  • exponentiell: O(kn)

Rechenregeln für einfache Betrachtungen

Gegeben sei eine Funktion f(n) mit dem Aufwand O(n). n sei die vriable Anzahl der zu verarbeitenden Datenelemente

  • Konstanten: Konstanten haben keinen Einfluss:
    • O(f(n)+k) = O(f(n))+k = O(f(n)) für k konstant
    • O(f(n)*k)=O(f(n))*k = O(f(n)) für k konstant
    • O(k) = O(1)
    • konstante Aufwände werden nicht einberechnet. Dies gilt für Multiplikation, sowie für die Addition.
  • Nacheinander ausgeführte Funktion f und g
    • Der Aufwand O(f(n)) sei größer als der Aufwand von O(g(n))
    • O(f(n)+g(n))=O(f(n))+O(g(n)) = O(f(n))
    • ... der größere Aufwand gewinnt.
  • Ineinander geschachtelte Funktionen oder Programmteile wie Schleifen f(g(n))
    • O(f(g(n))) = O(f(n))*O(g(n))
    • der Aufwand multipliziert sich.
    • Einschränkung: Hier wird davon ausgegangen, dass beide Schleifen von der gleichen Variablen abhängen!

Weitere Informationen



book | by Dr. Radut