9 Binäre Suche

package Kurs2.Sort;
public class Komplexitaet;
  private static int groesse = 1000;

  public static void main(String[] args) {
    algorithmus1(groesse);
    algorithmus2(groesse);
    algorithmus3(groesse);
    algorithmus4(groesse);
    algorithmus5(groesse);
    algorithmus6(groesse);
    algorithmus7(groesse);
  }

  public static void algorithmus1(int n) {
    for (int i = 1; i < n; i++) {
      int k = i * 2;
    }
  }

  public static void algorithmus2(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < 1000; j++) {
       int k = j - i;
      }
    }
  }

Die innere for-Schleife wird 1000 mal durchlaufen:

• O(1000) = O_innere(1)

Die äussere for-Schleife wird n mal durchlaufen:

• O(n)*O_innere(1)=O_aeussere(n)

Gesamtkomplexität: O(n)

  public static void algorithmus3(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < n; j++) {
        int k = j - i;
      }
   }
  }

• O_innere(n)

Die äussere for-Schleife wird n mal durchlaufen:

• O(n)*O_innere(n)=O_aeussere(n²)

Gesamtkomplexität: O(n²)

  public static void algorithmus4(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < n; j++) {
        for (int k = 1; k < n; k++) {
          int q = k - j - i;
        }
      } 
    }
  }

Die innere for-Schleife wird n mal durchlaufen:

• O_innere(n)

Die mittlere for-Schleife wird n mal durchlaufen:

• O(n)*O_innere(n) = O_mittlere(n²)

Die äussere for-Schleife wird n mal durchlaufen:

• O(n)*O_mittlere(n²)= O_aeussere(n³)

Gesamtkomplexität: O(n³)
 

  public static void algorithmus5(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < 1000; j++) {
        int k = j - i;
      }
      for (int j = 1; j < 1000; j++) {
        int k = j - i;
      }
    }
  }

Jede der inneren Schleifen wird 1000 mal durchlaufen und hat damit einen konstanten Aufwand

• O_innere2(1000)+O_innere2(1000)= O_innere2(1)+O_innere2(1)=O_innen(1)

Die äussere Schleife wird n mal durchlaufen:

• O(n)*O_innen(1)=O_aeussere(n)

Gesamtkomplexität: O(n)

  public static void algorithmus6(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < i; j++) {
        int k = j - i;
      }
    }
  }

Jede der inneren Schleifen wird i mal durchlaufen:

• O_innen(i)

Die äussere Schleife wird n mal durchlaufen:

• O(n)*O_innen(i)

Beide Schleifen haben gemeinsam die Durchläufe 1+2+3... +n = (n-1)n/2 = (n²-n)2

• O(n)*O_innen(i)=(O(n²)-O(n))/O(2)=O(n²)/O(1)=Oaussen(n²)

Gesamtkomplexität: O(n²)
Bemerkung: Das Zusammenwirken geschachtelter Schleifen ist nicht trivial. Es müssen alle relevanten Variablen aufgelöst und es muss eine Summenformel entwickelt werden.

   public static void algorithmus7(int n) {
    for (int i = 1; i < 2000; i++) {
      int j = 0;
      while (j < 1000) {
        j++;
        int k = 2 * j;
      }
    }
  }

Die while-Schleife wird 1000 mal durchlaufen. Ihr Aufwand ist konstant:

• O_while(1000)=O_while(1) 

Die for-Schleife wird wird 2000 mal durchlaufen. Ihr Aufwand ist konstant:

• O(2000)*O_while(1)=O(1)*O_while(1)=O_for(1)

Gesamtkomplexität: O(1)

  public static void algorithmus8(int n) {
    for (int i = 1; i < n; i++) {
      algorithmus1(n);
    }
  }

Die Methode algorithmus1() hat den Aufwand O(n). Siehe weiter oben.

Die for-Schleife wird n mal durchlaufen:

• O(n)*O(n)=O_for(n²)

Gesamtkomplexität: O(n²)

} // Ende der Klasse