Wie erkenne ich den worst-case mithilfe der O-Notation?

Answer 1

[Destranix]

Um den Worst-Case zu bestimmen nimmst du für die jeweiligen Werte, für die du den Worst-Case bestimmen möchtest, immer die schlimmst möglichen an.

Für eine Worst-Case-Laufzeit wäre das jeweils die längste mögliche Laufzeit eines Codesegments. An einem Beispiel verdeutlich:

Du hast eine Liste list der Länge n. Du möchtest ein bestimmtes Element der Liste finden. Dein Code dafür sieht folgendermaßen aus:

int searchedElementIndex = -1;
for(int i = 0; i < n; ++i){
    if(searchedElement.equals(list[i].value)){
        searchedElementIndex = i;
        break;
    }
}

Wie lange läuft die Schleife im Best-Case? Wie lange läuft die Schleife im Worst-Case? Wie lange läuft sie im Average-Case?

Der Best-Case wäre hier, dass das gesuchte Element an der ersten Stelle der Liste steht. Dann endet die Schleife nach einem Durchlauf, vollkommend egal, wie lang die Liste ist. Die Best-Case-Laufzeit wäre demnach in O(1).

Der Worst-Case wäre hier, dass das gesuchte Element an der letzten Stelle der Liste steht. Dann endet die Schleife nach n Durchläufen. Die Worst-Case-Laufzeit wäre demnach in O(n).

Die Average-Case-Laufzeit berechne ich hier über das arithmetische Mittel der Laufzeiten der möglichen Fälle. Womöglich wird das an anderer Stelle anders gemacht, da musst du jeweils schauen, wie das definiert ist.
Fälle gibt es hier n mögliche, jewiels das gesuchte Element an Stelle i. Die Zahl der Durchläufe für den Fall i ist (i+1). Entsprechend ergibt sich für den Average-Case eine Zahl an Durchläufen (unter Verwendung der Gaußschen Summenformel)

sum(1, n, i)/n = (n * (n+1))/(2n) = (n + 1)/2;

Das liegt in O(n);