Servus mitanand =)
Wir behandeln im Unterricht derzeit die Komplexität von Sortieralgorithmen, sprich Bubble-, Heap-, Merger-, Insertion- und Selectionsort.
So genaz konnte ich mich mit dem Thema jedoch noch nicht anfreunden.
Die Algorithmen an sich sind klar, was es jedoch genau mit der Komplexität auf sich hat, kann mir jemand vielleicht nochmal in seinen Worten erklären ?
Würde mich über Beistand freuen
Liebe Grüße.
Wir behandeln im Unterricht derzeit die Komplexität von Sortieralgorithmen, sprich Bubble-, Heap-, Merger-, Insertion- und Selectionsort.
So genaz konnte ich mich mit dem Thema jedoch noch nicht anfreunden.
Die Algorithmen an sich sind klar, was es jedoch genau mit der Komplexität auf sich hat, kann mir jemand vielleicht nochmal in seinen Worten erklären ?
Würde mich über Beistand freuen
Liebe Grüße.
__________________Blog Geschichte LK 2009/2010
NS Ideologie, Chinas Weg in die Moderne sowie Franzrev.
NS Ideologie, Chinas Weg in die Moderne sowie Franzrev.
Komplexität eines Algorithmus ist quasi seine asymptotische Laufzeit - Das bedeutet: Wie viel "Aufwand" macht der Algorithmus bei großen Datenmengen.
Bei Sortieralgorithmen setzt sich die Komplexität/Laufzeit z.B. aus den Vergleichsoperationen (wenn vorhanden) zusammen:
Schauen wir uns z.B. Insertionsort an, so muss eine Liste von Vorne bis hinten durchlaufen werden und (im schlimmsten Fall) das neu hinzuzufügende Element ganz durch die bereits sortierte Teilliste schieben -> Realisierbar durch zwei verschachtelte Schleifen.
Also muss bei n Eingabewerten ungefähr n² Aufwand betrieben werden (Faktoren und Konstanten lässt man weg). Dies drückt man "informatisch" als O(n²) aus.
Bei Sortieralgorithmen setzt sich die Komplexität/Laufzeit z.B. aus den Vergleichsoperationen (wenn vorhanden) zusammen:
Schauen wir uns z.B. Insertionsort an, so muss eine Liste von Vorne bis hinten durchlaufen werden und (im schlimmsten Fall) das neu hinzuzufügende Element ganz durch die bereits sortierte Teilliste schieben -> Realisierbar durch zwei verschachtelte Schleifen.
Also muss bei n Eingabewerten ungefähr n² Aufwand betrieben werden (Faktoren und Konstanten lässt man weg). Dies drückt man "informatisch" als O(n²) aus.
__________________Alle Angaben ohne Gewähr ;-)
Grundsätzlich hilft erstmal: Schleifen und deren Verschachtelung genau angucken und dann für sehr hohe n-werte (von mir aus 1 000 000) überlegen wie sich das auf die Zeit auswirkt.
Bei den Sortierverfahren die wir kennengelernt haben ist es meines wissens im worst case immer O(n²) gewesen.
Bei den Sortierverfahren die wir kennengelernt haben ist es meines wissens im worst case immer O(n²) gewesen.
Zuletzt bearbeitet von Alexius am 20.03.2010 um 18:11 Uhr
Bei der Komplexität handelt es sich meistens um eine worst-case Angabe. D.h. wir können garantieren, dass der Algorithmus nach einer bestimmten Zeit terminiert. Diese obere, asymptotische Schranke wird in der sog. O-Notation angegeben (http://de.wikipedia.org/wiki/O-Notation). Um diese Schranke zu berechnen werden Zuweisungen, arithmetische Operatoren etc. ignoriert, da sie immer eine konstante Zeit benötigen. Interessant sind vorerst nur die Schleifendurchläufe des Algorithmus. Als Beispiel Bubblesort: Er besteht aus zwei Schleifen. Die äußere Schleife wird (n-1) ausgeführt, die innere Schleife wird bei jeder Iteration (Schleifendurchlauf) um 1 verkürzt. Es ensteht also eine Laufzeit von n*(n-1+n-2...). Dies kann man als (n*(n-1))/2 zusammenfassen. Dadraus folgt die obere Schranke O(n²). Dies ist eine schlechte Laufzeit. Übrings: Vergleichbasierte Sortierverfahren haben immer mindestens eine O(n log n) Laufzeit als obere Schranke, schneller geht es nicht.
Finds super, dass du hier gleich so einsteigst, danke auch dafür!!
Gerade das Info- Forum ist nicht so angeregt, wie z.B Physik
Da kommen helfende Hände genau richtig.
Kann man dich bei nem konkreten Problem auch über /pm oder email erreichen ?
Liebe Grüße,
Niklas.
Gerade das Info- Forum ist nicht so angeregt, wie z.B Physik
Da kommen helfende Hände genau richtig.
Kann man dich bei nem konkreten Problem auch über /pm oder email erreichen ?
Liebe Grüße,
Niklas.
__________________Blog Geschichte LK 2009/2010
NS Ideologie, Chinas Weg in die Moderne sowie Franzrev.
NS Ideologie, Chinas Weg in die Moderne sowie Franzrev.
