Kleines Nachschlagewerk Informatik
Komplexitätsklassen
Worum geht es?
Im Folgenden sollen die Klassen vorgestellt und einige Beispiele genannt werden.
Konstant - O(1)
Rechenzeit uns Speicherverbrauch ändern sich nicht.

Beispiel ist der Zugriff auf ein Array. Ist das Array doppelt so groß, bleibt die Rechenzeit gleich.

      int[] dasArray = new int[200];
      int x = dasArray[3]; // Ist das Array doppelt so groß,
                               // ändert sich nichts
            
Weitere Beispiele: Summe aufeinanderfolgender Zahlen nach Gauß
Linear - O(n)
Hat man eine Schleife, deren Anzahl der Durchläufe von der Datenzahl abhängt, ist der Zusammenhang linear.

Beispiel: Sucht man einen Wert inn einem ungeordneten Array, muss man jede Zelle prüfen. Ist das Array doppelt so groß, müssen doppelt so viele Zellen geprüft werden.

      int[] das Array = new int[200];
      // hier wird das Array irgendwie gefüllt
      int i = 0;
      while (i < 200)
      {
          if (dasArray[i] == 3)
          {
              ...
          }
          i++;
      }
            
Weitere Beispiele: Fibonacci mit Schleife, Summe aufeinanderfolgender Zahlen mit Schleife
Quadratisch - O(n^2)
Die Rechenzeit wächst quadratisch mit der Datenmenge. Dies erkennt man zum Beispiel an geschachtelten Schleifen, deren Durchlaufzahl von der Datenmenge abhängt.

Ein Beispiel ist der Bubblesort-Algorithmus (hier soll das größte Element nach hinten). Die Daten liegen in einem Array, die Größe ist max.

      for (int i = 0; i < max; i++)
      {
          for (int j = 0; j < max - 1; j++)
          {
              if (dasArray[j] > dasArray[j+1])
              {
                  int m = dasArray[j];
                  dasArray[j] = dasArray[j+1];
                  dasArray[j+1] = m;
              }
          }
      }
            
Die Zahl der Durchläufe der inneren Schleife lässt sich reduzieren. Die Anzahl der Durchläufe verringert sich auf n^2/2. Dies ist keine Änderung der Klasse, der quadratische Zusammenhang bleibt erhalten.

Weitere Beispiele: Quicksort im ungünstigsten Fall, GameOfLife,
Kubisch - O(n^3)
Wächst der Rechenaufwand kubsich, sind meist drei geschachtelte Schelifen verantwortlich. Beispiele können Berechnungen im Raum sein, die Datenmenge ist die Zahl der Schritte.

      for (int xKoordinate = 0; xKoordinate < maxX; xKoordinate+=schrittweite)
      {
          for (int yKoordinate = 0; yKoordinate < maxY; yKoordinate+=schrittweite)
          {
               for (int zKoordinate = 0; zKoordinate < maxZ; zKoordinate+=schrittweite)
              {
                   // irgendwas berechnen
              }
          }
      }
            
Logarithmisch - O(log n)
Logarithmische Abhängigkeiten treten oft auf, wenn Dinge geteilt werden. Ein Beispiel ist das Suchen im geordneten Array. Sind Daten der Größe nach geordnet, kann man den Bereich fortlaufend halbieren.

In folgendem Beispiel zerteilt man die 16 Elemente log_2 16 = 4 Mal, um zu prüfen, ob die 15 gespeichert wurde.



Linear-Logarithmisch - O(n log n)
Weitere Beispiele: Quicksort, Mergesort
Exponentiell - O(2^n)
Exponentiell sind Algorithmen, die auf Probieren angewiesen sind.

Man nehme einen Algorithmus, der prüfen soll, ob ein logischer Term wahr ergibt. Der Term benutzt vier boolesche Variable, die wahr oder falsch sein können. Somit müssen 2^4=16 Tests durchgeführt werden. Erhöht sich die Zahl der Variablen um eins, müssen 2^5=32 Tests durchgeführt werden, weil es nun 32 verschiedene Belegungen gibt.

Weitere Beispiele: Fibonacci rekursiv, Rucksack-Problem