Aiuto - complessità computazionale

[cydmm]

Ciao ragazzi,

sono in crisi nera perchè non riesco a trovare la complessità computazionale del seguente algoritmo

i=n
while i>=1 do
x=x+1, i=i/2

Potete aiutarmi?

Grazie infinite

[apatriarca]

Ad ogni iterazione del ciclo il contatore viene dimezzato. Per cui i assume valori n, n/2, (n/2)/2, ... 1, 0. La complessità è quindi $log_2(n)$. Cosa non ti è chiaro esattamente?

[cydmm]

"apatriarca":Ad ogni iterazione del ciclo il contatore viene dimezzato. Per cui i assume valori n, n/2, (n/2)/2, ... 1, 0. La complessità è quindi $log_2(n)$. Cosa non ti è chiaro esattamente?

Non mi ci trovo con la soluzione.....

se così fosse... metti n=2 quando n è uguale a 2 il ciclo e quindi x=x+1 si svolge due volte
quindi il logaritmo in base 2 di n dovrebbe restiuirmi 2,ovvero il numero delle volte che entra nel ciclo e svolge l'operazione

[cydmm]

"cydmm":[quote="apatriarca"]Ad ogni iterazione del ciclo il contatore viene dimezzato. Per cui i assume valori n, n/2, (n/2)/2, ... 1, 0. La complessità è quindi $log_2(n)$. Cosa non ti è chiaro esattamente?

Non mi ci trovo con la soluzione.....

se così fosse... metti n=2 quando n è uguale a 2 il ciclo e quindi x=x+1 si svolge due volte
quindi il logaritmo in base 2 di n dovrebbe restiuirmi 2,ovvero il numero delle volte che entra nel ciclo e svolge l'operazione


[/quote]

Mi spiego meglio

quello che vorrei farti capire è che la soluzione che tu hai trovato...ad esempio logaritmo in base due di n... deve essere uguale al numero delle volte che viene effettuato x=x+1 in relazione a quell' n. Cioè se n= 4 l'operazione viene effettuata 3 volte...quindi il log in base 2 di 4 dovrebbe essere 3.

[Deckard1]

"cydmm":quello che vorrei farti capire è che la soluzione che tu hai trovato...ad esempio logaritmo in base due di n... deve essere uguale al numero delle volte che viene effettuato x=x+1 in relazione a quell' n. Cioè se n= 4 l'operazione viene effettuata 3 volte...quindi il log in base 2 di 4 dovrebbe essere 3.

Innanzitutto la complessità di un algoritmo è una stima asintotica, ovvero si valuta per n che tende all'infinito. Inoltre apatriarca intendeva naturalmente che il tempo di calcolo di questo algoritmo è $ ϑ(log n) $.

[apatriarca]

Come già spiegato da Deckard non intendevo l'esatto numero di iterazione del ciclo, ma la sua complessità asintotica. Volendo comunque calcolare l'esatto numero di iterazioni conviene interpretare la divisione intera per due come uno shift a destra di un bit (suppongo n > 0). Il ciclo termina quindi quando n è stato shiftato un numero di volte uguale ad 1 più il numero di cifre binarie di n. Cioè [tex]\lfloor \log_2 n \rfloor + 1[/tex]