# Komplexität bestimmen



## kulturfenster (12. Jun 2007)

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 (12. Jun 2007)

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 (12. Jun 2007)

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


----------

