Rikaan
Grünschnabel
Dabei seit: 03.02.2012
Beiträge: 3
 |
|
| 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 17:31 |
|
|
Nutzername
unregistriert
|
|
Frage 1:
Wenn ![[latex]t(m)=\alpha m+t(m-1)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=\alpha m+t(m-1)) (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]](http://www.matheboard.de/latex2png/latex2png.php?t(m-1)=\alpha (m-1)+t(m-2))
Somit ist ![[latex]t(m)=\alpha m+\alpha (m-1)+t(m-2)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=\alpha m+\alpha (m-1)+t(m-2))
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]](http://www.matheboard.de/latex2png/latex2png.php?t(2)=\alpha \cdot 2+t(1)) (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]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=2}^mi=\sum_{i=2}^mi+1-1=\sum_{i=1}^mi-1)
Jetzt kann man die Gaußsche Summenformel einsetzen.
|
|
|
03.02.2012 19:17 |
|
|
Rikaan
Grünschnabel
Dabei seit: 03.02.2012
Beiträge: 3
|
|
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
|
|
|
03.02.2012 22:04 |
|
|
Nutzername
unregistriert
|
|
| 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]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=m+t(m-1)) kann man die explizite Form ![[latex]t(m)=\sum_{i=2}^mi+t(1)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=\sum_{i=2}^mi+t(1)) machen.
Aus ![[latex]t(m)=t(m-1)+\beta[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=t(m-1)+\beta) wird ![[latex]t(m)=t(1)+(m-1)\cdot \beta[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=t(1)+(m-1)\cdot \beta) (arithmetische Reihe).
![[latex]t(m)=m\cdot t(m-1)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=m\cdot t(m-1)) ist gleichbedeutend mit ![[latex]t(m)=m!\cdot t(1)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?t(m)=m!\cdot t(1))
| 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]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=2}^mi=2+3+4+...+(m-2)+(m-1)+m)
Falls dir das etwas zu abstrakt ist, kannst du für m ja mal einen festen Wert einsetzen.
|
|
|
04.02.2012 10:58 |
|
|
Rikaan
Grünschnabel
Dabei seit: 03.02.2012
Beiträge: 3
|
|
| 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
|
|
|
04.02.2012 12:25 |
|
|
|
