Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Intrebare scurta  (Citit de 3057 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« : Noiembrie 04, 2007, 17:40:45 »

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


Karma: -6
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #1 : Noiembrie 04, 2007, 23:30:07 »

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

Memorat

RSS
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : Noiembrie 05, 2007, 00:29:38 »

Nah nu e bine.
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #3 : Noiembrie 05, 2007, 11:25:55 »

 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.
« Ultima modificare: Noiembrie 07, 2007, 11:18:08 de către nash mit » Memorat
thecata
Strain


Karma: 15
Deconectat Deconectat

Mesaje: 9



Vezi Profilul
« Răspunde #4 : Noiembrie 05, 2007, 11:52:08 »

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)
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #5 : Noiembrie 05, 2007, 12:08:42 »

   Scuze .. ai dreptate ... Smile uhm cat de usor poti sa faci o gafa cand nu esti atent la calcule ....
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #6 : August 07, 2009, 08:09:37 »

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
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #7 : August 10, 2009, 02:29:44 »

Nu e log a * log b ci log max(a, b).
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines