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