Complessità di un algoritmo

[MaxDembo81]

Come si fa a calcolare la complessità di un semplice algoritmo tipo questo?

#include <stdio.h>
#include <math.h>
#include <qfloat.h>

qfloat f(int n){
if (n == 1 ) return 1;
else return 2 / (2+f(n-1));
}
void main(){
printf("Continued Fraction (f(n)=1+2/2+f(n-1)\n\n");
qfloat a, tre, radice3;
int b;
radice3=sqrtq(3);
a=1;
b=1;
while(a != radice3){
a=1+f(b);
printf("%d) %104.1qf %qe\n",b,a, a-radice3);
b++;
}
}

Mi so un po' perso fra O grandi e Tn

[dedalo89]

Provo a rispondere io al tuo quesito (anche se è da un paio d'anni che non affronto più le complessità):

Suppongo tu sappia cosa sia un'equazione alle ricorrenze, quindi vediamo un attimo come interpretare la complessità della funzione qFloat().
Questa funzione ricorre su se stessa, quando il parametro passato è diverso da 1; in questo caso viene richiamata qFloat() decrementando di uno il valore passato.
Senza formulare una T(n) e svilupparla mediante unfolding, puoi già dire che sicuramente la tua qFloat è O(n), in quanto la funzione verrà richiamata un numero di volte (chiamate che effettuano operazioni elementari) pari al parametro che passi alla funzione meno 1, quindi O(n).

La notazione O-grande indica un limite superiore "lasco", ossia il tuo algoritmo non si comporterà mai peggio della classe di complessità a cui appartiene.

Se ci sono altre domande, chiedi pure!

[banryu79]

@MaxDembo81: se poi la questione ti dovesse interessare molto, qui c'è un corso online fatto di videoletture (della Stanford, in inglese) Design and Analysis of Algorithms