Zeitkomplexität des Siets des Eratosthenes-Algorithmus

Vom Wikipedia:

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

Wie kommen Sie an?

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

Angenommen, ich bin mit dem Sieb auf die ersten 100 zahlen (n = 100), vorausgesetzt, dass die Kennzeichnung der zahlen als zusammengesetzte benötigt Konstante Zeit (array-Implementierung), die Anzahl der Zeiten, die wir verwenden mark_composite() wäre so etwas wie

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

Und finden Sie die nächste Primzahl (zum Beispiel, zu springen, um 7 nach der überquerung alle zahlen, die Vielfache von 5), die Anzahl der Operationen wäre O(n).

So, die Komplexität wäre O(n^3). Sind Sie damit einverstanden?

InformationsquelleAutor der Frage Lazer | 2010-04-06

  1. 92

    1. Ihre n/2 + n/3 + n/5 + ... n/97 ist nicht O(n), weil die Anzahl der Begriffe ist nicht konstant. [Edit nach deinem edit: O(n2) zu Locker ist eine Obere Schranke.] Eine lockere Obere Schranke n(1+1/2+1/3+1/4+1/5+1/6+...1/n) (Summe der kehrwerte der alle zahlen bis n), die O(n log n): siehe Harmonische Reihe. Eine richtige Obere Schranke n(1/2 + 1/3 + 1/5 + 1/7 + ...), das ist die Summe der kehrwerte der Primzahlen bis n, die O(n log log n). (Siehe hier oder hier.)

    2. "Finden Sie die nächste Primzahl" - bit wird nur O(n) insgesamt, abgeschrieben — Sie wird vorne bewegen, um die nächste Nummer, nur n-mal in insgesamtnicht pro Schritt. So ist dieser ganze Teil des Algorithmus benötigt nur O(n).

    Also mit diesen beiden bekommen Sie eine Obere Schranke von O(n log log n) + O(n) = O(n log log n) arithmetische Operationen. Wenn Sie die Anzahl bit-Operationen, da Sie den Umgang mit zahlen bis n, die Sie über log n bits, die ist, wo der Faktor von log n kommt, was O(n log n log log n) bit-Operationen.

    InformationsquelleAutor der Antwort ShreevatsaR

  2. 8

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

    Beachten Sie, dass wenn Sie eine Primzahl P während der Siebung, die Sie nicht anfangen zu überqueren von zahlen auf Ihre aktuelle position + P; Sie tatsächlich beginnen, überqueren von zahlen auf P^2. Alle vielfachen von P weniger als P^2 wurden Durchgestrichen, die von vorherigen Primzahlen.

    InformationsquelleAutor der Antwort jemfinch

  3. 5
    1. Die innere Schleife wird n/i Schritte, wo i ist prim => das ganze
      Komplexität ist sum(n/i) = n * sum(1/i). Laut prime harmonische
      Serie, die sum (1/i) wo i ist prime ist log (log n). In
      insgesamt O(n*log(log n)).

    2. Denke ich, dass die Obere öse kann optimiert werden durch den Austausch n mit sqrt(n) also insgesamt Zeit Komplexität 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;
        }
    }    
}

    InformationsquelleAutor der Antwort anand tripathi

Schreibe einen Kommentar