OOPM1617 Übungswoche 11 (30.01-05.02.17)

Zielsetzung für die Übung

  • Besprechung der Hausaufgabe aus letzter Woche
    • Verifikation von Algorithmen
  • Komplexität von Algorithmen

Wir haben bei sehr vielen Algorithmen die Komplexitätsklasse bestimmt.
Unten ist ein Beispiel, welches aus den einzelnen Übungsaufgaben erstellt wurde und in der vorliegenden Version in der Komplexitätsklasse O(n^2) ist:

public static void c(int n){
    int k = 1;                        // 1
    int p = 2;                        // 1
    int s = 3;                        // 1
    for (int i = 0; i < n; i++){        // n+1
        s = s + k;                        // n
        for (int j = i; j < n; j++) {    // (n+1)(n+2)/2 - 1
            s--;                        // n * (n+1) / 2
        }
        for (int j = 1; j < n; j = j * p){    // n* (log(n)+1)
            k = i + j;                // n * log(n)
            if(k>s){                    // n * log(n)
                k++;
            }else{                    // n * log(n) - für then- und else-Teil gemeinsamer Aufwand
                s++;
            }
            for (int j2 = 0; j2 < 5; j2++) {    //6 * n * log(n)
                k--;                            //5 * n * log(n)
            }
        }
        k = k - s;                    // n
    }
}

Zielsetzung für das Programmierpraktikum

  • Implementation von Zustandsdiagrammen
    • Switch-Case-Anweisung
    • Method-Dispatch
    • Table Driven