Komplexitätsklasse


SUMME := SUMME + 1;
Komplexitätsklasse: O(1), denn die Anzahl der Anweisungen hängt NICHT
von den Eingabewerten ab!

ZAHL := LESE_ZAHL_VON_TASTATUR();
FOR i := 1 TO ZAHL DO
 SUMME := 1;
Komplexitätsklasse: O(N), denn die Anzahl der Anweisungen hängt linear von
der eingegebenen Zahl ZAHL ab!

Vereinfachung des zuletzt betrachteten Algorithmus:

SUMME := 1;
Komplexitätsklasse O(1), denn: Die Anzahl der Anweisungen hängt nicht von
irgendwelchen Eingabewerten ab!

Beispiel für eine höhene Komplexitätsklasse:

I := 10;

WHILE I >= 0 DO
  BEGIN
    FOR K := 1 TO I DO
      Irgendwas("Helau");
    I := I - 1;
  END;

Komplexitätsklasse O(N²), da zwei voneinander abhängige, verschachtelte
Schleifen im Algorithmus vorhanden sind, die beide von Variablen
abhängen.