Nötige Rechenoperationen und Aufwand in O-Notation aus Pseudocode berechnen

Question

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.

Answer 1

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)$$