Informatiker Board | Praktische Informatik | Laufzeit von Algorithmus SelectionSort Verständnisproblem

Informatiker Board » Themengebiete » Praktische Informatik » Laufzeit von Algorithmus SelectionSort Verständnisproblem » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 5 Beiträge

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

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.

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

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.

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