Analizzare costo di un algoritmo (caso peggiore)

[Andrew Ryan]

int funzione(int V[],int n,int x){
int i=n;
while(i>0){
if(V[i-1]==x) return 1;
i=i/2;
}
return 0;
}

Ho calcolato il costo in questo modo:

$ T(n) = 3 + n/2^(n-1) $

in notazione asintotica $ O(n/2^(n-1))$

è corretto?

[apatriarca]

Come avresti calcolato questa complessità? A me sembra semplicemente \( O(\log\,n) \) nel caso peggiore.

[hamming_burst]

"apatriarca": A me sembra semplicemente \( O(\log\,n) \) nel caso peggiore.

confermo ($O(log_2(n))$ se si vuol fare i pignoli).

[Andrew Ryan]

"apatriarca":Come avresti calcolato questa complessità? A me sembra semplicemente \( O(\log\,n) \) nel caso peggiore.

mi sono basato su quanto ha detto il professore in classe , int i=n e return 0 hanno costo 1,il corpo del while ha costo $ 2*n/2^n $ perchè i si dimezza ad ogni iterazione,infine +1 che sarebbe l'ultima verifica del while,quindi $ 1+ 2*n/2^n + 1 + 1 = 3+n/2^(n-1) = O(n/2^(n-1)) $
non è corretto?

[Rggb1]

Non mi sembra. Hai calcolato $c=n/(2^n)$ come costo del ciclo in base a $n$ parametro. Proviamo
$n=10$ ciclo $c=n/(2^n)=10/(2^10)=10/1024=0.009765625$
$n=20$ ciclo $c=n/(2^n)=20/(2^20)=20/1048576=0.000019073486328125$
$n=100$ ciclo $c=~7.88*10^-29$ (tralascio la formula).

Invece, come suggerito, ad ogni iterazione si dimezza il valore di $i$ partendo da $n$... questo non ti ricorda qualcosa tipo "come convertire un numero in binario"? E qual è il costo della conversione?

[Andrew Ryan]

"Rggb":Non mi sembra. Hai calcolato $c=n/(2^n)$ come costo del ciclo in base a $n$ parametro. Proviamo
$n=10$ ciclo $c=n/(2^n)=10/(2^10)=10/1024=0.009765625$
$n=20$ ciclo $c=n/(2^n)=20/(2^20)=20/1048576=0.000019073486328125$
$n=100$ ciclo $c=~7.88*10^-29$ (tralascio la formula).

Invece, come suggerito, ad ogni iterazione si dimezza il valore di $i$ partendo da $n$... questo non ti ricorda qualcosa tipo "come convertire un numero in binario"? E qual è il costo della conversione?

scusa ma all'inizio i assume il valore di n,cosa cambia? è sempre quello il valore che poi durante il ciclo si dimezza di volta in volta

[Rggb1]

"Andrew Ryan":scusa ma all'inizio i assume il valore di n,cosa cambia?

Io non ho fatto altro che applicare la formula che hai assegnato al costo del ciclo while, per farti vedere che non può essere corretta: al crescere di $n$ il costo del ciclo tenderebbe a zero...

Ragioniamo a rovescio: al primo ciclo while, $i$ vale $n$, al secondo $n \/ 2$, al terzo $n \/ 4$, e così via fino ad 1. Il costo totale (tutti i cicli) è il numero di elementi di questa successione, che puoi ordinare a rovescio partendo da 1:
$2^0, 2^1, 2^2 ... 2^k>=n$
Ora, prova a calcolare quanto vale $k$ (che è il numero totale di cicli effettuati),

[Andrew Ryan]

"Rggb":[quote="Andrew Ryan"]scusa ma all'inizio i assume il valore di n,cosa cambia?

Io non ho fatto altro che applicare la formula che hai assegnato al costo del ciclo while, per farti vedere che non può essere corretta: al crescere di $n$ il costo del ciclo tenderebbe a zero...

Ragioniamo a rovescio: al primo ciclo while, $i$ vale $n$, al secondo $n \/ 2$, al terzo $n \/ 4$, e così via fino ad 1. Il costo totale (tutti i cicli) è il numero di elementi di questa successione, che puoi ordinare a rovescio partendo da 1:
$2^0, 2^1, 2^2 ... 2^k>=n$
Ora, prova a calcolare quanto vale $k$ (che è il numero totale di cicli effettuati),[/quote]k è $ log_2(n) $ però ho ancora un dubbio: va considerata sempre la parte intera superiore? però quando i=1 non si continuerebbe ad avere 1? quindi per esempio nel caso di n=10 il numero delle iterazioni > $log_2(n)$

EDIT: tutto risolto,mi sono confuso con il valore di $i$ e il numero di iterazioni,in effetti se n=10 alla quarta iterazione i=1 verrebbe dimezzato e non entrerebbe più nel while,quindi se vogliamo essere precisi il while avrebbe costo $ log_2(n) + 1 $ dove 1 è il costo dell'ultimo test della condizione del while,poi adottando la notazione asintotica avremo $ O(log_2(n)) $

[Andrew Ryan]

qualcuno può confermare ciò che ho detto nell'EDIT qui sopra?

[hamming_burst]

"Andrew Ryan":qualcuno può confermare ciò che ho detto nell'EDIT qui sopra?

ok è corretto.