8 Komplexitätsbetrachtungen 3

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

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).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 16 Minuten

Antwort zu Frage 7:Komplexitätsbetrachtungen 2

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;
}
}
Ofor1(n)+Ofor2(1000)= Ofor1(n)+Ofor2(1) = 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++) {
for (int k = 1; k < n; k++) {
int s = j*k – i;
}
}
}
}
 Ofor1(n)*Ofor2(n)*Ofor3(n) = O(n3)
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;
}
}
}
}
Ofor1(n)*Ofor2(n)*(Owhile1(n)+Owhile2(n))
Ofor1(n)*Ofor2(n)*2*Owhile(n)= 2*O(n3) = O(n3
4.
  static void algorithmus4(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; j++) {
algorithmus2(n);
}
}
}
 Ofor(n)*Ofor2(1000)*Oalgorithmus2(n3) = O(n4)
 
 }// Ende der Klasse
 ---

Anonymous (not verified)

Wed, 06/27/2018 - 16:31

In der Aufgabenstellung wird nur nach den Algorithmen 1-7 gefragt, in der Lösung sind alle vorhanden.