4. [informatik]Komplexitätsanalyse - Sieb des Eratosthenes

[informatik]Komplexitätsanalyse - Sieb des Eratosthenes

  • A

    also würde sagen die innere schleifen läuft immer mit N/J durch,
    jetzt könnte man vielleicht die Warscheinlichkeit zunehmen.
    am Anfang ist die Warscheinlichkeit ob prim oder nicht prim 1/2 dann nur noch 1/3
    , 1/4 und so weiter...

    ist das der Ansatz?

    wenn ich mir das so anschaue könnte hier der 1. Hinweis in frage kommen.

    0
  • T

    Welchen Ansatz hast du den für Mread(N)?

    0
  • A

    also n-1 hatten wir ja schon.
    anfangs kann ich viel weg streichen, die Warscheinlichkeit sinkt
    mit jedem Durchlauf.

    also würd ich hier auf die harmonischen Zahlen schauen mit
    ∑k=2n1k\sum_{k=2}^{n} \frac {1}{k}

    aber die Warscheinlichkeit fällt in diesem fall etwas stärker ab, weshalb ich hier auf den Hinweis 1. zurück greifen würde

    ∑k=2n1klnk≈lnlnn\sum_{k=2}^{n} \frac {1}{k \; ln k} \approx ln ln n

    dann hätte ich schon etwas wie
    n−1+.....lnlnnn-1 + ..... ln ln n
    bei den ... fehlt dann noch was

    0
  • M

    Nein, mit Wahrscheinlichkeiten kommst du hier nicht weiter. Ignorier den ersten Tipp, der verwirrt dich anscheinend mehr als er dir hilft. Hast du denn nun die Lösung für die Schreiboperationen?

    0
  • A

    aso, das da oben war noch zum schreiben.
    für read muss ich mich nacher nochmal hinsetzen, erstmal wollen
    die Hunde raus.

    bin schon echt am verzweifeln sitze schon ewig dran, muss das heute abgeben,
    ich überlege schon ob mir 70pkt für die einsendeaufgaben reichen 🙂

    0
  • A

    ich hab nen bischen bei wiki rumgewühlt.

    ok, nochmal zum schreiben. für das markieren der zahlen könnte ich N/J
    nehmen als obere grenze mit n/2+n/3+n/4 ....., was aber noch zu ungenau ist
    genauer wäre n(1/2+1/3+1/4 ... 1/n) also könnte ich jetzt schreiben
    n ln(n). Noch besser wäre mit Primzahlen n(1/2+1/3+1/5+1/7 ... 1/n).

    also wäre dann die Lösung m_write = n-1+ n ln ln n?

    0
  • V

    Supi. Genau die richtige Richtung.
    Und jetzt die Tipps annehmen.
    Du musst nicht jede Scheiße summieren, wenn die Vorgabe schon was summiert hat.

    0
  • A

    also n-1 rauslassen dass nurnoch n ln ln n bleibt?

    0
  • M

    volkard schrieb:

    Supi. Genau die richtige Richtung.

    Nein. Die richtige Richtung ist: Am Anfang werden alle Zahlen gesetzt. Dann werden die Nicht-Primzahlen exakt einmal gesetzt. Macht insgesamt n-1 plus die Anzahl der Nicht-Primzahlen.

    0
  • A

    also n-1 + summe 2n (geschnitten) summe 3n ...... ?

    0
  • M

    adonis schrieb:

    also n-1 + summe 2n (geschnitten) summe 3n ...... ?

    Ich verstehe nicht, was du mir sagen willst. Die Anzahl der Nicht-Primzahlen ist die Anzahl aller Zahlen minus die Anzahl der Primzahlen. Beide Größen hast du gegeben.

    0
  • A

    ich will die menge vielfachen vom 2 + der menge der vielfachen von 3
    die in 2 nicht drin sind usw

    ok, also ich brauch die Summenformel der natürlichen zahlen - hinweis 2

    0
  • M

    adonis schrieb:

    ich will die menge vielfachen vom 2 + der menge der vielfachen von 3
    die in 2 nicht drin sind usw

    Dafür gibts das Inklusions-Exklusions-Prinzip. Aber ich sehe nicht, warum du das hier brauchst.

    Edit: Die eben von mir genannte Lösung ist die Endlösung. Du brauchst nicht mehr über die verschiedenen Iterationen zu summieren.

    0
  • A

    also summen formel für die natürlich zahlen - 2. hinweis

    Mit dem was ich oben geschrieben hab, erhalte ich doch die Anzahl der
    nicht Primzahlen. wenn ich jetzt die summe aller zahlen nehme und die abziehe
    hab ich die summe aller Primzahlen.

    ich könnte ja noch summe der mengen bilden die in nicht beiden vorkam und die draufzählen auf die menge der vielfachen von 2, dann hab ich doch die Anzahl der Schreibvorgänge.

    0
  • A

    also Idee menge A (4 6 8 ... n)
    Menge B (6 9 12 15 ...n)

    für die Schreibvorgänge anzahl von menge A + anzahl nicht(A durchschnitt 😎
    und so weiter + die erste for-schleife.

    Würde jetzt noch Eine Menge C hinzukommen die vielfachen von wäre der nächste
    summand wäre 0 weil C in A drin ist

    Jetzt müsste man vielleicht überlegen wie die Anzahl des weg streichens sinkt.

    oder Abschätzungen machen wenn n steigt, steigt auch die Laufzeit.
    Es wird mehr als linear ansteigen aber weniger als quadratisch, also
    irgendwas im n log n oder n log² n Bereich.

    ich würde das begründen durch da wegstreichen der vielfachen von 2.
    wenn n wächst hätte ich einen linearen anstieg. dann kommt noch das
    wegstreichen der anderen zahlen dazu, was aber weniger sein sollte als n²

    0
  • M

    Puh, erst einmal unterscheide bitte zwischen Summe und Anzahl. Ich kann dich nur bitten, die Antworten in Ruhe noch einmal durchzulesen. Hör auf, irgendwelche Mengen zu schneiden. An jeder Primzahlposition wird im gesamten Verlauf des Algorithmus genau einmal geschrieben, an jeder Nicht-Primzahlposition genau zweimal. Macht insgesamt 1 * n / log(n) + 2 * (n - n / log(n)).

    0
  • A

    mhh? also wenn ich den code durch arbeite wird erst einmal jede zahl als
    Primzahlkandidat markiert, und anschließend wird jede nicht Primalzahl
    rausgenommen. und durch die if-bedingung wird nur einmal jede der Position
    geschrieben.

    Zum Schluss sind nurnoch die Primzahlen mit 0 markiert.

    wie kommst du auf 2-mal bei jeder "nicht Primzahl" Position?

    zeile 11 ist der punkt, er scheibt die Primzahl nicht, sie wird gleich mit
    2 multiplizert.

    ende müsste also so aussehen.

    0 0 4 0 6 0 8 9 10 0 12 0 14 usw

    vielleicht ist n/j doch kein schlechter Ansatz wieviele in N lassen sich
    durch 2 teilen + den Anteil der sich durch 3 teilen lässt was aber zu ungenau
    ist

    dann wären wir schon wieder fast am anfang

    0
  • T

    Du hast sogar selbst geschrieben warum es 2 Schreibvorgänge für nicht-Primzahlen ist:

    wird erst einmal jede zahl als
    Primzahlkandidat markiert

    1. Schreibvorgang für alle

    anschließend wird jede nicht Primalzahl
    rausgenommen

    2. Schreibvorgang, diesmal nur für nicht Primzahlen

    0
  • A

    achso ja das ist wohl wahr
    ok jetzt verstehe ich langsam ...

    jetzt erscheint es irgendwie logisch...

    aber was fehlt mir? Übung oder ist es einfach nur mathematisches Verständnis
    ich wär glaub nie drauf gekommen

    0
  • A

    aber auf jeden fall danke,
    vorallem der geduld von Michael E..

    bringt mir zwar nichts mehr da ich schon abgegeben hab, aber sowas wurmt mich
    immer

    0
Anmelden zum Antworten