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

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

Fortsetzung Vergleich von Sortierverfahren

Zu Beginn der Stunde haben wir noch einmal die Ergebnisse der letzten Stunde zusammengefasst, nämlich, dass Insertionsort das schnellste Sortierverfahren ist und mit einer Quadratfunktion dargstellt werden kann. Für den Großteil der Stunde sollten wir für Bubble- und Selectionsort weitere Formeln herausfinden, indem wir die Listengröße schrittweise verdoppeln und die verbrauchte Zeit zum Sortieren auswerten.… Weiterlesen Fortsetzung Vergleich von Sortierverfahren

Vergleich von Sortierverfahren

Zu Beginn der Stunde haben wir die Sortierverfahren zeitlich verglichen. Wir haben Listen sortiert von der Länge 10 000 dabei kam raus das Insertionsort eindeutig am schnellsten von den 3 Verfahren ist: Anschließend haben wir Vergleichsfaktoren für Algortihmen gefunden: Länge der Liste Schleifenzählung Größenordnung der Liste: best case, average case, worst case Die Schleifenzählung ist… Weiterlesen Vergleich von Sortierverfahren

Sortierverfahren im Detail

Heute wurden die Sortierverfahren der Gruppen vorgestellt. Bei genauerer Betrachtung wurden sie folgendermaßen erklärt: Selectionsort: Am Beispiel von Spielkarten wurde uns dieses Verfahren beigebracht. Die Vorraussetzung ist eine unsortierte Liste (Es funktioniert auch mit sortierten Listen aber dann kann man sich das sparen). Das erste Element wird in einem Parameter gespeichert. Danach überprüft man ob… Weiterlesen Sortierverfahren im Detail

Gruppenphase zu Sortierverfahren

Die Sortierverfahren Bubblesort, Insertionssort und Selectionsort wurden in Gruppen bearbeitet. Ergebnisse der Phase sollen sein: Beschreibung des Funktionsprinzips mit Bezugnahme zum Namen des Verfahrens Darstellung an Balkenwaage oder Spielkarten Implementierung (hier kann es sinnvoll sein auch Pseudocode oder ein Struktogramm zur Verdeutlichung zu nutzen)