Laufzeit berechnen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:07 So 09.10.2011 | | Autor: | volk |
| Aufgabe | Algorithmus praefix-sum(A)
1 integer n = length(A);
2 erzeuge Feld S mit n Elementen;
3 integer a;
4 for i=0 to n-1 do
5 a=0;
6 for j=0 to i do
7 a=a+A[j];
8 od
9 S[i]=a/(i+1);
10 od |
Hallo,
ich möchte die Laufzeit des Algorithmus berechnen, komme aber nicht auf die vorgegebene Lösung. Für die Schleifen zählen wir ohne Befehle darin 2n Operationen (inkl. Vergleiche zum Abbruch)
In den Zeilen 1-3 habe ich 3 Operationen.
Die erste for-Schleife sind 2(n+2) [+2 wegen Zeile 5 und 9]
Die zweite for-Schleife 2(n+1) [+1 wegen Zeile 7]
Das macht zusammen [mm] T(n){\le}3+2(n+2)2(n+1)=3+4(n+1)(n+2)=3+4n^2+12n+8=11+12n+4n^2 [/mm] und das ist [mm] O(n^2)
[/mm]
In der Musterlösung steht jetzt allerdings [mm] T(n)=3+\summe_{i=0}^{n-1}(2+2(i+2)+(i+1))
[/mm]
Das ist natürlich genauer als das was ich raus habe, nur verstehe ich die Lösung nicht wirklich.
Die 3 vor der Summe sind ja die konstanten Operationen vor der ersten for-Schleife und die Summe kommt von der ersten for-Schleife. Der Rest ist mir aber nicht so klar.
Vielleicht hat jemand einen Tip.
Gruß volk
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:46 So 09.10.2011 | | Autor: | felixf |
Moin volk!
> Algorithmus praefix-sum(A)
>
> 1 integer n = length(A);
> 2 erzeuge Feld S mit n Elementen;
> 3 integer a;
> 4 for i=0 to n-1 do
> 5 a=0;
> 6 for j=0 to i do
> 7 a=a+A[j];
> 8 od
> 9 S=a/(i+1);
> 10 od
> Hallo,
> ich möchte die Laufzeit des Algorithmus berechnen, komme
> aber nicht auf die vorgegebene Lösung. Für die Schleifen
> zählen wir ohne Befehle darin 2n Operationen (inkl.
> Vergleiche zum Abbruch)
>
> In den Zeilen 1-3 habe ich 3 Operationen.
> Die erste for-Schleife sind 2(n+2) [+2 wegen Zeile 5 und
> 9]
> Die zweite for-Schleife 2(n+1) [+1 wegen Zeile 7]
Das ist ziemlich grob abgeschaetzt. Auch wenn's asymptotisch auf's gleiche hinauslaeuft.
> Das macht zusammen
> [mm]T(n){\le}3+2(n+2)2(n+1)=3+4(n+1)(n+2)=3+4n^2+12n+8=11+12n+4n^2[/mm]
> und das ist [mm]O(n^2)[/mm]
>
> In der Musterlösung steht jetzt allerdings
> [mm]T(n)=3+\summe_{i=0}^{n-1}(2+2(i+2)+(i+1))[/mm]
>
> Das ist natürlich genauer als das was ich raus habe, nur
> verstehe ich die Lösung nicht wirklich.
>
> Die 3 vor der Summe sind ja die konstanten Operationen vor
> der ersten for-Schleife und die Summe kommt von der ersten
> for-Schleife. Der Rest ist mir aber nicht so klar.
Die erste 2 in der Summe sind die 2 Befehle, die du pro Schleifeniteration ausfuehrst. (Insgesamt sind es ja $2 n$ Befehle fuer die ganze Schleife, wenn man den Inhalt der Schleife ignoriert.)
Dann wird die innere Schleife $i + 1$-mal durchlaufen, du hast also schonmal $2 (i + 1)$ Befehle rein fuer die Schleife und nochmal $i + 1$ Befehle fuer den Inhalt. Weiterhin hast du 2 weitere Befehle (Zeilen 5 und 9), die in jeder Iteration der aeusseren Schleife ausgefuehrt werden.
D.h. in der aeusseren Schleife werden $2 + 2 (i + 1) + (i + 1) + 2$. Das ist gerade gleich $2 + 2 (i + 2) + (i + 1)$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:10 So 09.10.2011 | | Autor: | volk |
Moin felixf,
vielen Dank für deine schnelle und sehr ausführliche Antwort.
LG
|
|
|
|
