---

Geschrieben von JROppenheimer am 19.11.2007 um 14:06:

  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?

---

Geschrieben von Tobias am 19.11.2007 um 15:24:

 

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.

---

Geschrieben von JROppenheimer am 19.11.2007 um 15:47:

 

danke danke, Du bist der beste

was ist denn dein bildungshintergrund? informatiker?

---

Geschrieben von Tobias am 19.11.2007 um 15:52:

 

angehender.