Zeitkomplexität von Sieb des Eratosthenes Algorithmus

Question

Wikipedia:

  

Die Komplexität des Algorithmus ist   O(n(logn)(loglogn)) Bit-Operationen.

Wie erreichen Sie das?

Dass die Komplexität umfasst der loglogn Begriff sagt mir, dass es eine sqrt(n) irgendwo.

---

Nehmen wir an ich das Sieb auf den ersten 100 Zahlen leite (n = 100), dass Markierung unter der Annahme, die Zahlen als Verbund konstante Zeit (Array-Implementierung) nimmt die Anzahl der Male, die wir mark_composite() verwenden wäre so etwas wie

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

Und die nächste Primzahl zu finden (zum Beispiel 7 zu springen, nachdem alle Zahlen Auskreuzen, die ein Vielfaches von 5 sind), würde die Anzahl der Operationen sein O(n).

So würde die Komplexität O(n^3) sein. Sind Sie damit einverstanden?

Answer 1

1. n / 2 + n / 3 + n / 5 + ... n / 97 ist nicht O (n), da die Anzahl der Bedingungen nicht konstant ist. [Bearbeiten nach dem Bearbeiten. O (n ² ) ist locker eine oberen Grenze] Ein loser Ober gebunden ist n (1 + 1/2 + 1/3 + 1/4 + 1 / 5 + 1/6 + ... 1 / n) (Summe der reziproken alle Zahlen bis n), die O (n log n): siehe Harmonic Nummer . Eine geeignete obere gebunden ist n (1/2 + 1/3 + 1/5 + 1/7 + ...), die Summe der reziproken Werte der Primzahlen bis N ist, das ist O (n log n log). (Siehe hier oder hier .)

2. Der "findet die nächste Primzahl" Bit ist nur O (n) insgesamt amortisiert - werden Sie vor, um die nächste Zahl zu finden nur n-mal in total , nicht pro Schritt. Also der ganze Teil des Algorithmus nimmt nur O (n).

So diese beiden verwenden Sie einen oberen von O gebunden erhalten (n log n log) + O (n) = O (n log log n) arithmetischen Operationen. Wenn Sie Bit-Operationen zählen, da man es zu tun mit Zahlen n up, haben sie etwa log n Bits, die ist, wo der Faktor log n kommt, gibt O (n log n log n log) Operationen Bit.

Answer 2

  

Dass die Komplexität umfasst der loglogn Begriff sagt mir, dass es eine sqrt (n) irgendwo.

Beachten Sie, dass, wenn Sie eine Primzahl P finden, während Sieben, Sie überqueren nicht beginnen Zahlen an Ihrer aktuellen Position + P; Sie beginnen tatsächlich aus Zahlen bei P^2 überqueren. Alle Vielfachen von P weniger als P^2 wird von früheren Primzahlen gestrichen wurden.

Answer 3

1. Die innere Schleife tut n/i Schritte, wo i prime = ist> das ganze Komplexität ist sum(n/i) = n * sum(1/i). Nach prime harmonischen Serie, die sum (1/i) wo i Primzahl ist log (log n). Im Insgesamt O(n*log(log n)).

2. Ich denke, die obere Schleife durch Ersetzen n mit sqrt(n) optimiert werden kann, so Gesamtzeitkomplexität wird 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 4

siehe die obige Erklärung nimmt die innere Schleife ist harmonische Summe aller Primzahlen bis sqrt (n). So ist die tatsächliche Komplexität O (sqrt (n) * log (log (sqrt (n))))