 Rekrusionsgleichung für Laufzeit |
|
|
| 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?
__________________
I'm 71% Megatron!
|
|
19.11.2007 14:06 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
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:24 |
|
|
|
|
danke danke, Du bist der beste 
was ist denn dein bildungshintergrund? informatiker?
__________________
I'm 71% Megatron!
|
|
|
19.11.2007 15:47 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
angehender. 
|
|
|
19.11.2007 15:52 |
|
|
|
