Nu exista diferente intre titluri.
Diferente intre continut:
Cat e complexitatea ca timp a Ciurului lui Erastotene? Motivati raspunsul.
*Update:* E interesant ca nu stim complexitatea unui algoritm pe care il invatam in clasa a 5-a. Ne gandim mai intai ca algoritmul trebuie sa fie mai rapid decat <tex>O(n^2)</tex>, pentru ca facem n pasi si fiecare pas e mai eficient decat o parcurgere a celor n numere. Daca ne uitam mai atent, numerele sunt parcurse pe sarite si numarul de operatii e <tex>n/2 + n/3 + n/4 + ... + n/n = n(1/2 + 1/3 + ... + 1/n)</tex>. Sirul <tex>1 + 1/2 + ... + 1/n - log\ n</tex> este convergent, astfel deducem ca ciurul lui eratostene are complexitatea mai mica decat <tex>O(n log n)</tex>. Nu am folosit faptul ca in algoritm noi vom marca doar pornind de la valori prime, sarind peste multe valori, astfel numarul de operatii al algoritmului e <tex>n (1/2 + 1/3 + 1/5 + ... + 1/pk)</tex> unde pk e cel mai mare numar prim mai mic decat n. Sirul <tex>1 + 1/2 + 1/3 + 1/5 + ... + 1/pk - ln\ ln\ n</tex> e convergent dupa cum putem citi 'aici':http://en.wikipedia.org/wiki/Meissel-Mertens_constant . Astfel complexitatea algoritmului _Ciurul lui Erstotene_ este <tex>O(n\ log\ log n)</tex>.
*Update:* E interesant ca nu stim complexitatea unui algoritm pe care il invatam in clasa a 5-a. Ne gandim mai intai ca algoritmul trebuie sa fie mai rapid decat <tex>O(n^2)</tex>, pentru ca facem n pasi si fiecare pas e mai eficient decat o parcurgere a celor n numere. Daca ne uitam mai atent, numerele sunt parcurse pe sarite si numarul de operatii e <tex>n/2 + n/3 + n/4 + ... + n/n = n(1/2 + 1/3 + ... + 1/n)</tex>. Sirul <tex>1 + 1/2 + ... + 1/n - log\ n</tex> este convergent, astfel deducem ca ciurul lui eratostene are complexitatea mai mica decat <tex>O(n\ log\ n)</tex>. Nu am folosit faptul ca in algoritm noi vom marca doar pornind de la valori prime, sarind peste multe valori, astfel numarul de operatii al algoritmului e <tex>n (1/2 + 1/3 + 1/5 + ... + 1/pk)</tex> unde pk e cel mai mare numar prim mai mic decat n. Sirul <tex>1 + 1/2 + 1/3 + 1/5 + ... + 1/pk - ln\ ln\ n</tex> e convergent dupa cum putem citi 'aici':http://en.wikipedia.org/wiki/Meissel-Mertens_constant . Astfel complexitatea algoritmului _Ciurul lui Erstotene_ este <tex>O(n\ log\ log\ n)</tex>.
Am o alta intrebare pentru voi: Stiti cat e complexitatea algoritmului lui Euclid?
'Comentarii':forum/index.php?topic=2265.0
Nu exista diferente intre securitate.
Diferente intre topic forum:
