PDA

View Full Version : [Java] aiuto complessità

Pete9
08-07-2010, 17:04
debbo calcolare la complessità asintotica nel caso peggiore del seguente metodo,potreste aiutarmi?

public static int esercizio(int n){
int c=0;
int a=n;
while(a>0){
int b=a;
while(b>0){
c+=b;
b--;
}
a=a/2;
}
return c;
}

Può essere O(log(n)^2)?
Rsk
08-07-2010, 17:16
debbo calcolare la complessità asintotica nel caso peggiore del seguente metodo,potreste aiutarmi?

public static int esercizio(int n){
int c=0;
int a=n;
while(a>0)
{
int b=a;
while(b>0)
{
c+=b;
b--;
}
a=a/2;
}
return c;
}

Può essere O(log(n)^2)?

Il ciclo interno viene eseguito n volte, quello più esterno n/2 volte
Pete9
08-07-2010, 17:18
Il ciclo esterno non viene eseguito log(n) volte?
clockover
08-07-2010, 17:36
Il ciclo esterno non viene eseguito log(n) volte?

anche a me sembra così
nuovoUtente86
08-07-2010, 17:38
Il ciclo esterno non viene eseguito log(n) volte?

si è sub-lineare
Pete9
08-07-2010, 17:45
cioè? con la notazione O grande come sarebbe??
Rsk
08-07-2010, 17:49
Errore mio.
Si è sublineare
Pete9
08-07-2010, 17:57
Cosa intendete per sub lineare? Me lo potreste spiegare?
nuovoUtente86
08-07-2010, 18:15
Cosa intendete per sub lineare? Me lo potreste spiegare?
sub vuol dire inferiore. Nel tuo caso la complessità del ciclo esterno è approssimativamente log(n) per difetto.
Pete9
08-07-2010, 19:23
ok, fin lì ci sono. Ma il secondo while quante volte viene eseguito? La risposta all'esercizio qual è?
wingman87
08-07-2010, 19:53
Il while interno viene eseguito la prima volta n volte, la seconda n/2, la terza n/4 e così via. In totale quasi 2n volte. Quindi la complessità secondo me è lineare: O(n)
nuovoUtente86
08-07-2010, 20:16
la complessità totale è nlog(n)
Pete9
08-07-2010, 22:59
Perchè nlog(n)?
wingman87
09-07-2010, 00:27
Applicando il Master Theorem (http://en.wikipedia.org/wiki/Master_theorem):
l'equazione di ricorrenza della tua funzione è:
T(n)=T(n/2)+n
dove T(n/2) rappresenta la reiterazione del ciclo più esterno, mentre n rappresenta il numero di esecuzioni del ciclo interno

In questa equazione abbiamo
a=1
b=2
f(n)=n

Siamo nel caso 3, infatti
f(n)=n=Ω(n^(0+ε)) per ε=1
e
f(n/2)<cf(n) per c>1/2

Quindi T(n)=Θ(f(n))
tuccio`
09-07-2010, 02:51
teorema master per una funzione non ricorsiva?

come diceva wingman:

n + n/2 + n/4 + ... = n * (serie geometrica di ragione 1/2) -> 2n

quindi è O(n)