OOPM1718 Übungswoche 09 (22.01-28.01.18)
Zielsetzung für die Übung
- Komplexität von Algorithmen
- Zeitkomplexität
- Speicherkomplexität
- Schranken (insb. obere Schranke mit O-Notation)
Beispiel:
Berechne für Bubblesort die Zeitkomplexität gemäß Vorlesungsfolien und bestimme die Komplexitätsklasse.
public static int[] bubblesort(int[] a) { //n = a.length
int temp; //0
for(int i=1 i<a.length i++) { //n
for(int j=0 j<a.length-i j++) { //n(n+1)/2
if(a[j]>a[j+1]) { //n(n-1)/2
temp=a[j]; //n(n-1)/2
a[j]=a[j+1]; //n(n-1)/2
a[j+1]=temp; //n(n-1)/2
}
}
}
return a; //1
}
Tw(n) = n + n(n+1)/2 + 4 n(n-1)/2 + 1
= n + n^2/2 + n/2 + 2n^2 - 2n + 1
= 2,5 n^2 - 0,5 n + 1
Die Komplexitätsklasse ist O(n^2)
Ein weiteres Beispiel:
public static int beispiel(int[] a) { n = a.length
int result = 0; //0
int x = 5; //0
int y = 2; //0
int z = 1; //0
for (int i = 0; i < x; i++) { //6
System.out.println("i: " + i); //5
for (int j = 1; j < a.length; j*=y) { //5 (log(n) + 1)
System.out.println("j: " + j); //5 log(n)
for (int k = a.length-x; k >= 0; k--) { //5 log(n) (n-3)
System.out.println("k: " + k); //5 log(n) (n-4)
for (int l = 0; l < a.length; l+=z) { //5 log(n) (n-4) (n+1)
System.out.println("l: " + l); //5 log(n) (n-4) n
for (int m = 0; m < Math.pow(2, a.length); m++) { //5 log(n) (n-4) n (2^n+1)
System.out.println("m: " + m); //5 log(n) (n-4) n 2^n
result += i - a[j] + a[k] - a[l]; //5 log(n) (n-4) n 2^n
}
}
}
}
}
return result; //1
}
Um Tw(n) zu bestimmen muss man jede Zeile zusammen addieren.
Um die Komplexitätsklasse zu bestimmen,
muss man sich nur den Summanden mit der größten Steigung anschauen.
Das wäre:
5*log(n)*n 2^n*(n-4) => log(n) *n^2*2^n
Komplexitätsklasse O(n^2 * log(n)*2^n)
Einige Komplexitätsklassen nach Größe sortiert:
O(nn) > O(n!) > O(2n) > O(n2) > O(nlog(n)) > O(n) > O(log(n)) > O(1)
Zielsetzung für das Programmierpraktikum
- Generizität
- Verwendung bei Containertypen
- Iteration
- Datentyp "Object"
- Down-casting
- Typtest mit instanceof
- (Varianzen)
page revision: 4, last edited: 24 Jan 2018 13:47