Tempo complessità del Crivello di Eratostene algoritmo

Question

Da Wikipedia:

La complessità dell'algoritmo è O(n(logn)(loglogn)) operazioni bit.

Come si arriva a questo?

Che la complessità includa il termine loglogn mi dice che c'è un sqrt(n) da qualche parte.

---

Supponiamo sto facendo funzionare il setaccio sui primi 100 numeri (n = 100), supponendo che la marcatura i numeri come composito richiede tempo costante (attuazione array), il numero di volte che utilizziamo mark_composite() sarebbe qualcosa come

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

E per trovare il numero primo successivo (per esempio per passare alla 7 dopo aver attraversato tutti i numeri che sono multipli di 5), il numero di operazioni sarebbe O(n).

Quindi, la complessità sarebbe O(n^3). Sei d'accordo?

Answer 1

1. tuo n/2 + n/3 + n/5 + ... n/97 non è O (n), perché il numero di termini non è costante. [Modifica dopo la modifica: O (n) è troppo largo un limite superiore.] Un limite superiore allentato è n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + ... 1/n) (somma dei reciproci di tutti i numeri fino a n), che è O (n log n): vedere Harmonic number. Un upper-bound più corretto è n (1/2 + 1/3 + 1/5 + 1/7 + ...), che è la somma di reciproci di primi fino a n, che è O (n log log n). (Vedere here o here.)

2. Il "trovare il numero primo successivo" bit è O (n) nel complesso, amortized - si andare avanti per trovare il numero successivo solo n volte in totale, non per passo. Quindi questa intera parte dell'algoritmo richiede solo O (n).

Quindi, utilizzando questi due si ottiene un limite superiore di O (n log log n) + O (n) = O (n log log n) operazioni aritmetiche. Se si contano le operazioni di bit, dal momento che si ha a che fare con numeri fino a n, hanno circa n bit di registro, che è il punto in cui entra in gioco il fattore n, fornendo operazioni di bit O (n log n log log n).

Answer 2

Che la complessità includa il termine loglogn mi dice che c'è un sqrt (n) da qualche parte.

Tenete a mente che quando si trova un numero primo P mentre setacciatura, non si inizia attraversando fuori i numeri a vostra posizione corrente + P; in realtà inizi a passare i numeri allo P^2. Tutti i multipli di P inferiori a P^2 saranno stati cancellati dai numeri primi precedenti.

Answer 3

1. Il ciclo interno fa n/i passi, dove è primo i => l'intero complessità è sum(n/i) = n * sum(1/i). Secondo la serie di prime armoniche, lo sum (1/i) dove i è primo è log (log n). Nel totale , O(n*log(log n)).

2. penso che il ciclo superiore può essere ottimizzato sostituendo n con sqrt(n) complessità quindi nel complesso il tempo sarà 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; 
        } 
       }  
   }