La complejidad del tiempo del algoritmo Sieve of Eratosthenes

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?

  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 2 ) 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) (sum 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 sum de recíprocos de primos hasta n, que es O (n log log n). (Vea aquí o aquí )

  2. El bit “encontrar el próximo número primo” es solo O (n) global, amortizado : 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).

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.

  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 

vea la explicación anterior, el ciclo interno es la sum armónica de todos los números primos hasta sqrt (n). Entonces, la complejidad real de es O (sqrt (n) * log (log (sqrt (n))))