Komplexität eines Algorithmus

Die Komplexität eines Algorithmus beschreibt man mit der Kostenfunktion. Hierbei fällt auf das unsere Funktionen wie beispielsweiße n^2 oder n! unterschiedlich komplex sind. Um unsere Funktionen weiterhin zu vergleichen, um herauszufinden welche die beste Funktion ist, betrachten wir für jede Funktion den „Worst-Case“. Dadurch finden wir heraus, dass es im Worst-case immer bessere Funktionen, als die die wir betrachtet haben. Dieses Verfahren wird solange durchgeführt, bis es keine bessere Funktion gibt.

Neues Sortierverfahren

Danach hat Herr Karp uns ein weiteres Sortierverfahren präsentiert. Hierbei ist uns die Anzahl und Werte der Karten bekannt. Nun nimmt man die erste und sortiert sie, unter Rücksichtnahme der Informationen, so ein, dass noch Platz für die Nachfolgenden ist. Bsp: Wir haben 5 Karten, 10, Bube, Dame, König und Ass. Wir ziehen den König und Sortieren ihn so, dass links von ihm 3 Plätze und rechts von ihm 1 Platz frei bleibt, da wir die Informationen beachtet haben. Das Verfahren klingt recht gut, jedoch ist bei diesem Sortierverfahren das Problem, dass wir leere Elemente in einer Liste (beim Implementieren) hätten.

Schreibe einen Kommentar