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)