Laufzeit von Algorithmus SelectionSort Verständnisproblem

03.02.2012, 17:31

Rikaan

Laufzeit von Algorithmus SelectionSort Verständnisproblem

Hallo,

ich lerne gerade für meine erste Mathe Klausur an der Uni und wir sollen dort auch die Laufzeit von Algorithmen berechnen können.

Ich habe mich intensiver mit dem SelectionSort Algorithmus beschäftigt und mir hierzu die Lösung angesehen, aber ich komme damit nicht zurecht, bzw. kann mir manche Schritte nicht erklären. In dem Screenshot sind direkt meine Fragen mit eingefügt, damit ich hier nicht einen ellenlangen Text schreiben muss.

SelectionSort

1. Kleinstes Element der Liste finden
2. Kleinstes Element an die Spitze der Liste setzen
3. Liste mit m-1Einträgen sortieren

Ich hoffe ihr könnt mir helfen

Mfg Rikaan

03.02.2012, 19:17

Auf diesen Beitrag antworten »

Nutzername

Frage 1:
Wenn $[latex]t(m)=\alpha m+t(m-1)[/latex]$ (das beta ignoriere ich mal, ändert an der Erklärung nichts),
dann kann man t(m-1) ersetzen durch $[latex]t(m-1)=\alpha (m-1)+t(m-2)[/latex]$
Somit ist $[latex]t(m)=\alpha m+\alpha (m-1)+t(m-2)[/latex]$
Das wiederholen wir jetzt sooft, bis wir t(1) dortstehen haben. Die letzte Ersetzung ist also: $[latex]t(2)=\alpha \cdot 2+t(1)[/latex]$ (Diese 2 ist es auch, die in der eckigen Klammer steht)
Wir brechen den Term also rekursiv herunter.

Frage 2:
Weil in der eckigen Klammer die Summanden von 2 bis m stehen.

Frage 3:
Ja:
$[latex]\sum_{i=2}^mi=\sum_{i=2}^mi+1-1=\sum_{i=1}^mi-1[/latex]$
Jetzt kann man die Gaußsche Summenformel einsetzen.

03.02.2012, 22:04

Auf diesen Beitrag antworten »

Rikaan

Hmm okay,

Kann ich daraus schließen, dass ich im Prinzip für alle rekursiven Algorithmen sagen kann: "ich schaue mir für die Summanden 2 bis m an"? oder ist dies ein Trugschluss?

Und was genau passiert mit dem m - X ?? Warum stehen dann da aufeinmal Zahlen ohne m, wo hin verschwindet das ?

Den Rest habe ich nun aber zum Glück verstanden, bzw. die Unklarheiten wurden beseitigt ^^

Vielen Dank bis hier =)

Rikaan

04.02.2012, 10:58

Auf diesen Beitrag antworten »

Nutzername

Zitat:

Kann ich daraus schließen, dass ich im Prinzip für alle rekursiven Algorithmen sagen kann: "ich schaue mir für die Summanden 2 bis m an"? oder ist dies ein Trugschluss?

Das kommt ganz darauf an, wie genau die Rekursionsvorschrift aussieht:
Aus der impliziten Form [latex]t(m)=m+t(m-1)[/latex]

kann man die explizite Form $[latex]t(m)=\sum_{i=2}^mi+t(1)[/latex]$ machen.
Aus $[latex]t(m)=t(m-1)+\beta[/latex]$ wird $[latex]t(m)=t(1)+(m-1)\cdot \beta[/latex]$ (arithmetische Reihe).

$[latex]t(m)=m\cdot t(m-1)[/latex]$ ist gleichbedeutend mit $[latex]t(m)=m!\cdot t(1)[/latex]$

Zitat:

Und was genau passiert mit dem m - X ?? Warum stehen dann da aufeinmal Zahlen ohne m, wo hin verschwindet das ?

Es verschwindet nicht, es steht im Summenzeichen:
$[latex]\sum_{i=2}^mi=2+3+4+...+(m-2)+(m-1)+m[/latex]$

Falls dir das etwas zu abstrakt ist, kannst du für m ja mal einen festen Wert einsetzen.

04.02.2012, 12:25

Auf diesen Beitrag antworten »

Rikaan

Zitat:

Es verschwindet nicht, es steht im Summenzeichen

Achso, ich verstehe, also ist das im Prinzip "die umgekehrte Reihenfolge" von dem, was zuvor in den eckigen Klammern stand.

Gut, dann habe ich die Lösung jetzt verstanden :-)

Na dann hoffe ich mal, dass ich das in der Klausur auch an einem unbekannten Algorithmus nachvollziehen kann ;-)

Vielen Dank

Rikaan

Neue Frage »

Antworten »

Laufzeit von Algorithmus SelectionSort Verständnisproblem

Verwandte Themen