Complexité temporelle de l'algorithme Sieve of Eratosthenes

Question

De Wikipedia:

La complexité de l'algorithme est O(n(logn)(loglogn)) opérations sur les bits.

Comment voulez-vous arriver à cela?

Que la complexité comprend l' loglogn terme me dit qu'il y a un sqrt(n) quelque part.

---

Supposons que je suis en cours d'exécution le tamis sur les 100 premiers numéros (n = 100), en supposant que le marquage des numéros de composite prend à temps constant (tableau de mise en œuvre), le nombre de fois que nous utilisons mark_composite() serait quelque chose comme

n/2 + n/3 + n/5 + n/7 + ... + n/97        =      O(n^2)                         

Et pour trouver le prochain nombre premier (par exemple, pour sauter 7 après le passage de tous les nombres qui sont multiples de 5), le nombre d'opérations O(n).

Ainsi, la complexité serait O(n^3). Êtes-vous d'accord?

Answer 1

1. Votre n/2 + n/3 + n/5 + ... n/97 n'est pas O(n), parce que le nombre de termes n'est pas constante. [Edit après votre edit: O(n²) est trop lâche une limite supérieure.] Un lâche de la limite supérieure est n(1+1/2+1/3+1/4+1/5+1/6+...1/n) (somme des inverses de tous les nombres jusqu'à n), O(n log n): voir Harmonique nombre. Un plus appropriée de la limite supérieure est n(1/2 + 1/3 + 1/5 + 1/7 + ...), c'est la somme des inverses des nombres premiers jusqu'à n, qui est en O(n log log n). (Voir ici ou ici.)

2. "Trouver le prochain nombre premier" est seulement O(n) dans l'ensemble, amorti - vous vous déplacer à l'avance pour trouver le nombre suivant que n fois au total, pas par pas. Donc, toute cette partie de l'algorithme prend seulement O(n).

Donc, en utilisant ces deux, vous obtenez une limite supérieure de O(n log log n) + O(n) = O(n log log n) opérations arithmétiques. Si vous comptez les opérations sur les bits, puisque vous avez à traiter avec des nombres jusqu'à la n, ils ont environ log n bits, ce qui est où le facteur de n log vient en, donnant à O(n log n log log n) opérations sur les bits.

Answer 2

Le fait que la complexité inclut le terme loglogn me dit qu'il existe un sqrt (n) quelque part.

Gardez à l'esprit que lorsque vous trouvez un nombre premier P lors du tamisage, vous ne commencez pas à rayer des nombres à votre position actuelle + P ; vous commencez à rayer des nombres à P^2 . Tous les multiples de P inférieurs à P^2 auront été rayés par des nombres premiers précédents.