infoarena

Comentarii la postul http://infoarena.ro/blog/intrebare-scurta

Raspuns: O(N) cu o constanta.

CATEVA NOTIUNI:

Consideram nr de operatii de marcare a multiplilor pt fiecare numar de la 1 la N

cntMark = {O(1) daca i nu este prim
              O(N/i) daca nr este prim

Suma cu i de la 1 la N de  cntMark =  (O(1) * N - pt fiecare nr se fac cel putin un nr constant de op
                                                       +
                                                 O(N/2) + (N/3) + (N/5)...- marcajele pt nr prime
Stim ca
1) N/1 + N/2 + N/3 +..N/i+...N/N ~= O(NlogN) (aprox. grosolana) E simplu de arat, rotunjind fiecare nr i spre cea mai mare putere de 2 mai mica ca i
   N/1 + N/2 + N/3 +..N/N <= N/1 + N/2 + N/2 + N/4 +... N/[2^x] = O(NlogN),  x= max{ y/ 2^y <= N}
 

2) se stie ca in primele N nr naturale exista N / lnN nr prime

REZOLVARE:

O(N/1) + O(N/2) + O(N/3) + ... O(N/N) - cu limita O(NlogN)
O(N/2) + O(N/3) + O(N/5) + .... - subsir de termeni al prime sume, cu  nr de elemente = N / lnN, exista lnN astfel de subsiruri, fiecare avand limita O(NlogN)  / lnN ~= O(N) cu o constanta

Complexiate Ciur eratostene = O(N) * logN/lnN ~= O(N)


P.S. La 1) limita adevarata e mai mica de NlogN,e chiar NlnN

Nah nu e bine.

 O demonstratie poate fi legata de numerele Fibonacci ... plecand de la faptul ca daca am face cmmdc(F[n+1],F[n+2]) am face prin scaderi succesive maxim "n" operatii . Asta este echivalent cu a calcula pe cel de al n-lea termen al lui fibonacci ... si putem sa ajungem astfel la scrierea celui de-al "n"-lea termen cu ajutorul numarului de aur . Bine intales ... complexitatea este cam "larga" pentru ca eu fac scaderi in loc de impartiri ... se poate ajunge pana la log(n) ... unde "n" este cel mai mare numar dintre cele care se calculeaza cmmdc.

legat de post-ul anterior... daca aplici cmmdc ala cu impartiri in loc de scaderi ajungi exact in acelasi loc, deoarece F[n+2] mod F[n+1]=F[n]. Deci intr-adevar, complexitatea devine O(log n) (pentru demonstratie completa, exista un subcapitol in Cormen, chiar si un capitol intreg in Knuth vol 2 - daca e voie sa fac reclama la piraterie... le am in format pdf cui ii trebe)

   Scuze .. ai dreptate ... :) uhm cat de usor poti sa faci o gafa cand nu esti atent la calcule ....

Daca nu ma insel complexitatea  algoritmului lui euclid este de O( log a * log b ) ? pentru a demonstra cred ca sa folosit teorema impartiri cu rest:
a:b = c, r;
a=b*c+r; r= a-b*c;  r= a- b* [a/b]; r= a - b* ( a/b - {a/b} ) ; r= b*{a/b};
unde

• = parte intreaga de x si {y} parte fractionara din x

Nu e log a * log b ci log max(a, b).