Laufzeit einer Prozedur

07.05.2011, 15:17

OhneWitz

Laufzeit einer Prozedur

Folgende Aufgabe:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

// Laufzeit als Anzahl des Print-Befehls
public static void nichts(int n)
{
    for(int i=1; i<=n-1; i++)
        for(int j=i+1; j<=n; j++)
            for(int k=1; k<=j; k++)
                System.out.println("nichts");
}

Hinweis:
Es gilt: $\begin{eqnarray*} \sum\limits_{i=1}^n i^{2}=\frac{n*(n+1)*(2n+1)}{6} \end{eqnarray*}$

Schreiben Sie ein Test-Programm und bestimmen Sie die Anzahl der Print-Befehle für n = 1,2,3,4,... Wie lautet die allgemeine Summenformel?

Ergebnisse des Testprogramms:
n=0 count=0
n=1 count=0
n=2 count=2
n=3 count=8
n=4 count=20
n=5 count=40
n=6 count=70
n=7 count=112
n=8 count=168
n=9 count=240
n=10 count=330

Mein Lösungsversuch

Also für die äußeren beiden Schleifen sollte gelten:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i \end{eqnarray*}$

und für das gesamte Konstrukt dachte ich mir, müsste dann innerhalb der Summenformel nochmal ne Summe kommen:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} (\sum\limits_{k=1}^i k ) \end{eqnarray*}$

Das Ganze hab ich dann erstmal auseinander gezogen:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} (\sum\limits_{k=1}^i k ) = \sum\limits_{i=1}^{n-1} (\frac{i*(i+1)}{2} ) = \frac{1}{2}*\sum\limits_{i=1}^{n-1} (i^{2}+i)= \frac{1}{2}*\sum\limits_{i=1}^{n-1}(i^{2} ) + \frac{1}{2}*\sum\limits_{i=1}^{n-1}(i) \end{eqnarray*}$

Und anschließend die beiden Summenformeln eingesetzt + ausmultipliziert:
$\begin{eqnarray*} \frac{1}{2}(\frac{(n-1)*((n-1)+1))*(2(n-1)+1)}{6} +\frac{1}{2}(\frac{(n-1)(n-1+1)}{2})=\frac{2n^{3}-5n^{2}+3n}{12}+\frac{n^{2}-n}{4} \end{eqnarray*}$

Und dann kam ich am Ende auf:
$\begin{eqnarray*} \frac{2n^{3}-2n^{2} }{12} \end{eqnarray*}$

Wenn man das allerdings zum testen durchrechnet, kommt man auf falsche Ergebnisse. (z.B. mit n=5 = 200/12, wobei 40 rauskommen sollte)

War mein Ansatz schon komplett falsch oder hab ich irgendwo beim Rechnen Fehler gemacht?

07.05.2011, 17:23

Abakus

Auf diesen Beitrag antworten »

RE: Laufzeit einer Prozedur

Zitat:

Original von OhneWitz
Also für die äußeren beiden Schleifen sollte gelten:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i \end{eqnarray*}$

Hallo,

was genau soll hier gelten, du schreibst nur eine Summe hin und sonst nichts?

Wenn das die Zahl der Prints sein soll, stimmt das nicht jedenfalls. Wenn es die Anzahl der Durchläufe der beiden äußeren Schleifen sein soll, brauchst du vielleicht eine Doppelsumme.

(Wieso muss der Leser eigentlich raten, was du genau meinst?)

Grüße Abakus smile

07.05.2011, 17:33

OhneWitz

Auf diesen Beitrag antworten »

RE: Laufzeit einer Prozedur

Zitat:

Original von Abakus

Zitat:

Original von OhneWitz
Also für die äußeren beiden Schleifen sollte gelten:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i \end{eqnarray*}$

Also als Erklärung dazu. Ich habe vorher eine andere Aufgabe bearbeitet gehabt.

code:
1: 2: 3: 4: 5:	for(int i=n; i>0; i--) for(int j=i; j<n; j++) count++;

Hierbei war das Ergebnis für die count-Inkrementierungen:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i \end{eqnarray*}$

Wenn man nun diese Aufgabe mit der oberen Aufgabe vergleicht, also:

code:
1: 2: 3: 4: 5: 6:	for(int i=1; i<=n-1; i++) for(int j=i+1; j<=n; j++) for(int k=1; k<=j; k++) System.out.println("nichts");

Fällt einem auf, dass zwar bei den beiden äußeren Schleifen ein wenig anders gezählt wird, aber die äußerste Schleife ebenfalls n-1 mal durchlaufen wird, und wenn das "count++;" in der 2. Schleife stehen würde, würde man ebenfalls aufs gleiche Ergebnis kommen, also:

$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i \end{eqnarray*}$

An dieser Stelle, wo bei der anderen Aufgabe das count war, steht ja aber nun noch eine weitere Schleife. Weshalb ich annehme, dass man über folgendes Konstrukt an die Anzahl der Print-Befehle kommt:

$\begin{eqnarray*} prints = \sum\limits_{i=1}^{n-1} (\sum\limits_{k=1}^i k ) \end{eqnarray*}$

Zitat:

(Wieso muss der Leser eigentlich raten, was du genau meinst?)

Grüße Abakus smile

Dies war selbstverständlich keine Absicht. Betriebsblindheit: Wenn man stundenlang an so ner Aufgabe gesessen hat, nimmt man manche Sachen einfach als selbstverständlich hin, wo für eine außenstehende Person dann der Bezug fehlt.

Ich hatte jedenfalls versucht, die Situation so genau wie möglich zu beschreiben.

07.05.2011, 18:22

Abakus

Auf diesen Beitrag antworten »

RE: Laufzeit einer Prozedur

Zitat:

Original von OhneWitz
Also als Erklärung dazu. Ich habe vorher eine andere Aufgabe bearbeitet gehabt.

code:
1: 2: 3: 4: 5:	for(int i=n; i>0; i--) for(int j=i; j<n; j++) count++;

Hierbei war das Ergebnis für die count-Inkrementierungen:
$\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i \end{eqnarray*}$

Also von hier stammt die Formel dann, ok.

Wenn wir $\begin{eqnarray*} n = 100 \end{eqnarray*}$ annehmen, ist $\begin{eqnarray*} count = 4.950 = \frac 1 2 \cdot (n-1) \cdot n \end{eqnarray*}$ also. Letzteres ist ein einfacherer Ausdruck für deine Summe (stimmt soweit).

Mein Ansatz zu den 3 Schleifen wäre von innen nach außen vorzugehen und das jeweils als Summe zu schreiben:

$\begin{eqnarray*} AnzahlPrints = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 \end{eqnarray*}$

Das wird jetzt nacheinander ausgerechnet:

$\begin{eqnarray*} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} j \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{i=1}^{n-1} (\sum_{j=1}^{n} j - \sum_{j=1}^{i} j) \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{i=1}^{n-1} (\frac 1 2 \cdot n \cdot (n+1) - \frac 1 2 \cdot i \cdot (i+1)) \end{eqnarray*}$

$\begin{eqnarray*} = \frac 1 2 \cdot (n-1) \cdot n \cdot (n+1) - \frac 1 2 \cdot \sum_{i=1}^{n-1} (i^2 + i) \end{eqnarray*}$

Letzteres ist dann noch sauber weiter zu rechnen... dein Ansatz sieht ähnlich, aber doch anders aus.

Grüße Abakus smile

07.05.2011, 18:51

OhneWitz

Auf diesen Beitrag antworten »

Vielen Dank schonmal. Ich schau mir das morgen früh genauer an. Hab für heute genug davon. smile

Schönen Abend! smile

Neue Frage »

Antworten »

Laufzeit einer Prozedur

Verwandte Themen