[Algoritmi] Semplice complessità di un ciclo for

[Blitzcrank97]

Ho un ciclo for così strutturato:

Codice:

int a = 0;
for(int i = 0; i < f(x)*f(x); i++)
   a++;

Ora, sapendo che la funzione f(x) ha come complessità O(n^2) mentre restituisce un risultato O(n^3) vorrei sapere la complessità totale del ciclo.

Io ho fatto n^3 * n^3 il numero totale in cui viene eseguito il for moltiplicato per la complessità del suo corpo che è O(1)
Mi verrebbe quindi O(n^6) ma il risultato è O(n^8)

Probabilmente deve essere presa in considerazione anche il tempo di esecuzione di f(x)? Come funziona?

[apatriarca]

La funzione \(f(x)\) viene calcolata due volte ad ogni iterazione. Quindi il risultato è \(O(n^6\,(2\,n^2 + 1)) = O(n^8)\).

[Blitzcrank97]

Ok grazie volevo sapere proprio questo risolto

[Blitzcrank97]

Ora mi è venuto un dubbio, ma se io avessi fatto così:

Codice:

int a = 0;
int s = f(x)*f(x);
for (int i = 0; i < s ; i++)
 a++;


Avrei ridotto la complessità?

[Blitzcrank97]

Metto anche un altro caso che non riesco a capire:
funzione g:

Codice:

if(x<=0) return 1;
int a=0; int b=0;
for(int i = 0; i <= x; i++) a += i;
for(int j = a; j >= 0; j--) b += j;
return b/a + g(x - 1);

Allora per la complessità della funzione mi torna, "a" diventa di complessità n^2 perché è la somma dei primi n numeri, verrebbe quindi così:
T(0) = O(1)
T(n) = bn^2 + T(n - 1) che fa O(n^3)

Poi però mi serve la complessità del risultato restituito dalla funzione che non capisco, anche "b" è n^2, anche lui è somma dei primi n numeri, se faccio b/a non verrebbe 1?
Quindi dovrebbe essere
R(n) = n^2/n^2 + R(n - 1) e venire O(n)!
Ma invece sembra che b/a sia comunque n^2 e la soluzione è
O(n^3), perché?

[apatriarca]

Ora mi è venuto un dubbio, ma se io avessi fatto così:

Codice:

int a = 0;
int s = f(x)*f(x);
for (int i = 0; i < s ; i++)
 a++;


Avrei ridotto la complessità?

Sì, la complessità sarebbe stata ridotta perché la funzione è chiamata al di fuori del ciclo. In effetti, visto il costo della funzione avresti anche semplicemente potuto richiamarla una singola volta e calcolare il limite del ciclo separatamente. Inoltre è evidente che il codice sta semplicemente calcolando:

Codice:

int s = f(x);
a = s*s;


[apatriarca]

Metto anche un altro caso che non riesco a capire:
funzione g:

Codice:

if(x<=0) return 1;
int a=0; int b=0;
for(int i = 0; i <= x; i++) a += i;
for(int j = a; j >= 0; j--) b += j;
return b/a + g(x - 1);

Allora per la complessità della funzione mi torna, "a" diventa di complessità n^2 perché è la somma dei primi n numeri, verrebbe quindi così:
T(0) = O(1)
T(n) = bn^2 + T(n - 1) che fa O(n^3)

Poi però mi serve la complessità del risultato restituito dalla funzione che non capisco, anche "b" è n^2, anche lui è somma dei primi n numeri, se faccio b/a non verrebbe 1?
Quindi dovrebbe essere
R(n) = n^2/n^2 + R(n - 1) e venire O(n)!
Ma invece sembra che b/a sia comunque n^2 e la soluzione è
O(n^3), perché?

Il primo ciclo viene eseguito \(x+1\) volte e il risultato sarà \(a = \sum_{i=0}^x i = (x^2 + x)/2\). Il secondo ciclo verrà eseguito \(a\) volte e \(b\) sarà quindi uguale a \(b = \sum_{j=0}^a j = (a^2 + a)/2 \). Se quindi calcoli \(b/a\) non ottieni \(1\) ma qualcosa che sarà proporzionale ad \(a\). Quindi anche il risultato sarà \(O(n^3)\).

[Blitzcrank97]

Ok grazie mille, quindi b è di ordine O(n^4) in poche parole?

[apatriarca]

Esatto.