eratosthenes - sieve algorithm

La complejidad del tiempo del algoritmo Sieve of Eratosthenes

Question

De la Wikipedia:

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

¿Cómo llegas a eso?

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

Supongamos que estoy ejecutando el tamiz en los primeros 100 números ( n = 100 ), suponiendo que marcar los números como compuesto toma tiempo constante (implementación de matriz), el número de veces que usemos mark_composite() sería algo así como

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

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

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

Answer 1

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

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

Answer 2

1. El ciclo interno realiza n/i pasos, donde i es primo => toda la complejidad es sum(n/i) = n * sum(1/i) . De acuerdo con la serie de armónicos primos, la sum (1/i) donde i es primo es log (log n) . En total, O(n*log(log n)) .

2. Creo que el ciclo superior se puede optimizar reemplazando n con sqrt(n) por lo que la complejidad general del tiempo será 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 3

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 reciprocos de todos los números hasta n), que es O (n log n): ver el número armónico . 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). (Vea here o here )

2. El bit "encontrar el próximo número primo" es solo O (n) global, amortized : avanzará para encontrar el siguiente número solo n veces en total , no por paso. Entonces, esta parte del algoritmo solo toma O (n).

Entonces, usando estos dos obtienes 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).