[Java] aiuto complessità

[Pete9]

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]

Originariamente inviato da Pete9

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]

Il ciclo esterno non viene eseguito log(n) volte?

[clockover]

Originariamente inviato da Pete9

Il ciclo esterno non viene eseguito log(n) volte?

anche a me sembra così

[nuovoUtente86]

Originariamente inviato da Pete9

Il ciclo esterno non viene eseguito log(n) volte?

si è sub-lineare

[Pete9]

cioè? con la notazione O grande come sarebbe??

[Rsk]

Errore mio.
Si è sublineare

[Pete9]

Cosa intendete per sub lineare? Me lo potreste spiegare?

[nuovoUtente86]

Originariamente inviato da Pete9

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]

ok, fin lì ci sono. Ma il secondo while quante volte viene eseguito? La risposta all'esercizio qual è?

[wingman87]

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]

la complessità totale è nlog(n)

[Pete9]

Perchè nlog(n)?

[wingman87]

Applicando il 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`]

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)