Imi poate explica cineva va rog cum se calculeaza complexitatea unui program?
Am de exemplu o problema: sa se testeze daca un numar este prim a carei rezolvare ar trebui sa aiba complexitate timp O(√n)…cum pot verifica asta?
ElenaIuliauser (0)
Nu inteleg ce ceri? programu` care calculeaza primalitatea sau calculul complexitatii?
k=0;
for(i=2;i*i<=n;i++)
if(n%i==0)
k=1;
if(!k)
printf(„n=prim”);
else
printf(„n=neprim”);
Complexitatea se face cam asha.
Ne uitam dupa for. Observam ca se opreste cand i*i>n deci cand i>sqrt(n).
Atunci complexitatea e data de sqrt(n) deoarece i se incrementeaza cu 1 iar sqrt(n) reprezinta un fel de margine superioara. Sper ca te-am lamurit.
Ok..merci mult, era vorba de complexitate.. oricum am inteles, multumesc!