| Die letzten 4 Beiträge |
| Tobias |
angehender. 
|
| JROppenheimer |
danke danke, Du bist der beste 
was ist denn dein bildungshintergrund? informatiker? |
| Tobias |
Halte ich für korrekt. Dabei muss man allerdings immer aufpassen, welche Operationen man zählt und welche nicht. Ich gehe mal davon aus, dass die Laufzeit sich aus elementaren Vergleichs- und Kopieroperationen zusammensetzt.
Zuerst vergleicht man das einzufügende Element mit mit k Elementen bis zu der Stelle k, wo es eingefügt werden soll.
Danach muss man n-k-1 Elemente eins weiter kopieren und A[n] einsetzen. Dafür muss A[n] zwischengespeichert werden. Das würde also noch eine zusatzliche "+1" bei dir ergeben. Aber ich denke so pingelig sollten wir nicht sein. 
|
| JROppenheimer |
Rekrusionsgleichung für Laufzeit
Sei "Sortieren durch Einfügen" (Insertion Sort) rekursiv definiert, wie folgt:
Um A[1..n] zu sortieren, sortieren wir A[1..n-1] rekursiv, und setzen A[n] in das sortierte Feld ein.
Dazu soll eine Rekursionsgleichung für die Laufzeit geschrieben werden.
Meine Idee war folgende:
T(n) = 1 für n = 1 UND n+T(n-1) für n>1
Was denkt ihr? |
|
|
