complexité temporelle de Sieve de l'algorithme Eratosthène

Question

De Wikipedia:

  

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

Comment arrivez-vous à cela?

Que la complexité inclut le terme de loglogn me dit qu'il ya un sqrt(n) quelque part.

---

Supposons que je courais le tamis sur les 100 premiers chiffres (n = 100), en supposant que le marquage des nombres comme composite prend du temps constant (mise en œuvre du tableau), 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 passer à 7 après avoir traversé tous les chiffres qui sont des multiples de 5), serait O(n) le nombre d'opérations.

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

Answer 1

1. Votre n / 2 + n / 3 + n / 5 + ... n / 97 ne représente pas O (n), car le nombre de termes ne sont pas constantes. [Modifier après avoir modifié:. O (n ² ) est lâche aussi une limite supérieure] Une limite supérieure lâche est n (1 + 1/2 + 1/3 + 1/4 + 1 / 5 + 1/6 + ... 1 / n) (somme des inverses des tous nombre jusqu'à n), qui est O (n log n): voir numéro harmonique . Une plus appropriée est n limite supérieure (1/2 + 1/3 + 1/5 + 7/1 + ...), qui est la somme des inverses des nombres premiers jusqu'à n, qui est O (n log log n). (Voir ou ici .)

2. "trouver le prochain nombre premier" bit est seulement O (n) Dans l'ensemble, amorti - vous aller de l'avant pour trouver le numéro suivant que n fois, et non par étape totale . Donc, toute cette partie de l'algorithme ne prend que 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 de bits, puisque vous traitez avec des chiffres jusqu'à n, ils ont environ n bits log, ce qui est l'endroit où le facteur de log n arrive, donnant O (n log n log log n) opérations de bits.

Answer 2

  

Que la complexité inclut le terme loglogn me dit qu'il ya un sqrt (n) quelque part.

Gardez à l'esprit que lorsque vous trouvez un nombre premier P en tamisant, vous ne commencez pas barrant les numéros à votre position actuelle + P; vous commencez réellement barrant les numéros à P^2. Tous les multiples de P moins de P^2 auront été biffé par des nombres premiers précédents.

Answer 3

1. La boucle intérieure ne n/i étapes, où i est premier => l'ensemble la complexité est sum(n/i) = n * sum(1/i). Selon harmonique premier série, le sum (1/i) où i est premier est log (log n). Dans au total, O(n*log(log n)).

2. Je pense que la boucle supérieure peut être optimisée par le remplacement n avec sqrt(n) si la complexité globale de temps va O(sqrt(n)loglog(n)):

   void isprime(int n)
   {
       int prime[n],i,j,count1=0;
       for(i=0;i<n;i++)
       {
          prime[i]=1;
       }
       prime[0]=prime[1]=0;
       for(i=2;i<=n;i++)
       {
           if(prime[i]==1)
           {
               printf("%d ",i);
               for(j=2;(i*j)<=n;j++)
                   prime[i*j]=0;
           }
       }    
   }
   

Answer 4

voir prendre l'explication ci-dessus la boucle interne est la somme harmonique de tous les nombres premiers jusqu'à sqrt (n). Ainsi, la complexité réelle de O (sqrt (n) * log (log (sqrt (n))))