Complexidade de tempo do algoritmo Sieve de Eratóstenes

Da Wikipedia:

A complexidade do algoritmo é a O(n(logn)(loglogn))operação de bits.

Como você chegou a isso?

O fato de a complexidade incluir o loglogntermo me diz que existe um sqrt(n)lugar.

Suponha que eu esteja executando a peneira nos primeiros 100 números ( n = 100), supondo que marcar os números como compostos leva um tempo constante (implementação de matriz), o número de vezes que usamos mark_composite()seria algo como

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

E para encontrar o próximo número primo (por exemplo, para saltar 7depois de riscar todos os números que são múltiplos de 5), o número de operações seria O(n).

Então, a complexidade seria O(n^3). Você concorda?

1. Seu n / 2 + n / 3 + n / 5 +… n / 97 não é O (n), porque o número de termos não é constante. [Edite após sua edição: O (n ² ) é um limite superior muito vago.] Um limite superior solto é n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n) (soma dos recíprocos de todos os números até n), que é O (n log n): consulte o número do Harmônico . Um limite superior mais adequado é n (1/2 + 1/3 + 1/5 + 1/7 + ...), que é a soma dos recíprocos dos primos até n, que é O (n log log n). (Vejo aqui ou aqui .)

2. O bit "encontre o próximo número primo" é apenas O (n) no geral, amortizado - você avançará para encontrar o próximo número apenas n vezes no total , não por etapa. Portanto, toda essa parte do algoritmo leva apenas O (n).

Então, usando esses dois, você obtém um limite superior de O (n log log n) + O (n) = O (n log log n) operações aritméticas. Se você contar as operações de bits, já que está lidando com números até n, elas têm cerca de log n bits, que é onde o fator de log n entra, dando O (n log n log log n) operações de bits.

O fato de a complexidade incluir o termo loglogn me diz que existe um sqrt (n) em algum lugar.

Lembre-se de que, ao encontrar um número primo Pdurante a peneiração, você não começa a riscar os números na posição atual + P; você começa a riscar os números em P^2. Todos os múltiplos de Pmenos do que P^2serão riscados pelos números primos anteriores.

1. O loop interno executa n/ietapas, onde ié primo => toda a complexidade é sum(n/i) = n * sum(1/i). De acordo com as séries harmônicas primos, sum (1/i)onde ié primo é log (log n). No total,O(n*log(log n)) ,.

2. Eu acho que o loop superior pode ser otimizado substituindo n-o sqrt(n)por complexidade de tempo geral 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;
           }
       }    
   }
   

veja a explicação acima, o loop interno é a soma harmônica de todos os números primos até sqrt (n). Portanto, a complexidade real de é O (sqrt (n) * log (log (sqrt (n))))