Laufzeitanalyse & Summen(Sigma < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:48 Sa 04.06.2011 | | Autor: | teremy |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo, ich habe eine Frage bezüglich der Umformung bei Summen mit der Sigmaschreibweise.
Das ganze findet unter der Überschrift der Laufzeitanalyse statt, daher hier erstmal der Pseudocode, dessen Laufzeit bestimmt werden soll:
InsertionSort(Array A)
| 1: |
| | 2: | for j = 2 to length[A] do
| | 3: | key = A[j]
| | 4: | i = j-1
| | 5: | while i > 0 and A[i]>key do
| | 6: | A[i+1] = A[i]
| | 7: | i = i-1
| | 8: | A[i+1] = key
|
Bei Eingabegröße n haben wir dann am Ende folgendes raus:
[mm]5+-4+3\summe_{}^{} t_j[/mm]
[mm] t_j [/mm] ist die Anzahl der Wiederholungen der while-Schleife bei Laufindex j
Erste Frage:
Da wir eine Worst-Case Analyse machen, wieso ist der schlechteste Fall dann [mm] t_j [/mm] = j-1
Der schlechteste Fall ist natürlich die absteigend sortierte Eingabe ( wir wollen aufsteigend sortieren ), aber wieso j-1?
Dann wird in der Summe etwas umformuliert:
[mm]T(n) = 5n-4+3*\summe_{j=2}^{n} (j-1) = 4n-4+3*\summe_{j=1}^{n} j [/mm]
Die zweite Frage ist, wie genau diese Umformung vonstatten ging?
Danke im Voraus
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:11 So 05.06.2011 | | Autor: | felixf |
Moin!
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Hallo, ich habe eine Frage bezüglich der Umformung bei
> Summen mit der Sigmaschreibweise.
> Das ganze findet unter der Überschrift der Laufzeitanalyse
> statt, daher hier erstmal der Pseudocode, dessen Laufzeit
> bestimmt werden soll:
>
> InsertionSort(Array A)
> | 1: |
| | 2: | > for j = 2 to length[A] do
| | 3: | > key = A[j]
| | 4: | > i = j-1
| | 5: | > while i > 0 and A[i]>key do[/i]
| | 6: | > [i] A[i+1] = A[i][/i][/i]
| | 7: | > [i][i] i = i-1[/i][/i]
| | 8: | > [i][i] A[i+1] = key[/i][/i]
| | 9: | > [i][i] |
[/i][/i]
>
> Bei Eingabegröße n haben wir dann am Ende folgendes
> raus:
> [mm]5+-4+3\summe_{}^{} t_j[/mm]
>
> [mm]t_j[/mm] ist die Anzahl der Wiederholungen der while-Schleife
> bei Laufindex j
>
> Erste Frage:
> Da wir eine Worst-Case Analyse machen, wieso ist der
> schlechteste Fall dann [mm]t_j[/mm] = j-1
> Der schlechteste Fall ist natürlich die absteigend
> sortierte Eingabe ( wir wollen aufsteigend sortieren ),
> aber wieso j-1?
Nun, die Laufvariable der inneren Schleife wird doch mit $j - 1$ initialisiert. Und wenn die andere Abbruchbedingung nicht eintritt, wird die innere Schleife somit $j - 1$ mal durchlaufen.
> Dann wird in der Summe etwas umformuliert:
> [mm]T(n) = 5n-4+3*\summe_{j=2}^{n} (j-1) = 4n-4+3*\summe_{j=1}^{n} j[/mm]
>
> Die zweite Frage ist, wie genau diese Umformung vonstatten
> ging?
Nun: $3 [mm] \sum_{j=2}^n [/mm] (j - 1) = 3 [mm] \sum_{j=2}^n [/mm] j - 3 [mm] \sum_{j=2}^n [/mm] 1$ (einfach ausmultiplizieren). Jetzt ist [mm] $\sum_{j=2}^n [/mm] 1 = n - 1$, da die Summe genau $n - 1$ Summanden hat (und die alle 1 sind). Also ist $3 [mm] \sum_{j=2}^n [/mm] (j - 1) = 3 [mm] \sum_{j=2}^n [/mm] j - 3 (n - 1)$.
LG Felix
|
|
|
|
