11 Komplexitätsbetrachtungen 4

Submitted by javafrage on Sun, 03/01/2015 - 11:18

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 p = n;
      for (int j = 1; j < p; j++) {
        for (int k = 1; k < n; k++) {
          int s = j*k – i;
        } // end for
      } // end for
    } // end for
  }
  
2. 
  static void algorithmus2(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;
       } // end while
    } // end for
  } // end for
}
  
3. 
  static void algorithmus3(int n) {
  for (int i = 1; i < n; i++) {
   for (int j = i; j < n; j++) {
    int k=0;
    while (k<1000000) {  
      k++;
      int r = i*j*k;
 } // end while
   } // end for
  } // end for
}
  
4. 
  static void algorithmus4(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1000; j++) {
      algorithmus1(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 10: Aufwand binäre und sequentielle Suche

  • Aufwand O() der binären Suche: O(log(n))
  • Aufwand O() der sequentiellen Suche: O(n)