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… Weiterlesen Komplexität eines Algorithmus

Funktionswachstum

Es ging heute darum verschiedene Funktionstypen und deren Wachstum einzuordnen. Hierbei gelten folgende Zusammenhänge: Eine (Kosten-) Funktion f wächst schneller als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen unendlich strebt. Eine (Kosten-) Funktion f wächst langsamer als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen 0… Weiterlesen Funktionswachstum

Effizienztest bei Kostenfunktionen + Wachstum

Allgemeines zu Funktionstypen Die Erkenntnis zu beginn der Stunde war folgende : Alle quadratischen Funktionen verlaufen relativ gleich.Weiteren Überlegungen entnahmen wir das folgende Verhalten von verschiedenen Funktionstypen beim variieren der x-und y-Werte : Wenn man den x-Wert einer Quadratfunktion verdoppelt, verfierfacht sich der y-Wert Wenn man den x-Wert einer Linearfunktion verdoppelt, verdoppelt sich der y-Wert… Weiterlesen Effizienztest bei Kostenfunktionen + Wachstum

Effizienstests bei Kostenfunktionen

Ermitteln der Effizienz Uns wurden zwei Formeln gegeben. T1 = 0,01*n*n und T2 = 100*n*log10(n). Beide wurden nebeneinander in Excel-Tabellen eingefügt und an viele verschiedenen Werten für n getestet. Das Ergebnis war, dass T1 T2 bei großen n-Werten (nach den ersten 18 Zahlen in einer sich verdoppelnden Excel Tabelle) überholte und ist somit besser für… Weiterlesen Effizienstests bei Kostenfunktionen

Quicksort: Laufzeitanalyse

Als erstes haben wir die Grundfunktion des Sortierverfahrens „Quicksort“ nochmal aufgefrischt: Alle die währenddessen noch nicht 100% wach waren, können das hier nachholen. Die Leitfrage der Stunde war: „wie quick ist Quicksort wirklich?“ Um diese Frage zu beantworten, müssen wir zwischen worst- und best-case Szenarien unterscheiden und beide beachten. 1. Worst-case: Das ausgewählte Element, mit… Weiterlesen Quicksort: Laufzeitanalyse

Laufzeiten der Sortierverfahren

Wir haben un smit dem Begriff der Problemgröße beschäftigt. In unserm Fall ist die Problemgröße die Listengröße der unsortierten Listen. Als anderes Beispiel haben wir uns die Primfaktorzerlegung von Zahlen angeschaut und sind zu dem Entschluss gekommen, dass hier die Problemgröße die Anzahl der Stellen der Zahlen ist. Bei der Bestimmung von allgemeinen Fromeln für… Weiterlesen Laufzeiten der Sortierverfahren

Besprechung des Quicksort- Codes + weiteres Vorgehen

Zu beginn der Stunde haben wir den Code für das Quicksort-Verfahren besprochen und die Laufzeittests durchgeführt. Hier ein Beispiel-Code: Weiteres Vorgehen und Kosten-Maß: Bei den Laufzeittests ist aufgefallen, dass es sich zunächst um eine lineare Abhängigkeit handelte, jedoch bei genauerer Betrachtung auffiel, dass es sich um keine Abhängigkeit handelt und wir nun die Schritte der… Weiterlesen Besprechung des Quicksort- Codes + weiteres Vorgehen

Quicksort – Anfang der Implementierung

Zu Beginn der Stunde wurde zur Wiederholung mit Filmdöschen und einer Waage vorgeführt, wie Quicksort in etwa abläuft. Grob zusammengefasst: Man pickt sich ein Element raus und vergleicht es mit allen anderen Elementen. Dabei werden zwei Listen erstellt, in eine kommen die Elemente hinein, die kleiner als das Pivotelement(das Herausgepickte) sind. In die andere kommen… Weiterlesen Quicksort – Anfang der Implementierung