complejidad Tiempo de Criba de Eratóstenes algoritmo

Question

De Wikipedia:

La complejidad del algoritmo es O(n(logn)(loglogn)) operaciones de bits.

¿Cómo se llega a eso?

Que la complejidad incluye el término loglogn me dice que hay un sqrt(n) en alguna parte.

---

Supongamos que estoy corriendo el tamiz en los primeros 100 números (n = 100), suponiendo que el marcado de los números de material compuesto lleva tiempo constante (aplicación array), el número de veces que utilizamos mark_composite() sería algo así como

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

Y para encontrar el siguiente número primo (por ejemplo, para saltar a 7 después de cruzar todos los números que son múltiplos de 5), el número de operaciones sería O(n).

Por lo tanto, la complejidad sería O(n^3). ¿Estás de acuerdo?

Answer 1

1. Su n/2 + n/3 + n/5 + ... n/97 no es O (n), porque el número de términos no es constante. [Editar después de su edición: O (n) es un límite superior demasiado flojo.] Un límite superior suelto es n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + ... 1/n) (suma de recíprocos de todos números hasta n), que es O (n log n): ver Harmonic number. Un límite superior más apropiado es n (1/2 + 1/3 + 1/5 + 1/7 + ...), que es suma de recíprocos de primos hasta n, que es O (n log log n). (Ver here o here.)

2. El "encontrar el siguiente número primo" bit sólo O (n) en general, amortized - pasará por delante para encontrar el siguiente número solamente n veces en total de, no por paso. Entonces, esta parte del algoritmo solo toma O (n).

lo tanto, utilizando estos dos se obtiene un límite superior de O (n log log n) + O (n) = O (n log log n) operaciones aritméticas. Si cuenta operaciones de bits, dado que está tratando con números hasta n, tienen aproximadamente log n bits, que es donde entra el factor de log n, dando operaciones de bit O (n log n log log n).

Answer 2

Que la complejidad incluye el término loglogn me dice que hay un sqrt (n) en alguna parte.

Tenga en cuenta que cuando se encuentra un número primo P mientras tamizado, no se empieza tachando los números en su posición actual + P; en realidad comienzas a tachar los números al P^2. Todos los múltiplos de P menos de P^2 habrán sido tachados por números primos anteriores.

Answer 3

1. El bucle interno hace n/i pasos, donde i es primo => toda la complejidad es sum(n/i) = n * sum(1/i). De acuerdo con la serie armónica principal , la sum (1/i) donde i es la principal es log (log n). En total, O(n*log(log n)).

2. creo que el bucle superior se puede optimizar mediante la sustitución de n con sqrt(n) complejidad por lo general el tiempo se 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; 
        } 
       }  
   }