Wirklich wichtig werden präzise Berechnungen der Komplexitätsklasse erst, wenn du dich irgendwo im 2.-3. Semester an der Uni rum treibst.... und selbst dann isses größtenteils reiner Selbstzweck. Eine gute Dimensionsschätzung reicht üblicherweise vollkommen, um sich für einen Algorithmus zu entscheiden.
Sortieralgorithmen-Aufwandsanalyse
- Ersteller Chris95
- Erstellt am
Daaron schrieb:
Diese Aussage musst du mir mal erklären:
1. was sind präzise und damit unpräzise Berechnungen der Komplexitätsklasse?
Die Bestimmung der Komplexitätsklasse ist sehr einfach WENN man die Laufzeit bestimmt hat und hat nur eine grobe Aussagekraft für eine Entscheidung ob ich es nutze [ polynomiel: kommt in frage, exponentiel: nur wenn ich nichts anderes finde, .... ]
2. selbstzweck? weil davon so wenige ahnung haben sitzen wir alle vor so ressourcenverschwendenen programmen. ach was wäre windows flotter wenn sie für's paging nicht durchgängig fifo nutzen würden (tuen sie es noch mit win7?).
3. Was ist eine Dimänsionsabschätzung? (in diesem Zusammenhang).
3.a. und was heißt üblicherweise? ülicherweise verwenden 90% die algorothimen und datenstrukturen ineffizeint weil sie keine echte ahnung von deren situationsbezogene komplexität haben.
1
1668mib
Gast
@Dese: Ich denke mit Selbstzweck ist eher was anderes gemeint.
Du kannst verschiedene Algorithmen auseinander nehmen, sie auf ihre Komplexität hin untersuchen, aber wenn du genau weißt, dass du immer nur 16 Eingangswerte hast, kann es am Ende sinnvoller sein, einfach mal die verschiedenen Algorithmen durchzutesten und zu schauen, welcher denn für die Situation dann der schnellste ist.
Ein O(log n)-Algorithmus kann ja bei entsprechenden Eingangswerten auch von einem O(n²)-Algorithmus geschlagen werden... wenn ich jetzt 16 Eingangswerte habe, sagt mir die Komplexität dennoch relativ wenig, welchen ich nehmen sollte... es kann auch durchaus sinnvoll sein, eben einen von der Komplexität her schlechteren Algorithmus verwenden.
Du kannst verschiedene Algorithmen auseinander nehmen, sie auf ihre Komplexität hin untersuchen, aber wenn du genau weißt, dass du immer nur 16 Eingangswerte hast, kann es am Ende sinnvoller sein, einfach mal die verschiedenen Algorithmen durchzutesten und zu schauen, welcher denn für die Situation dann der schnellste ist.
Ein O(log n)-Algorithmus kann ja bei entsprechenden Eingangswerten auch von einem O(n²)-Algorithmus geschlagen werden... wenn ich jetzt 16 Eingangswerte habe, sagt mir die Komplexität dennoch relativ wenig, welchen ich nehmen sollte... es kann auch durchaus sinnvoll sein, eben einen von der Komplexität her schlechteren Algorithmus verwenden.
Zuletzt bearbeitet:
@Chris95:
der limes ist (in diesem fall) unwichtig. das summenzeichen ist eine einfache sache, aber fundamental wichtig in der methatik. dürfte aber kein problem für dich sein.
es gibt keine pauschalen weg laufzeiten zu berrechnen/bestimmen/abzuschätzen. man muss das problem, den algorithmus in komponenten zerlegen, z.b. in funktionen, oder schleifen etc.
dann bestimmt man deren einzelnen laufzeiten und daraus dann die zusammengesetzte. das ist aber nur eine grobe strategie. fall unterscheidungen etc. verkomplizieren das und erlauben oft keine genaue bestimmung der laufzeit sondern nur abschätzungen (obere / untere schranken). da kann dann limes helfen solche zu bestimmen.
in meinem post habe ich dir die korrekte bestimmung der laufzeit für den im eröfnungspost geschilderten situation erklärt. bei fragen dazu melde dich.
@1668mib:
deine aussage verstehe ich und sie ist acuh richtig. aber zu mindest meiner erfahrung nach sind situationen in denen ich mich auf sowas wie "nur 16 mal" verlassen konnte eher selten.
nichts desto trotz eine legitime rangehensweise. nur die wenigsten denken darüber hinaus, nicht weil sie es nciht könnten, sondern weil sie es nciht besser wissen.
edit: wobei cih immer noch nicht weiß, was da mit slebstzweck gemeint seien soll.
der limes ist (in diesem fall) unwichtig. das summenzeichen ist eine einfache sache, aber fundamental wichtig in der methatik. dürfte aber kein problem für dich sein.
es gibt keine pauschalen weg laufzeiten zu berrechnen/bestimmen/abzuschätzen. man muss das problem, den algorithmus in komponenten zerlegen, z.b. in funktionen, oder schleifen etc.
dann bestimmt man deren einzelnen laufzeiten und daraus dann die zusammengesetzte. das ist aber nur eine grobe strategie. fall unterscheidungen etc. verkomplizieren das und erlauben oft keine genaue bestimmung der laufzeit sondern nur abschätzungen (obere / untere schranken). da kann dann limes helfen solche zu bestimmen.
in meinem post habe ich dir die korrekte bestimmung der laufzeit für den im eröfnungspost geschilderten situation erklärt. bei fragen dazu melde dich.
Ergänzung ()
@1668mib:
deine aussage verstehe ich und sie ist acuh richtig. aber zu mindest meiner erfahrung nach sind situationen in denen ich mich auf sowas wie "nur 16 mal" verlassen konnte eher selten.
nichts desto trotz eine legitime rangehensweise. nur die wenigsten denken darüber hinaus, nicht weil sie es nciht könnten, sondern weil sie es nciht besser wissen.
edit: wobei cih immer noch nicht weiß, was da mit slebstzweck gemeint seien soll.
Zuletzt bearbeitet:
maxwell-cs
Lt. Junior Grade
- Registriert
- Juli 2007
- Beiträge
- 465
man braucht übrigens gar nicht gauß zu bemühen, um auf O(n^2) zu kommen, das geht trivial mit elementaren umformungen:
1 + 2 + ... + (n-1) + n <= n + n + ... + n + n = n^2
damit hat man schon O(n^2). dass sogar Theta(n^2) gilt, O(n^2) also eine bestmögliche analyse ist, sieht man genau so elementar:
1 + 2 + ... + (n-1) + n >= n/2 + (n/2 + 1) + ... + (n-1) + n >= n/2 * n/2 = (n^2)/4.
zur allgemeinen diskussion: man muss sich immer darüber im klaren sein, dass die O-notation lediglich obere schranken für die laufzeit angibt. wenn unsere obere schranke für die laufzeit des algorithmus A besser ist als die für algorithmus B, heißt das erstmal nicht viel, es kann sogar sein, dass B IMMER schneller ist als A (wenn B nicht bestmöglich analysiert wurde).
aber selbst bei scharfen analysen kann es vorkommen, dass in der praxis A fast immer schneller ist als B, siehe z.b. simplex-algorithmus.
wenn man nicht nur groß-O, sondern Theta zeigen kann (wie hier), sieht das ganze natürlich anders aus und man kann sich mehr drauf verlassen.
testen sollte man aber sowieso immer, wenn es wirklich auf die laufzeit ankommt.
1 + 2 + ... + (n-1) + n <= n + n + ... + n + n = n^2
damit hat man schon O(n^2). dass sogar Theta(n^2) gilt, O(n^2) also eine bestmögliche analyse ist, sieht man genau so elementar:
1 + 2 + ... + (n-1) + n >= n/2 + (n/2 + 1) + ... + (n-1) + n >= n/2 * n/2 = (n^2)/4.
zur allgemeinen diskussion: man muss sich immer darüber im klaren sein, dass die O-notation lediglich obere schranken für die laufzeit angibt. wenn unsere obere schranke für die laufzeit des algorithmus A besser ist als die für algorithmus B, heißt das erstmal nicht viel, es kann sogar sein, dass B IMMER schneller ist als A (wenn B nicht bestmöglich analysiert wurde).
aber selbst bei scharfen analysen kann es vorkommen, dass in der praxis A fast immer schneller ist als B, siehe z.b. simplex-algorithmus.
wenn man nicht nur groß-O, sondern Theta zeigen kann (wie hier), sieht das ganze natürlich anders aus und man kann sich mehr drauf verlassen.
testen sollte man aber sowieso immer, wenn es wirklich auf die laufzeit ankommt.
Zuletzt bearbeitet:
1
1668mib
Gast
@Dese: Natürlich müsste/sollte man es sicherstellen, dass man sich dann auch an die Dimensionen hält. Wenn es wider erwarten jemand falsch macht, dann kann es halt nach hinten losgehen. Solche Annahmen sind natürlich eher für Dinge sinnvoll, die man selbst in der Hand hat und nicht von Benutzereingaben usw abhängen - also bei einer Kontaktliste würde ich solche Annahmen nicht treffen.
Aber in der CryEngine werden durchaus auch "schlechtere" Algorithmen verwendet, die aber für die geringe Zahl an Eingangswerten (z.B. Punkte eines einfachen Modells) effizienter sind (auf Zeit bezogen).
Aber in der CryEngine werden durchaus auch "schlechtere" Algorithmen verwendet, die aber für die geringe Zahl an Eingangswerten (z.B. Punkte eines einfachen Modells) effizienter sind (auf Zeit bezogen).
danke für die beiträge - wenn ich die nächsten tage ein bisschen Zeit habe setze ich mich nochmal dran und gehe schritt für schritt alle beiträge durch und versuche sie nachzuvollziehen.
danke an R3ddy für den Link - jetzt weiß ich wie man auf n*(n+1)/2 kommt.
Auf wikipedia ist das ziemlich gut erklärt.
mit den gleichen Ansatz versuche ich dann die Aufwandsberechnung nachzuvollziehen.
Da sich beim Sortieren ja auch eine Folge ergibt nur mit (n-1)
Der Algorithmus hat ja bei 10 feldern 9+8+7+6.... Vergleiche
danke an R3ddy für den Link - jetzt weiß ich wie man auf n*(n+1)/2 kommt.
Auf wikipedia ist das ziemlich gut erklärt.
mit den gleichen Ansatz versuche ich dann die Aufwandsberechnung nachzuvollziehen.
Da sich beim Sortieren ja auch eine Folge ergibt nur mit (n-1)
Der Algorithmus hat ja bei 10 feldern 9+8+7+6.... Vergleiche
@1668mib:
wie gesagt, hat ja niemand (das ich wüsste) was anderes behauptet.
bei einer asymptotischen laufzeit sind die konstanten faktoren unterschlagen. bei einer praktischen anwendung muss man berücksichtigen ob die eingabemenge evtl. höhere konstante faktoren komepnsieren kann oder nicht.
gibt ja nicht zu letzt so ansätze wie:
falls input größe < x benutze algo 1
sonst benutze algo 2
für Chris vieleciht inreressant:
obowhl QuickSort im Grunde asymptotisch langsamer seien kann als MergeSort, so ist er dennoch die bessere wahl, für alle eingabengrößen (mergesort hat eine ganz andere art von anwendungsgebiet). warum das so ist macht den psot dann aber doch etwas zu lang
@maxwell-cs
kleine haarspalter-korrektur
O-Notation ist nicht nur ne obere schranke, O-Notation ist die Bezeichnung für alle Abschätzungen, egal ob O,o, Theta, theta, Omega oder omega. Man dies alles die O-Notation.
wie gesagt, hat ja niemand (das ich wüsste) was anderes behauptet.
bei einer asymptotischen laufzeit sind die konstanten faktoren unterschlagen. bei einer praktischen anwendung muss man berücksichtigen ob die eingabemenge evtl. höhere konstante faktoren komepnsieren kann oder nicht.
gibt ja nicht zu letzt so ansätze wie:
falls input größe < x benutze algo 1
sonst benutze algo 2
für Chris vieleciht inreressant:
obowhl QuickSort im Grunde asymptotisch langsamer seien kann als MergeSort, so ist er dennoch die bessere wahl, für alle eingabengrößen (mergesort hat eine ganz andere art von anwendungsgebiet). warum das so ist macht den psot dann aber doch etwas zu lang
@maxwell-cs
kleine haarspalter-korrektur
O-Notation ist nicht nur ne obere schranke, O-Notation ist die Bezeichnung für alle Abschätzungen, egal ob O,o, Theta, theta, Omega oder omega. Man dies alles die O-Notation.
maxwell-cs
Lt. Junior Grade
- Registriert
- Juli 2007
- Beiträge
- 465
es war absolut klar, was gemeint ist: abschätzungen, die O benutzen...
Zuletzt bearbeitet:
1
1668mib
Gast
@Dese: Warum soll QuickSort bei allen Eingabegrößen die bessere Wahl sein als MergeSort? Oder vielleicht solltest du kurz erklären, was du mit Anwendungsgebiet meinst, weil ich dachte wir reden von Soriteren...
Zuletzt bearbeitet:
ice-breaker
Commodore
- Registriert
- Nov. 2008
- Beiträge
- 4.132
Sei mir nicht böse, aber ich will nicht unbedingt meine alten Vorlesungsaufzeichnungen rauskramen. Ich weiß aber noch, dass ich genau so, wie ich es geschrieben habe, auf die Finger geklopft bekommen habe. Das musste ich dann nochmal formaler beweisen, dass meine Aussage auch wirklich stimmt (was aber jeder Oberstufler erkannt hätte).Dese schrieb:
Denn so wie ich es geschrieben habe, kann es jeder nachvollziehen und es stimmt auch, aber es ist nicht bewiesen, dass meine Vereinfachungen des Terms auch wirklich korrekt sind.
Die Eingabegröße ist doch irrelevant. Wenn du in Quicksort ein (größtenteils) vorsortiertes Array wirfst erreichst du eine Komplexität von O(n^2). Ein Mergesort dagegen wird in jedem Fall nur O(n*log n) brauche, egal wie die Daten aussehen.Dese schrieb:obowhl QuickSort im Grunde asymptotisch langsamer seien kann als MergeSort, so ist er dennoch die bessere wahl, für alle eingabengrößen (mergesort hat eine ganz andere art von anwendungsgebiet). warum das so ist macht den psot dann aber doch etwas zu lang
Die O-Notation ist und bleibt nur ein Hinweis auf die Effizienz eines Algorithmus. Das Beispiel eines vorsortierten Arrays in Quicksort zeigt sehr gut, dass noch auf viel mehr Dinge geachtet werden muss, als einfach einen Algorithmus mit guter durchschnittlicher Geschwindigkeit laut O-Notation zu nutzen (wobei QuickSort und MergeSort dort identisch sind aber in der Realität eben nicht).
Zuletzt bearbeitet:
maxwell-cs
Lt. Junior Grade
- Registriert
- Juli 2007
- Beiträge
- 465
Die Komplexität ist aber auch zum Beispiel O(n^231 * log(n)^n). Deshalb nimmt man für solche Aussagen Thetaice-breaker schrieb:
@1668mib : im falle von eingabegrößen ist quicksort tatsächlich bei jeder besser. aber das war nicht einmal das gemeinte... der punkt ist der, dass quicksort aber nicht auf jeder eingabenverteilung die n log n LZ hält. quicksort hat nur eine avarage case LZ von n log n, aber ne worst case von n².
dennoch ist quicksort im allgemeinen für jede eingabegröße besser. mergesort hingegen hat andere vorteile. mergesort ist geeignet, wenn man große datenmengen sortieren will, die nicht alle in den schnellen hauptspeicher passen. mergesort erlaubt eine blockweise verarbeitung, was somit dem transfer zwischen externen und hauptspeicher zu gute kommt. aber mergesort hat einen größeren konstanten faktor (mehr overhead bei seinen operationen).
das sage ich nicht um dich zu beleidigen, aber ich will dir kklar machen, dass das WEIT ab vom schuss ist.
1. was hat das mit der eingabeGRÖ?E zu tun?
2. bei einem sortieren array KANNST du eine laufzeit von Theta(n^2) bekommen. das hängt aber davon ab, wie das pivot-element gewählt wird. quicksort wird im allgemeinen mit einem randomisierten pivot-selection implementiert. das führt dazu, dass die n^2 laufzeit relative selten reinhaut.
ausserdem ist die richtung der sortierung in der regel noch wichtig.
die o-notation sagt das in diesem fall genau aus:
merge-sort hat Laufzeit THETA( n log n)
quicksort hat Laufzeit O( n ^ 2)
quicksort hat AVARAGE CASE Laufzeit Theta( n log n )
mehr als das muss man nicht wissen, dass quicksort seine schwächen hat. DENNOCH ist quicksort bei sortierungen von im hauptsoeicher befindlcihen dingen IMMER vorzuziechen!
im übrigen, wenn man das sortieren parallelisieren will (es gibt zwei varianten eines parallelen quicksorts) sieht die sache wieder anders aus: da sind dann z.b. selection sort oder odd-even-sort besser geeignet (im allgemeinen), wegen geringeren kommunikationsaufwand.
wenn man sagen will, dass etwas schlecht ist, d.h. mindestens so langsam/schnell ist, dann nimmt man Omega. bei soilch einer aussage macht sich keiner die mühe ein Theta sicherzustellen.
im übrigen natürlich war mir klar, was du mit O-Notation gemeint hast. ich hab es ja auch nicht böse gemeint. dachte ich hätte das mit dem smilie und meinem haarspalter-vorwort deutlich gemeint. ich will nur sicherstellen, dass fachbegriffe hier von anderen nicht falsch gelernt werden. daraus erwachsen dann nämlich die ganzen halbwahrheiten.
@ice-breaker
hier mal zwei beispiele warum deine analyse von der ersten seite total falsch ist:
1.
for( i=1 bis n) {
for( j=1 bis i) {
}
}
äussere laufzeit n, innere i. analog zu deiner rechnung folgt laufzeit n*i, weil i konstant folgt O(n).
du hast nämlich nur glück gehabt, dass in dem therm für die laufzeit der inneren schleife ein "n" vorkam. das geht aber selbst dann in die hose, wie man an beispiel 2 sieht:
2.
EDIT_ Beispiel 2 ist erstmal gestrichen. Hab da quatsch verzapft.
EDIT: mit anderen worten: deine analyse gibt rein zufällig für das beipsiel vom TE das richtige ergebnis aus. der weg dahin ist aber mehrfach völlig daneben.
dennoch ist quicksort im allgemeinen für jede eingabegröße besser. mergesort hingegen hat andere vorteile. mergesort ist geeignet, wenn man große datenmengen sortieren will, die nicht alle in den schnellen hauptspeicher passen. mergesort erlaubt eine blockweise verarbeitung, was somit dem transfer zwischen externen und hauptspeicher zu gute kommt. aber mergesort hat einen größeren konstanten faktor (mehr overhead bei seinen operationen).
Ergänzung ()
so wie du es da auf seite eins geschrieben hast ist das total falsch. es ist weder etwas nachvollziehbares noch in irgendeiner weise richtig. so kann man noch darf man sowas analysieren. es tut mir leid, aber das da war ein absolutes no go! für sowas gibts auf der uni 0 punkte und die assistenten machen wetten darauf ob du es ins nächste semester schaffst.ice-breaker schrieb:
das sage ich nicht um dich zu beleidigen, aber ich will dir kklar machen, dass das WEIT ab vom schuss ist.
das ist so falsch!
1. was hat das mit der eingabeGRÖ?E zu tun?
2. bei einem sortieren array KANNST du eine laufzeit von Theta(n^2) bekommen. das hängt aber davon ab, wie das pivot-element gewählt wird. quicksort wird im allgemeinen mit einem randomisierten pivot-selection implementiert. das führt dazu, dass die n^2 laufzeit relative selten reinhaut.
ausserdem ist die richtung der sortierung in der regel noch wichtig.
die o-notation sagt das in diesem fall genau aus:
merge-sort hat Laufzeit THETA( n log n)
quicksort hat Laufzeit O( n ^ 2)
quicksort hat AVARAGE CASE Laufzeit Theta( n log n )
mehr als das muss man nicht wissen, dass quicksort seine schwächen hat. DENNOCH ist quicksort bei sortierungen von im hauptsoeicher befindlcihen dingen IMMER vorzuziechen!
im übrigen, wenn man das sortieren parallelisieren will (es gibt zwei varianten eines parallelen quicksorts) sieht die sache wieder anders aus: da sind dann z.b. selection sort oder odd-even-sort besser geeignet (im allgemeinen), wegen geringeren kommunikationsaufwand.
Ergänzung ()
maxwell-cs schrieb:Die Komplexität ist aber auch zum Beispiel O(n^231 * log(n)^n). Deshalb nimmt man für solche Aussagen Theta
wenn man sagen will, dass etwas schlecht ist, d.h. mindestens so langsam/schnell ist, dann nimmt man Omega. bei soilch einer aussage macht sich keiner die mühe ein Theta sicherzustellen.
im übrigen natürlich war mir klar, was du mit O-Notation gemeint hast. ich hab es ja auch nicht böse gemeint. dachte ich hätte das mit dem smilie und meinem haarspalter-vorwort deutlich gemeint. ich will nur sicherstellen, dass fachbegriffe hier von anderen nicht falsch gelernt werden. daraus erwachsen dann nämlich die ganzen halbwahrheiten.
Ergänzung ()
@ice-breaker
hier mal zwei beispiele warum deine analyse von der ersten seite total falsch ist:
1.
for( i=1 bis n) {
for( j=1 bis i) {
}
}
äussere laufzeit n, innere i. analog zu deiner rechnung folgt laufzeit n*i, weil i konstant folgt O(n).
du hast nämlich nur glück gehabt, dass in dem therm für die laufzeit der inneren schleife ein "n" vorkam. das geht aber selbst dann in die hose, wie man an beispiel 2 sieht:
2.
EDIT_ Beispiel 2 ist erstmal gestrichen. Hab da quatsch verzapft.
EDIT: mit anderen worten: deine analyse gibt rein zufällig für das beipsiel vom TE das richtige ergebnis aus. der weg dahin ist aber mehrfach völlig daneben.
Zuletzt bearbeitet:
maxwell-cs
Lt. Junior Grade
- Registriert
- Juli 2007
- Beiträge
- 465
klar, im allgemeinen schon. wenn man aber O(n^2) sowieso schon vorher gezeigt hat, kann man die laufzeit ja gleich mit Theta angeben.Dese schrieb:
prinzipiell hast du aber natürlich recht.
maxwell-cs: aufgrund deiner ausführung ist mir schon klar, dass du das weißt. ich korrigiere dich nur aus einem grund: andere die das lesen sollen es möglichst ganz richtig sehen sonst schlecihen sich fehlinterpretationen und halbwahrheiten ein.
deswegen bitte ich natürlich auch um korrekturen meiner ausführungen. eine habe ich bereits oben selbst vorgenommen - siehe edits.
deswegen bitte ich natürlich auch um korrekturen meiner ausführungen. eine habe ich bereits oben selbst vorgenommen
- siehe edits.Ich hab es mal jetzt auf eine einfachere Art und Weise versucht(danke für den link zum kleinen Gauss):
Angenommen wir haben einen Array mit 10 Feldern, dann haben wir im ersten Durchlauf 9, im zweiten 8, im dritten 7, ......0 Vergleiche.
9+8+7+6+5+4+3+2+1 sind ja (n-1) Zahlen, die jeweils in einer zweiten Zeile in umgekehrter Reihenfolge n ergeben.
9+8+7+6+5+4+3+2+1
1+2+3+4+5+6+7+8+9
Um die Summe der ersten zu erhalten muss dann nur noch mit 2 dividiert werden.
n[Wert]*(n-1)[Zahlen]/2 --> Anzahl der Vergleiche
In jedem der Vergleiche kann schlimmsten Falls ein Umtausch stattfinden. Im Durchschnitt jedes zweite Mal:
Das sind dann n*(n-1)/4 durchschnittliche Umspeicherungen.
Jetzt nur noch der Faktor 3, aufgrund der 3 notwendigen Operationen und die Summe aus Vergleich und Umtauschungen bilden um den Durchschnittsaufwand zu berechnen:
3n*(n-1)/4+n*(n-1)/2
Angenommen wir haben einen Array mit 10 Feldern, dann haben wir im ersten Durchlauf 9, im zweiten 8, im dritten 7, ......0 Vergleiche.
9+8+7+6+5+4+3+2+1 sind ja (n-1) Zahlen, die jeweils in einer zweiten Zeile in umgekehrter Reihenfolge n ergeben.
9+8+7+6+5+4+3+2+1
1+2+3+4+5+6+7+8+9
Um die Summe der ersten zu erhalten muss dann nur noch mit 2 dividiert werden.
n[Wert]*(n-1)[Zahlen]/2 --> Anzahl der Vergleiche
In jedem der Vergleiche kann schlimmsten Falls ein Umtausch stattfinden. Im Durchschnitt jedes zweite Mal:
Das sind dann n*(n-1)/4 durchschnittliche Umspeicherungen.
Jetzt nur noch der Faktor 3, aufgrund der 3 notwendigen Operationen und die Summe aus Vergleich und Umtauschungen bilden um den Durchschnittsaufwand zu berechnen:
3n*(n-1)/4+n*(n-1)/2
F_GXdx
Captain
- Registriert
- März 2006
- Beiträge
- 4.028
Eure Betrachtungen greifen allerdings etwas kurz: Neben der Laufzeit ist es auch wichtig für einen Suchalgorithmus, dass er gut parallelisierbar ist und sich damit gut auf Hardware implementieren lässt.
Das ist eben bei InsertionSort nicht der Fall, daher ist er sowieso schonmal schlecht.
Mit der Analyse sollte man es auch nicht übertreiben, da am Ende die Chance, dass man sich verrechnet höher ist, als der Präzisionsgewinn, wenn man irgendwelche komplizierten Umformungen betreibt.
Daher stellt man in der Praxis fest:
1) Der Algorithmus betrachtet jeden Eingabewert und macht etwas damit: n
2) Für jeden Eingabewert wird etwas gemacht: *
3) Das was gemacht wird, benötigt im schlimmsten Fall n Betrachtungen ("gegen Ende"): n
O(n^2)
Wobei man hier sehr schnell merkt, dass das in der Praxis nur wenig aussagt. Die ersten Elemente in einem Array kann InsertionSort extrem schnell sortieren (praktisch in linearer Zeit), während die Abschätzung für 3) extrem böse ist. Denn eigentlich geht es gegen Ende des Algorithmus darum, Daten in eine sortierte Liste einzufügen, und das ist in logarithmischer Zeit möglich (binäres einsortieren).
Ich persönlich müsste es mir jetzt genauer ansehen, es wirkt mir aber so, als wäre InsertionSort eigentlich in O(n log n), auch wenn das Wikipedia widerspricht.
Meine Behauptung ist jedenfalls, dass O(n^2) eine sehr schlechte und Praxis irrelevante Schranke von InsertionSort ist! Für den Average Case sowieso und auch für den Worst Case.
Was man jedoch festhalten muss ist, dass InsertionsSort wohl nur auf verlinkten Listen sehr effektiv ist, auf Arrays dagegen nicht. In der Praxis wird man aber nur selten Listen haben (Speicherbedarf). Wahrscheinlich liegt es daran.
Das ist eben bei InsertionSort nicht der Fall, daher ist er sowieso schonmal schlecht.
Mit der Analyse sollte man es auch nicht übertreiben, da am Ende die Chance, dass man sich verrechnet höher ist, als der Präzisionsgewinn, wenn man irgendwelche komplizierten Umformungen betreibt.
Daher stellt man in der Praxis fest:
1) Der Algorithmus betrachtet jeden Eingabewert und macht etwas damit: n
2) Für jeden Eingabewert wird etwas gemacht: *
3) Das was gemacht wird, benötigt im schlimmsten Fall n Betrachtungen ("gegen Ende"): n
O(n^2)
Wobei man hier sehr schnell merkt, dass das in der Praxis nur wenig aussagt. Die ersten Elemente in einem Array kann InsertionSort extrem schnell sortieren (praktisch in linearer Zeit), während die Abschätzung für 3) extrem böse ist. Denn eigentlich geht es gegen Ende des Algorithmus darum, Daten in eine sortierte Liste einzufügen, und das ist in logarithmischer Zeit möglich (binäres einsortieren).
Ich persönlich müsste es mir jetzt genauer ansehen, es wirkt mir aber so, als wäre InsertionSort eigentlich in O(n log n), auch wenn das Wikipedia widerspricht.
Meine Behauptung ist jedenfalls, dass O(n^2) eine sehr schlechte und Praxis irrelevante Schranke von InsertionSort ist! Für den Average Case sowieso und auch für den Worst Case.
Was man jedoch festhalten muss ist, dass InsertionsSort wohl nur auf verlinkten Listen sehr effektiv ist, auf Arrays dagegen nicht. In der Praxis wird man aber nur selten Listen haben (Speicherbedarf). Wahrscheinlich liegt es daran.
Zuletzt bearbeitet:
nö, ist es im allgemeinen nicht. scenarien in denen sich das lohnt UND sowohl das know how als auch das nötige framework dazu vorhanden sind im allgemeinen sehr sehr rar gesäht.F_GXdx schrieb:
was soll das damit zu tun haben? davon abgesehen sind mir keine wissenschaftlichen noch projekte im alltäglichen bussiness bekannt, die sortieralgorithem in hardware implementieren.
ne, der ist schon mal schlecht, weil er sowieso nu Theta(n^2) ist, keine vorteile gegenüber anderen verfahren hat und selbst für kleine eingabengrößen teils schlechtere konstanten hat als manch anderer.
ganz ehrlich... solche analysen sind nicht für jederman. für den programmierer reicht es zu verstehen, was so eine laufzeit analyse bedeutet (und die ALLER ALLER wenigsten tuen das, aber die meisten glauben das von sich) UND ein fundiertes vertständnis wie so etwas in rel. einfachen fällen geht um den eigenen code abschätzen zu können. das meiste was so programmiert wird ist nichts was kompliziert zu analysieren wäre.
kaum ein programmier der irgendwo als entwickler arbeitet erfindet irgendwelche ausgeklügelten algorithmen. sie wenden vorhande nur an oder passen sie an ihre situation etwas an.
also gerade in dem betrachteten beispiel sagt es verdammt viel aus. schon bei kleiner eingabe größe (20-80) fängt ein quicksort, ja selbst ein merge sort alle n^2 sortierverfahren in die tasche zu stecken.
deine behauptung ist schlcihtweg falsch. insertion sort ist sowohl im avarage case und damit auch im worst case n^2. das muss man sich nicht einmal genauer anschauen um das zu sehen, mit ein kleinen wenig erfahrung.
ich vermute mal du beziehst dich darauf, dass bei "normaler" benutzung von arrays hier beim einfügen alle nachfolgenden elemente verschoben werden müssen. damit hast du recht.
ABER, mit einer zwischenabbildung kann man listen effizient mit arrays implementieren und dann auch insertion sort die vorteile von arrays zu gute kommen lassen. der aufwand lohnt sich hier aber nicht da insertion sort ohnehin ne schlechte wahl ist.
ja leider wird in der praxis nur selten listen verwendet, viel zu selten. ganz besonders wird (was ich bisher so gesehen habe) in der praxis in projekten die auf java bauen arraylisten ohne ende genutzt AUCH dann wenn häufig elemente gelöscht und eingefügt werden.
oft ist dieser nachteil bedingt durch die eingabegrößen nicht bemerkbar.... aber oft genug nicht. in meiner neum job gerade bin ich der erste der linked lists nutzt. bisher wurden für alle listen IMMER arraylist genutzt.
demnächst führe ich da meine eigene single-linked-list ein statt der jaba linkedlist, weil
1. oft nur eine traversierungsrichtung nötig ist und diese weniger speicher verbracuht
2. java listen (nicht array basierte) gar nicht vollständig und sinnvoll implementiert hat. man kann defakto mit standard java möglichkeiten listen nicht so effizient verwenden, wofür sie erfunden wurden (es geht um das traversieren mit merheren iteratoren, das clonen von iteratoren, und das bearbeiten/löschen von elementen während man mit mehreren iteratoren die liste traversiert)
das sind funktionalitäten die viele algorithmen überhaupt erst effizient umsetztbar machen.
bei uns an der uni (naja seit mai arbeite ichi nicht mehr da) haben die leute von algorithm engineering die java hastables sogar ersetzt, weil sie zu lahm sind.
selbst google hat für entsprechende algorithmen eigene listen und iteratoren implementiert weil listen einfach nicht voll funktionsfähig sind in java....
sorry ich schweife ab. hab mich immer noch nicht von dem schock erholt, als ich diesen bockmist entdeckt hatte vor nen monat.
gute nacht
Ergänzung ()
kleiner nachtrag warum insertion sort auch im avarage case Theta(n^2) laufzeit hat:
die entscheidende beobachtung ist, dass bei einer zufälligen eingabe, zu jedem zeitpunkt während der ausführung die erwarte anzahl an schritten um das gerade neu einzusortierende element an seine richtige position zu setzten 1/2 mal Anzahl bereits vorhandenen elemente ist.
und genau das ist avarage case.
worst case ist trivial ... ne sortierte eingabe, passend gewählt absteigend oder aufsteigend, jeh nach implementierung. eben so, dass du für jedes neu einzufügende element bis ans ende laufen musst für die richtige einfüge position.
insertion sort ist nebenbei einer der am einfachsten zu analysierenden sortierverfahren (unter den klassischen).
edit: ich will hier mal betonen, weil hier so sprüche kommen, dass man es mit der analyse nicht übertreiben soll, und und und....
die analyse von insertion sort ist so ziemlich unterstes niveau. das ist so eines wenn nicht sogar DAS einstiegsbeispiel zum reinschnuppern im ersten semester. wer das nicht analysieren kann sollte es mit dem analysieren lieber ganz seien lassen (falls es er das mal gelehrt bekommen hat, denn hats null gefruchtet) oder halt anfangen das zu lernen (niemand wird mit dem wissen geboren).
Ergänzung ()
und noch was zum parrallen sortieren:
für paralleles sortieren wird fast ausschließlich sample sort oder seltener eine parallele variante von merge sort verwendet (es gibt einige scenarien wo dieses vorteilhaftger ist). alle anderen parallelisierten sortieralgorithmen werden kaum verwendet. paralleles sample sort (richtig implementiert) ist nicht zu schlagen, aufgrund seines vergleichsweise gering zu haltenen kommunikations overhead.
fast vergessen, paralleles odd-even-sort wird manchmal auch verwendet. ist gerade bei kleineren/mittelgrößen eingaben (klein ist hier immer noch größer als was man so unter groß bei sequenziellen problemen versteht). recht gut wegen guten kosntanten.
das mag sich irgendwann ändern wenn andere technologien für verbinsungen zwischen cores/cpus verwendung finden.
edit: wichtig: die wahl des parallelen sortieralgorithmus hängt SEHR stark von der topologie des kommunikationsnetzes ab. sind z.b. alle cpus nur in einer kette miteinander verbunden, dann ist odd-even-sort einfach unschlagbar!
gibt es schnelle broadcast und prefixsum möglichkeiten, haut sample-sort alles weg.
Zuletzt bearbeitet:
daemon777
Lt. Commander
- Registriert
- Dez. 2003
- Beiträge
- 1.371
Jetzt habt ihr mir Lust darauf gemacht mir mal für verschiedene Algorithmen Wege zur Parallelisierung zu überlegen
Ich fand die Diskussion hier sehr interessant und habe hier noch ein paar Punkte gefunden, denen ich mich noch widmen sollte, während andere Punkte mal wieder aufgefrischt wurden (obwohl ich noch im Studium bin. Manche werden eben früher alt ).
Aber eins darf man finde ich nicht vergessen, wenn man als Neuling anfängt die Laufzeit eines Algorithmusses asymptotisch zu bestimmen: die Aussagekraft dieses Ergebnisses sollte man immer anzweifeln.
Auch wenn QuickSort bei den meisten Anwendungen schneller ist als ein BubbleSort, so muss das nicht unbedingt immer so sein. Ein schönes Beispiel ist hier finde ich eine Zahlenfolge, von der bekannt ist, dass höchstens nur benachbarte Zahlen vertauscht werden müssen. Diese Zahlenfolge ist also vorsortiert. Ein Beispiel wäre hierfür: 1,3,2,4,5,7,6. Bei so etwas hat BubbleSort plötzlich eine Laufzeit von O(n).
Das sollte nur mal eine Anmerkung für alle Algorithmus-Interessierten sein und ist nicht als Belehrung der Diskutanten gedacht
Ich fand die Diskussion hier sehr interessant und habe hier noch ein paar Punkte gefunden, denen ich mich noch widmen sollte, während andere Punkte mal wieder aufgefrischt wurden (obwohl ich noch im Studium bin. Manche werden eben früher alt
).Aber eins darf man finde ich nicht vergessen, wenn man als Neuling anfängt die Laufzeit eines Algorithmusses asymptotisch zu bestimmen: die Aussagekraft dieses Ergebnisses sollte man immer anzweifeln.
Auch wenn QuickSort bei den meisten Anwendungen schneller ist als ein BubbleSort, so muss das nicht unbedingt immer so sein. Ein schönes Beispiel ist hier finde ich eine Zahlenfolge, von der bekannt ist, dass höchstens nur benachbarte Zahlen vertauscht werden müssen. Diese Zahlenfolge ist also vorsortiert. Ein Beispiel wäre hierfür: 1,3,2,4,5,7,6. Bei so etwas hat BubbleSort plötzlich eine Laufzeit von O(n).
Das sollte nur mal eine Anmerkung für alle Algorithmus-Interessierten sein und ist nicht als Belehrung der Diskutanten gedacht
@daemon777:
überschätzt diese beobachtung nicht. stell dir die frage, wie wahrscheinlich es ist, das so etwas passiert. bedenke bubble sort hat auch avarage case laufzeit von n^2, quick sort n log n.
schau dir mal n / log n an (den binären logarithmus, also zur basis 2):
bereits für n = 16 ergibt das 4. für n=32 ist das etwas über 6. für n=64 ist das schon über 10.
ein Theta(n^2) algorithmus muss also bei einer eingabegröße von 16 seine einzelnen operationen 4 mal schneller sein um mit einen n log n verfahren mithalten zu lönnen.
wenn man algorithmen auf ihre laufzeiten untersucht, dann werden (so weit möglich) nicht nur ihre worst cases analysiert, sondern im allgemeinen upper und lower bounds sowie avarage case, eben um sich nicht an so etwas aufzuhängen wie an einer worst case analyse, die aber wenig aussagt weil der algo im allgemeinen viel schneller läuft, da der worst case extrem selten ist (wie z.b. eben bei quicksort).
zum lernen und verstehen von laufzeitanalysen gehören zwei dinge: die mathematische analyse und das richtige interpretieren der ergebnisse im kontext.
ausserdem was spricht denn dagegen algorithmen für das selbe problem jeh nach eingabegröße oder anderer kriterien on the fly auszutauschen?
da fällt mir was lustiges ein:
ein ehemaliger kollege hat in einer klausur folgende aufgabe gestellt:
beschreibe einen sortieralgorithmus, der in best case laufzeit O(n) hat und in worst-case O(n log n).
kaum einer hat die gelöst, dabei ist es so sau einfach. bei der klausurbesprechung hat jeder zu sich selbst gesagt "man bin cih doof" - wahre story!
lösung:
lauf einmal deine eingabe durch und überprüfe ob sie sortiert ist
- falls ja -> fertig
- falls nein -> merge sort
für manche fragestellungen gibt es mächtige klassen von instanzen (also ne große menge von eingaben), die man anders schneller lösen kann. wenn das so ist und eine billige überprüfung existiert ob eine eingabe in solch einer klasse liegt, dann kann sich sowas lohnen.
im falle von quicksort ist aber die menge von eingaben (instanzen) so klein bei der quicksort significant über n log n ist (bei zufällig eingabe), dass es sich fast nie lohnt.
überschätzt diese beobachtung nicht. stell dir die frage, wie wahrscheinlich es ist, das so etwas passiert. bedenke bubble sort hat auch avarage case laufzeit von n^2, quick sort n log n.
schau dir mal n / log n an (den binären logarithmus, also zur basis 2):
bereits für n = 16 ergibt das 4. für n=32 ist das etwas über 6. für n=64 ist das schon über 10.
ein Theta(n^2) algorithmus muss also bei einer eingabegröße von 16 seine einzelnen operationen 4 mal schneller sein um mit einen n log n verfahren mithalten zu lönnen.
wenn man algorithmen auf ihre laufzeiten untersucht, dann werden (so weit möglich) nicht nur ihre worst cases analysiert, sondern im allgemeinen upper und lower bounds sowie avarage case, eben um sich nicht an so etwas aufzuhängen wie an einer worst case analyse, die aber wenig aussagt weil der algo im allgemeinen viel schneller läuft, da der worst case extrem selten ist (wie z.b. eben bei quicksort).
zum lernen und verstehen von laufzeitanalysen gehören zwei dinge: die mathematische analyse und das richtige interpretieren der ergebnisse im kontext.
ausserdem was spricht denn dagegen algorithmen für das selbe problem jeh nach eingabegröße oder anderer kriterien on the fly auszutauschen?
da fällt mir was lustiges ein:
ein ehemaliger kollege hat in einer klausur folgende aufgabe gestellt:
beschreibe einen sortieralgorithmus, der in best case laufzeit O(n) hat und in worst-case O(n log n).
kaum einer hat die gelöst, dabei ist es so sau einfach. bei der klausurbesprechung hat jeder zu sich selbst gesagt "man bin cih doof" - wahre story!
lösung:
lauf einmal deine eingabe durch und überprüfe ob sie sortiert ist
- falls ja -> fertig
- falls nein -> merge sort
für manche fragestellungen gibt es mächtige klassen von instanzen (also ne große menge von eingaben), die man anders schneller lösen kann. wenn das so ist und eine billige überprüfung existiert ob eine eingabe in solch einer klasse liegt, dann kann sich sowas lohnen.
im falle von quicksort ist aber die menge von eingaben (instanzen) so klein bei der quicksort significant über n log n ist (bei zufällig eingabe), dass es sich fast nie lohnt.
