Rekrusionsgleichung für Laufzeit |
| 19.11.2007, 14:06 | Auf diesen Beitrag antworten » |
| 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? |
|
|
|
| 19.11.2007, 15:24 | Auf diesen Beitrag antworten » |
| 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. 
|
| 19.11.2007, 15:47 | Auf diesen Beitrag antworten » |
| JROppenheimer | danke danke, Du bist der beste 
was ist denn dein bildungshintergrund? informatiker? |
| 19.11.2007, 15:52 | Auf diesen Beitrag antworten » |
| Tobias | angehender. 
|
| Anzeige | |
|
|
|
|
|
