Biespiel für Komplexitätsklassen von Algorithmen in Java

AlgorithmusB ist aus O(1), da if-Anweisung dafür sorgt, dass n maximal 10 als Wert annehmen kann.

AlgorithmusC ist aus O(n^2). Die Schleife Außen wird n-mal durchlaufen, die innere Schleife wird aber nur i mal duchlaufen, wobei i für die Iteration der äußeren Schleife steht. Das führt zur Gaußschen Summe und deshalb einer Komplexitätsoberklasse O(n^2).

AlgorithmusD ist aus O(log n). Bei jedem Durchlauf der while-Schleife wird n halbiert. Bis zur Verletzung der Schleifenbedingung kann man eine Zahl genau log(n;2) al durch zwei teilen, somit ist die Komplexität des Algorithmus O(log(n)).


// Eingabe n>0
public double algorithmusB(int n){
   if(n>10){
      n = 10;
   }

   double s = 0;

   for(int i=1;i<=n; i++){
       s++;
    }

    return s;
}

// Eingabe n>1
public double algorithmusC(int n){
    
     double s = 0;

     for(int i=1; i<=n; i++){
        a = 0;
     
        for(j=1;j&lt;i; j++){
             a = a+1;
        }

      s = s+a;
     }

     return s;
}

// Eingabe n > 1 
public double algorithmusD(int n){

    double z = 0;

     while(n >= 2){

         n = n/2;

         z++;
     }

     return z;
}