7 Komplexitätsbetrachtungen 2

Submitted by javafrage on Wed, 01/09/2013 - 08:48

Tragen Sie die Aufwände O(n) für die gegeben Methoden des Javaprogramm ein.

Nr. Quellcode Antwort
  
public class K1 {
   private static int groesse = 1000;
 
   public static void main(String[] args) {
     algorithmusBsp(groesse);
     algorithmus1(groesse);
     algorithmus2(groesse);
     algorithmus3(groesse);
     algorithmus4(groesse);
   } 
  Nichts in dieses Feld eintragen!
 Bsp. 
  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;}
   }
 Beispiel:
Ofor1(n)+Ofor2(n) = O(n)
1. 
  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;
     }
  }
  
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;
         }
       }
     }
  }
  
3. 
  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;
           }
       }
    }
 }
  
4. 
  static void algorithmus4(int n) {
     for (int i = 1; i < n; i++) {
        for (int j = 1; j < 1000; j++) {
           algorithmus2(n);
        }
     }
  }
  
  
 }// Ende der Klasse
  ---

 

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

Niveau 2
Schwierigkeitsgrad mittel
Zeit 8 Minuten

Antwort zu Frage 6: Komplexitätsbetrachtungen 1

Gegeben ist das folgende Javaprogramm:

Nr. Quellcode Antwort
  
public class K1 {
private static int groesse = 1000;
public static void main(String[] args) {
  algorithmusBsp(groesse);
  algorithmus1(groesse);
  algorithmus2(groesse);
  algorithmus3(groesse);
  algorithmus4(groesse);
}
  nichts eintragen
 Bsp. 
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;
    }
}
 Beispiel:
Ofor1(n)+Ofor2(n) = O(n) 
1.  
static void algorithmus1(int n) {
  for (int i = 1; i < n; i++) {
    int k = i * 2;
  }
  for (int i = 1; i < 1000; i++) {
    int k = i +2;
  }
}
 O(n)+O(1000)=O(n) 
 2. 
static void algorithmus2(int n) {
  for (int i = 1; i < n; i++) {
    int p = n;
    for (int j = 1; j < p; j++) {
      int k = j - i;
    }
  }
}
O(n)*O(n)=O(n2)
 3. 
static void algorithmus3(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;
      }
      int p=0;
        while (p<n) {
          p++;
          int r = n*p;
        }
    }
  }
}
O(n)*O(n)*[O(n)+O(n)]=O(n3)
 4. 
static void algorithmus4(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1000; j++) {
      algorithmus2(n);
    }
  }
}

O(n)*[O(1000)*O(algorithmus2)]=

O(n)*O(algorithmus2)=O(n3)
  
}// Ende der Klasse
  Nichts eintragen