Complejidad temporal del algoritmo Sieve of Eratosthenes

95

De Wikipedia:

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

¿Cómo llegas a eso?

Que la complejidad incluya el loglogntérmino me dice que hay un sqrt(n)lugar.


Supongamos que estoy ejecutando el tamiz en los primeros 100 números ( n = 100), suponiendo que marcar los números como compuestos toma un tiempo constante (implementación de matriz), la cantidad de veces que usamos 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 7despué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?

Lazer
fuente
5
No sé sobre el resto (demasiado matemático para mi cerebro demasiado adormecido en este momento), pero la raíz cuadrada se debe al hecho de que si un número no tiene divisores menos que su raíz cuadrada, es primo. Además, acabo de aprender que loglog (n) significa que hay una raíz cuadrada. Agradable.
R. Martinho Fernandes
13
¿Cómo significa que el loglog (n) está allí significa que hay un sqrt (n) en alguna parte? (@Martinho: ¿Por qué dices que "acabas de aprender esto"?) ¡El análisis real no involucra raíces cuadradas!
ShreevatsaR

Respuestas:

117
  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 suelto.] Un límite superior suelto es n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n) (suma de los recíprocos de todos los números hasta n), que es O (n log n): consulte Número armónico . Un límite superior más adecuado es n (1/2 + 1/3 + 1/5 + 1/7 +…), que es la suma de los recíprocos de los números primos hasta n, que es O (n log log n). (Vea aquí o aquí ).

  2. El bit "encontrar el siguiente número primo" es solo O (n) en total, amortizado ; avanzará para encontrar el siguiente número solo n veces en total , no por paso. Entonces, toda esta parte del algoritmo toma solo O (n).

Entonces, usando estos dos, obtienes un límite superior de operaciones aritméticas O (n log log n) + O (n) = O (n log log n). 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, lo que da O (n log n log log n) operaciones de bits.

ShreevatsaR
fuente
Para una parte del problema, está considerando la complejidad asintótica. Por otra parte, está considerando la competencia amortizada. Estoy confundido.
crisron
2
@crisron ¿Cuál es el problema? No es el caso de que la "complejidad asintótica" y la "complejidad amortizada" sean dos tipos diferentes de la misma cosa. La amortización es solo una técnica para contar algo con más cuidado, que puede ser la complejidad asintótica.
ShreevatsaR
Todo esto mientras solía pensar en ellos como diferentes. Gracias por aclararlo.
crisron
1
@ShreevatsaR ¿Por qué calculamos la suma de series armónicas hasta n términos? ¿No deberíamos calcular solo hasta los términos sqrt (n)? ¿Dar la respuesta como theta de n (loglogsqrt (n)) operaciones aritméticas? Además, wikipedia dice que la complejidad del espacio es O (n). ¿No debería ser theta de n porque necesitamos una matriz de n elementos en cualquier caso?
a_123
@ s_123 Sí, puede calcular solo hasta √n términos, pero no hace una diferencia en el análisis asintótico (o incluso una diferencia práctica significativa en el tiempo de ejecución), porque log (√x) = (1/2) log x para cualquier x. Entonces Θ (n log log √n) = Θ (n log log n). Para su otra pregunta, sí, la complejidad del espacio es Θ (n), que también es O (n): es convencional usar O () para indicar que está especificando el límite superior, en lugar de decir Θ () para indicar que también es el límite inferior (especialmente cuando el límite inferior es obvio, como lo es aquí).
ShreevatsaR
7

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

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

jemfinch
fuente
10
esta declaración es verdadera en sí misma, pero no tiene relación con la declaración citada que en sí misma no tiene mérito. Ya sea que partamos de po p^2, la complejidad es la misma (con matrices de acceso directo). SUM (1/p) {p<N} ~ log (log N)es la razón.
Will Ness
6
  1. El bucle interno hace n/ipasos, donde ies primo => toda la complejidad es sum(n/i) = n * sum(1/i). Según la serie de armónicos primos, sum (1/i)donde ies primo es log (log n). En total O(n*log(log n)),.
  2. Creo que el bucle superior se puede optimizar reemplazando ncon sqrt(n)la complejidad del tiempo total 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;
            }
        }    
    }
    
Anand Tripathi
fuente
2
no, reemplazar n con sqrt (n) lo convierte en ~ n log log (sqrt n) que sigue siendo ~ n log log n. y isprimees absolutamente el nombre incorrecto para usar allí.
Will Ness
-1

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

Bharath Kumar Reddy Appareddy
fuente
2
incorrecto. marcamos todo el camino hasta N: N / 2 + N / 3 + N / 5 + N / 7 + N / 11 + ... = N (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) ~ N log log (sqrt N) ~ N log log N.
Will Ness