Sortieralgorithmen-Aufwandsanalyse

[Chris95]

Wie kann ich mathematisch den Aufwand von Sortieralgorithmen bestimmen.
z.B. beim SelectionSort/Sortieren durch Auswählen

Algorithmus:
http://www.matheprisma.uni-wuppertal.de/Module/Sortieren/index.htm
Bitte überfliegt einmal diese Seite.

Nun ist bei Matheprisma die Aufwandsanalyse folgender Maßen veranschaulicht.

Die erste i-Schleife muss n-1 mal durchlaufen werden.
(ist ja auch logisch da, das letzte Element nicht mit sich selber verglichen wird)
Die zweite Schleife muss (n-(i+1))mal durchgelaufen werden.
(Das nächste Element wird verglichen, deswegen i +1, und die noch zu sortierende Liste nimmt kontinuierlich ab, deswegen wird i+1 auch von n abgezogen).

Meine frage ist dann wie ich mittels eines Terms nun die Abhängigkeit der Speichervergleiche von n- der Felder des Array bzw. der Liste ausdrücke und evtl vereinfache, sodass ich die Gleichung wie bei Matheprisma erhalte.

Für die Speichervertauschungen müsste es ähnlich funktionieren - nur mit dem faktor 3 aufgrund der 3 damit verbundener Speicheroperationen multipliziert werden.

danke

 

[DJND]

Der Aufwand hier wäre n*n => n^2

In der Aufwandsbestimmung ist ein Daumenmaß gefragt. Ob du nun n Elemente oder n-1 Elemente durchläufst ist ein unwichtiges Detail. Es ist und bleibt n. Und da du n Elemente genau n mal durchlaufen mußt (pro Element ein Durchlauf) landest du bei n*n.

Es ist nicht der exakte Aufwand gefragt sondern es stellt sich vielmehr die Frage, wie der Aufwand sich verhält wenn man nicht 10 sondern 100, 1000 oder noch höhere Größenordnungen damit verarbeiten würde. Ein doppelt so großes Array zum Sortieren würde nicht einfach zu einer Verdopplung des Aufwandes führen sondern zu... dem vierfachen. Eine Verzehnfachung des Aufwandes führt also zu einer Verhundertfachung des Aufwandes.

Oh, auch ein simpler Faktor - basierend auf benötigten Operationen - wird ignoriert hierbei.

 

[miac]

Ich weiß jetzt nicht genau, welches der Verfahren Du meinst. Generell ist das aber ein Thema von Folgen und Reihen. Ist wie die berühmten ersten 100 Zahlen zusammenzuzählen. Das geht per Überlegung oder mit Fleiß.

 

[Sneazel]

http://de.wikipedia.org/wiki/Selectionsort
?
Weiß nicht genau was du wissen willst

 

[R3ddy]

Da es auf der von dir verlinkten Seite eigentlich recht gut erklärt ist, vermute ich, dass dir ein paar mathematische Grundlagen Fehlen. Eventuell helfen dir diese Links weiter:

Summenzeichen
Gaußsche Summenformel

 

[Keepers]

Ich hab das jetzt nicht alles durchgelesen - aber Komplexität und Laufzeitanalysen-Schätzung macht man mit O-Notation. Ein Teilgebiet der theoretischen Informatik.

Konstanten werden weggelassen.

Für deine 2 Schleifen bedeutet das.

FOR i to n-1
FOR j to n-(i+1)

n-1 * n-(i+1) -> weil i bis n-1 läuft und Konstanten weggelassen werden: O(n^2)

http://michaelgoerz.net/studies/semester01/comp_sci2/inf_skript.pdf oder auch jedes andere Buch, dass sich mit Thoretischer Informatik beschäftigt (Empfehlung: Uwe Schöning - Theoretische Informatik kurzgefasst)

 

[Chris95]

Danke, für die schnellen Antworten;
Ich habe es jetzt einiger Maßen verstanden.
"n-1 * n-(i+1) -> weil i bis n-1 läuft und Konstanten weggelassen werden: O(n^2)"(Keepers)
das ist wahrscheinlich das wichtigste und Danke für die links.

 

[ice-breaker]

Wenn du es genau rechnest kommt ja "n^2 - n - i - 1" raus. Die Konstanten "-i - 1" kommen weg, das stimmt. Damit bleibt noch der Termin "n^2 - n" übrig. In der Laufzeit wird n^2 dominieren und -n wird bei großem n somit irrelevant (teste doch mal mit n = 100) und deswegen verschwindet auch -n.

Verkürzte einfache Fassung, das kann man noch ne Ecke komplexer und richtiger ausdrücken, aber das trifft es schon relativ gut

 

[Daaron]

Oder anders: Es ähnelt gravierend der guten alten Limes-Berechnung, die wir doch hoffentlich alle im Abitur mitgenommen haben.... Du guckst scharf hin, welcher Teil der Gleichungen signifikant stärker wächst als der Rest und ignorierst diesen Rest, weil er irgendwann eh irrelevant wird.

oder kennen heutige Abiturienten nur noch den Wodka Erdbeer Limes?

 

[Keepers]

Wir könnten es auch gleich formal definieren - aber aus Erfahrung verstehen das dann wirklich nur diejenigen, die sich damit beschäftigt haben oder Mathematiker ;-)
Der Limes ist ein guter Vergleich ;-)

 

[protossgamer]

man kann sich noch den aufwand fuer den "besten" bzw den "schlechtesten" fall untersuchen. wobei letzterer der entscheidene ist.

 

[nullPtr]

Ganz ehrlich... hier sträuben sich jedem theoretischen Informatiker ja die Haare
Weder ist "i" eine Konstante, noch kann es einfach weggelassen werden.

Diese Art von Schleifen analysiert man nicht einfach, in dem "i" a la "n * (n-i)" reinmultipliziert.
R3ddy hat hier den korrekten Vorschlag gemacht: Gaußsche Summe. Genau so wird es auch in der Wikipedia analysiert und das ist die einzig akzeptable Analyse für diese Art von ineinander geschachtelte Schleifen.

 

[Keepers]

man kann sich noch den aufwand fuer den "besten" bzw den "schlechtesten" fall untersuchen. wobei letzterer der entscheidene ist.

Ganz ehrlich... hier sträuben sich jedem theoretischen Informatiker ja die Haare
Weder ist "i" eine Konstante, noch kann es einfach weggelassen werden.

Diese Art von Schleifen analysiert man nicht einfach, in dem "i" a la "n * (n-i)" reinmultipliziert.
R3ddy hat hier den korrekten Vorschlag gemacht: Gaußsche Summe. Genau so wird es auch in der Wikipedia analysiert und das ist die einzig akzeptable Analyse für diese Art von ineinander geschachtelte Schleifen.

Dann fordere ich dich jetzt auf, die O-Notation formal dafür zu definieren, anstatt von Haare sträuben zu reden. Mit einem Beweis lasse ich mich gerne überzeugen.

i als Zählvariable ist eine Bedingung für den Zweiten Zähler. Dieser ist aber dadurch immernoch mit n austauschbar.
Ich bleibe immernoch bei der Abschätzung der oberen Schranke für O(n^2).

Gerne darfst du dich nun aber formal als theoretischer Informatiker austoben und meinen Fehler aufdecken und gegenbeweisen. Das schadet mir nicht, sondern frischt eher mal wieder auf ;-)

 

[Dese]

nullPtr hat recht. so ist das falsch gemacht.

die obere abschätzung von O(n^2) ist zwar richtig, aber errechnet wird dies anders. i ist schonmal keine konstante und so auch nicht anzunehmen. hier mal die richtige rechnung:

(man beachte, dass ich nciht überprüft habe ob die getroffenen annahmen für das sortierverfahren überhaupt stimmen. ich glaub euch da mal)

- außere schleife n-1 viele durchläufe
- innere n-(i+1) viele im i-ten durchlauf der äusseren:

==>

summe von i=1 bis n-1 ( n-i-1) = summe von i=1 bis n-1 ( i-1) = summe von i=0 bis n-2 ( i) = summe von i=1 bis n-2 ( i)

und es gilt: für summe von k=1 bis m (k) = m(m+1) / 2 (siehe http://en.wikipedia.org/wiki/Summation)

==>
summe von i=1 bis n-2 ( i) = (n-2)(n-1)/2 = O(n^2)

edit: und zur O-Notation (wohl gemerkt GROß O!!!) gilt:

f(x) = O(g(x)) <=> Es gibt eine Konstante c mit für alle x : f(x)<= c g(x)

Ergänzung (12. September 2012)

Ich hab das jetzt nicht alles durchgelesen - aber Komplexität und Laufzeitanalysen-Schätzung macht man mit O-Notation. Ein Teilgebiet der theoretischen Informatik.

hierzu muss ich zwei dinge sagen:
1. man macht keine analyse mit O-Notation. O-Notation ist eine NOTATION also eine formale schreibweise und kein analyseverfahren
2. ist O-Notation kein Teilgebiet, es ist überhaupt kein Forschungs oder Anwendungsgebiet. es ist nur eine NOTATION!

Man verwendet die O-Notation um bestimmte beziehungen zwischen funktionen einfach niederzuschreiben/auszudrücken (siehe edit in meinem vorigen post).

edit: ich habe 6 Jahre als Forscher in der Theoretischen Informatik gearbeitet. das hier sind grundlagen aus dem ersten oder höchstens 2ten semester informatik bei uns an der uni.

 

[Keepers]

i ist schonmal keine konstante und so auch nicht anzunehmen.

Ich habe auch nie behauptet, dass i eine Konstante ist.
Da es aber sehr wohl mit der äußeren Schleife korreliert und dementsprechend zu beachten ist, und die restlichen Konstanten wegfallen, lässt sich sehr schnell die obere Schranke aufzeigen und dominieren.

Dem Summationssatz ist nichts hinzuzufügen. Entweder habe ich mich zu unklar ausgedrückt, oder für Leute die auch etwas davon verstehen zu "larifari" ;-)

1. man macht keine analyse mit O-Notation. O-Notation ist eine NOTATION also eine formale schreibweise und kein analyseverfahren

Korrekt.

2. ist O-Notation kein Teilgebiet, es ist überhaupt kein Forschungs oder Anwendungsgebiet. es ist nur eine NOTATION!

Gehört zur Komplexitätstheorie, was eindeutig ein Teilgebiet der theoretischen Informatik ist.

ch habe 6 Jahre als Forscher in der Theoretischen Informatik gearbeitet. das hier sind grundlagen aus dem ersten oder höchstens 2ten semester informatik bei uns an der uni

Das freut mich für dich - dass es in den Grundlagenvorlesungen enthalten ist, ist glaube ich fast ein Standard. Zumindest für jede Uni die das ordentlich macht ;-)

 

[Dese]

Wenn du es genau rechnest kommt ja "n^2 - n - i - 1" raus. Die Konstanten "-i - 1" kommen weg, das stimmt. Damit bleibt noch der Termin "n^2 - n" übrig. In der Laufzeit wird n^2 dominieren und -n wird bei großem n somit irrelevant (teste doch mal mit n = 100) und deswegen verschwindet auch -n.

die "genaue" rechnung würde mich mal interessieren.

Verkürzte einfache Fassung, das kann man noch ne Ecke komplexer und richtiger ausdrücken, aber das trifft es schon relativ gut

ich denke das ist schon genau gerechnet, wie kann es dann richtiger ausgedrückt werden?

das da oben ist totaler quatsch!

Ergänzung (12. September 2012)

Ich habe auch nie behauptet, dass i eine Konstante ist.

habe ich dir auch nicht direkt vorgeworfen.
ice-breaker war das.

nullPtr hat das kritisiert und du hast ... sagen wir mal etwas eingeschnappt dich gegen die kritik gewehrt indem du ihn aufgefordert hast es besser zu machen... einfach ausgedrückt.

Da es aber sehr wohl mit der äußeren Schleife korreliert und dementsprechend zu beachten ist, und die restlichen Konstanten wegfallen, lässt sich sehr schnell die obere Schranke aufzeigen und dominieren.

welche restlichen konstanten? überhaupt, welche konstanteN. es gibt nur eine einzige, und das ist "n".

und bitte bitte BITTE! mach mal pause bei der verwendung von fachbegriffen ohne wirklich zu wissen was sie bedeutet.... korreliert die aussage macht keinen sinn.

Dem Summationssatz ist nichts hinzuzufügen. Entweder habe ich mich zu unklar ausgedrückt, oder für Leute die auch etwas davon verstehen zu "larifari" ;-)

mindestens unklar. das was da in den ersten posts so steht ist schlichtweg falsch.

Ergänzung (12. September 2012)

Korrekt.

ich frag mich von wem ich mir das hier sagen lassen muss.... bei dem was ich hier gelesen habe. sorry.

Gehört zur Komplexitätstheorie, was eindeutig ein Teilgebiet der theoretischen Informatik ist.

ich will dich erst gar nicht mal über komplexitätstheorie fragen...

aber so oder so O-Notation ist kein Teilgebiet, auch wenn es in einem Teilgebiet verwendet oder gar definiert wird.

 

[Keepers]

und bitte bitte BITTE! mach mal pause bei der verwendung von fachbegriffen ohne wirklich zu wissen was sie bedeutet.... korreliert die aussage macht keinen sinn.

Das kann ich wiederum nicht nachvollziehen - als Korrelation beschreibt man die Ahängigkeit von 2 Größen.
Eine innere Schleife ist immer abhängig von ihrer äußeren. Wie auch immer du das nun anders interpretieren wolltest.

 

[Dese]

Das kann ich wiederum nicht nachvollziehen - als Korrelation beschreibt man die Ahängigkeit von 2 Größen.

Falsch!!!

korrelation und abhäöngigkeit sind zwei verschiedene dinge!

Eine innere Schleife ist immer abhängig von ihrer äußeren. Wie auch immer du das nun anders interpretieren wolltest.

auch falsch. eine innere schleife ist nicht IMMER abhängig von ihrer äusseren, bis auf die eigenschaft überhaupt wenigstens einmal ausgeführt zu werden. beispiel:

for(i=1 bis n) {
for(j=1 bis m) {

}
}

die inner schleife läuft völlig unabhängig von der äusseren m-mal.


EDIT: darf ich mal fragen ob du dieses "Wissen" dir selbst aus dem inet oder büchern zusammen gesucht hast oder ob du informatik oder ähnliches an einer fh oder uni studierst?

edit2: dieser edit war quatsch

 

[Keepers]

Wir verlagern mal auf PN ;-)

 

[Chris95]

Hieraus ist ja ein richtiger Diskussionsthread entstanden.
Ich bin ehrlich gesagt im Moment noch Schüler der Q1 am Gymnasium und im Informatik-unterricht beschäftigen wir uns im Moment mit Sortierverfahren.
Dabei wollten wir den Aufwand des SelectionSortverfahrens und des BubbleSortverfahrens vergleichen.
Wir haben festgestellt,dass diese annähernd gleich sind.
Dabei wurde die Aufwandsanalyse nur schnell durch den Lehrer angeschrieben.
Teilweise verstehe ich sie ja;
Ich glaub es ist auch nicht so wirklich relevant, sondern wir wollten eher die Effizienz der Verfahren beurteilen.
Nur interessiert mich es sehr stark, wie sie mathematisch und schrittweise durchgeführt wird.
Den Limes kenne ich aus der EP (Differentialgleichungen) und mit dem Summenzeichen habe ich nur kurz bei Regressionsgeraden, die leider nur kurz und nur in der Vorgehensweise erläutert wurden.
ich werde mir es dann selber erarbeiten müssen.
danke für eure Unterstützung, die Beiträge sind hilfreich
Gruß
Chris95