Willkommen zu einer neuen Ausgabe von Komplexität von Algorithmen.

Wir waren stehen geblieben letztes Mal bei unserer ersten Average Case Analyse.

Wir machen heute noch zwei weitere Beispiele.

Vom zweiten Beispiel werde ich einen Teil heute nicht mehr schaffen.

Das macht dann Herr Gurin am Freitag zu Ende.

Ich kann selber leider abwesen.

Sie werden feststellen, dass die Algorithmen, die wir in der Average Case Analyse verwenden,

obwohl sie jetzt schwieriger werden als dieses erste Beispiel, weiterhin sehr primitiv bleiben.

Das liegt daran, dass Average Case Analyse schwierig ist

und im Allgemeinen nur in besonderen Fällen in Griff zu bekommen ist.

Wir machen es trotzdem.

Also weitere Beispiele über Average Case Analyse.

Ich tue mal so, als hätte ich dem ersten Beispiel eine Nummer gegeben.

Es hätte also die Nummer 1 sein sollen.

Dementsprechend kommt jetzt Beispiel 2.

Auch das, wie gesagt, keine Rocket Science.

Suche nach maximal.

Was ist da das Problem?

Wir stellen uns vor, wir hätten gegeben ein Array von n natürlichen Zahlen.

Wir suchen den Index, an dem die größte Zahl steht.

Wie machen wir das?

Ich nenne das, was jetzt feucht, mal Max, um später darauf zugreifen zu können.

Das soll jetzt kein Prozedurnamen sein, einfach ein Name für das Programm, das jetzt hier feucht.

Was tun wir?

Wir gehen von vorne durch das Array.

Wir setzen zunächst mal das prospektive Maximum auf den ersten Eintrag.

Gut, klar, was können wir tun?

Dann laufen wir durch das Array durch.

Beginnt jetzt natürlich beim 2-Index 2.

Index 1 haben wir schon abgehandelt.

Wir gucken jetzt, ob wir das Maximum ändern müssen.

Wann müssen wir das ändern?

Wir müssen es dann ändern, wenn der neue Eintrag, den wir jetzt hier kriegen, größer ist als das bisherige Maximum.

Das heißt, wenn a i größer ist als m,

dann setzen wir m auf a i.

Ja gut, guckt man sich das an und fragt sich, was das überhaupt jetzt mit der Analyse soll.

Wir sehen ja, wie oft diese Schleife durchläuft.

Das ist eine Vorschleife ohne weitere Abbruchkriterien.

Das läuft schlicht und einfach n-1-mal durch.

Was ist also die Frage?

Die Frage ist, wie oft müssen wir tatsächlich das Maximum ändern?

Das ist ja nur das Gerüst für das Ganze.

Bei Änderungen des Maximums könnte hier ja was Komplizierteres passieren.

Wir stellen uns vor, dieser Schritt hier sei teuer.

Dementsprechend fragen wir also, wie oft müssen wir tatsächlich das Maximum ändern?

Wie oft weisen wir a i an m zu?

Ja, da können wir wieder erstmal, um zu motivieren,

warum wir überhaupt eine Average-Case-Analyse machen,

uns eine Worst-Case und eine Best-Case-Analyse angucken.

Beide sehr einfach.