Komplexität bestimmen

[kulturfenster]

Hallo allerseits,
Ich muss von einem Algorithmus die Komplexität bestimmmen.

Hier der Algo:

// Input: Array A of n integers
// Output: Array B of n integers
for(int i = 0; i < n-1; i++) {
   B[i] = 0;
   for(int j = 0; j < n*n; j++) {
       k = j % n; // der Pseudocode lautet: k <- j mod n; hoffe, hab das richtig verstanden...
       B[i] = A[k] + B[i];
       }
   }
return B;

meiner Ansicht ist die Komplexität n^3, da die erste Schlaufe n mal wiederholt wird und die zweite n^2 mal. Da die beiden Schlaufen verschachtelt sind, ergibt sich n^3.

richtig, falsch??

Vielen Dank für alle Tipps!

 

[SlaterB]

richtig,

Tipp: n*n nur einmal berechnen und in einer Variablen speichern,
nicht n^3x allein diese Zahl ständig neu berechnen

wenn du die j Schleife nach außen setzt würde auch das k nur n^2 berechnet werden statt n^3 mal

 

[kulturfenster]

der Algo ist nicht von mir, aber danke für die Tipps!