0 Daumen
418 Aufrufe

Gegeben sei der folgende Pseudocode

m=1;
for i=1 to n
        for j=1 to n
               for k=1 to i*j
                  m=m+2^i;
               end;
       end;
end;

Berechnen Sie den Aufwand unter der Annahme, dass Additionen und Multiplikationen jeweils eine Zeit Einheit benötigen. (Fur den Ausdruck 2^i werden somit i-1 Zeiteinheiten.)

In dieser Aufgabe soll ich die Anzahl der nötigen Rechenoperationen (FLOPs) und den Aufwand in O-Notation bestimmen.

Problem ist, dass ich den Pseudocode nicht richtig verstehe, was genau der Sinn dahinter ist, also was rechnet der Code überhaupt aus. Zudem weiß ich nicht genau, wie ich von diesem Code die nötigen Rechenoperationen feststellen kann, aber alleine durch die 3 for-Schleifen kann wahrscheinlich schon grob deuten, dass wenigstens ein Aufwand von O(n^3) nötig sein wird.

Avatar von

1 Antwort

0 Daumen

Hallo:-)

Für den benötigten Aufwand hast du hier eine dreifach verschachtelte Summierung der Form:

$$ \sum\limits_{i=1}^n\left(\sum\limits_{j=1}^n\left(\sum\limits_{k=1}^{i\cdot j} (\underbrace{1}_{\text{Zeiteinheit Addition}}+\underbrace{(i-1)}_{\text{Zeiteinheit für }2^i})\right)\right)\\[20pt]=\sum\limits_{i=1}^n\left(\sum\limits_{j=1}^n\left(\sum\limits_{k=1}^{i\cdot j}  i \right)\right)=\left(\sum\limits_{i=1}^n i \right)\cdot \left(\sum\limits_{j=1}^n\left(\sum\limits_{k=1}^{i\cdot j} 1  \right)\right)=\left (\sum\limits_{i=1}^n i \right) \cdot \left(\sum\limits_{j=1}^n i\cdot j\right)=\left(\sum\limits_{i=1}^n i^2\right)\cdot \left(\sum\limits_{j=1}^n j\right)\\[20pt]=\left(\sum\limits_{i=1}^n i^2\right)\cdot n=\left[\frac{1}{6}\cdot n\cdot (n+1)\cdot (2n+1)\right]\cdot n=\frac{1}{6}\cdot n^2\cdot (n+1)\cdot (2n+1)\\[10pt]\stackrel{n\geq 0}{\leq }\frac{1}{6}\cdot n^2\cdot (2n+1)\cdot (2n+1)=\frac{1}{6}\cdot n^2\cdot (4n^2+4n+1)\\[10pt]\stackrel{n\geq 1}{\leq } \frac{1}{6}\cdot n^2\cdot (4n^2+4n^2+n^2)=\frac{1}{6}\cdot n^2\cdot 9\cdot n^2=\frac{3}{2}\cdot n^4\in \mathcal{O}(n^4)$$

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community