8 Komplexitätsbetrachtungen 3

Welchen Aufwand O haben die Methoden algorithmus1() bis algorithmus8() des folgenden Programms abhängig vom Übergabeparameter n?

Gehen Sie davon aus, das der Java JIT (Just in Time Compiler) nichts optimiert.

Hinweis: Wie oft werden die jeweiligen Schleifen durchlaufen? Welche Durchläufe sind konstant, welche variabel?

package Kurs2.Sort;
public class Komplexität {
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;
            }
        }
    }
public static void algorithmus3(int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int k = j - i;
            }
        }
    }
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;
                }
            }
        }
    }
public static void algorithmus5(int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < 1000; i++) {
                int k = j - i;
            }
            for (int j = 1; j < 1000; j++) {
                int k = j - i;
            }
        }
    }
public static void algorithmus6(int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < i; j++) {
                int k = j - i;
            }
        }
    }
public static void algorithmus7(int n) {
        for (int i = 1; i < 1000; i++) {
            int j = 0;
            while (j < 1000) {
                j++;
                int k = 2 * j;
            }
        }
    }

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

} // Ende der Klasse

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 7:Komplexitätsbetrachtungen 2

public class K1 {
   private static int groesse = 1000;
 
   public static void main(String[] args) {
     algorithmusBsp(groesse);
     algorithmus1(groesse);
     algorithmus2(groesse);
     algorithmus3(groesse);
     algorithmus4(groesse);
   } 

  static void algorithmusBsp(int n) {
     for (int i = 1; i < n; i++)
        { int k = i * 2; }
     for (int j = 1; j < n; j++)
        { int k = j * 3;}
   }

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

  static void algorithmus2(int n) {
     for (int i = 1; i < n; i++) {
       int p = n;
       for (int j = 1; j < p; j++) {
         for (int k = 1; k < n; k++) {
            int s = j*k – i;
         }
       }
     }
  }

  static void algorithmus3(int n) {
     for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
           int k= 0;
           while (k<n) {
              k++;
              int q = k - j - i;
           }
           int p=0;
           while (p<n) {
             p++;
             int r = n*p;
           }
       }
    }
 }

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

 }// Ende der Klasse