Complexidade temporal do algoritmo Sieve of Eratosthenes

Da Wikipedia:

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

Como você chega a isso?

Que a complexidade inclui o termo loglogn me diz que existe um sqrt(n) algum lugar.


Suponha que eu esteja executando a peneira nos primeiros 100 números ( n = 100 ), assumindo que marcar os números como compostos tomam tempo constante (implementação da 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 para 7 depois de cruzar 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. [Editar após a sua edição: O (n 2 ) está muito solto no limite superior.] Um limite superior solto é n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n) (sum de recíprocos de todos os números até n), que é O (n log n): veja o número Harmônico . Um limite superior mais adequado é n (1/2 + 1/3 + 1/5 + 1/7 +…), isto é sum de recíprocos de primos até n, que é O (n log log n). (Veja aqui ou aqui .)

  2. O bit “localizar o próximo número primo” é somente O (n) no geral, amortizado – você avançará para encontrar o próximo número apenas n vezes no total , não por etapa. Então toda essa parte do algoritmo leva apenas O (n).

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

Que a complexidade inclui o termo loglogn me diz que existe um sqrt (n) em algum lugar.

Tenha em mente que quando você encontrar um número primo P durante a peneiração, você não começará a cruzar números na sua posição atual + P ; você realmente começa a cruzar os números em P^2 . Todos os múltiplos de P menores que P^2 serão cruzados pelos números primos anteriores.

  1. O laço interno faz n/i passos, onde i é primo => toda a complexidade é sum(n/i) = n * sum(1/i) . De acordo com séries harmônicas primárias, a 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 por sqrt(n) para que a complexidade geral do tempo seja O(sqrt(n)loglog(n)) :

     void isprime(int n) { int prime[n],i,j,count1=0; for(i=0;i 

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