Intrebare scurta

Cosmin Negruseri
04 noiembrie 2007

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 $O(n^2)$ , 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 $n/2 + n/3 + n/4 + ... + n/n = n(1/2 + 1/3 + ... + 1/n)$ . Sirul $1 + 1/2 + ... + 1/n - log\ n$ este convergent, astfel deducem ca ciurul lui eratostene are complexitatea mai mica decat $O(n\ log\ n)$ . 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 $n (1/2 + 1/3 + 1/5 + ... + 1/pk)$ unde pk e cel mai mare numar prim mai mic decat n. Sirul $1 + 1/2 + 1/3 + 1/5 + ... + 1/pk - ln\ ln\ n$ e convergent dupa cum putem citi aici . Astfel complexitatea algoritmului Ciurul lui Erstotene este $O(n\ log\ log\ n)$ .