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

[informatik]Komplexitätsanalyse - Sieb des Eratosthenes

  • A

    Ah, entschuldigung!
    hier einfach wie in der Aufgabe:

    Algorithmus Eratosthenes(N: integer) A: Array[2...N] of integer;
var i,j:integer;
var A:array[2..N] of ineter;
begin
 for i := 2 to N do
     A[i] := 0;
 end for
j:= 2;
while j <= N do
  if A[j] = 0 then
  i:= 2*j;
  while i <= N do
     if A[i] = 0 then
        A[i] = j;
     end if
     i := i +j
  end while;
  end if
  j:= j + 1
end while
return A
end Eratosthenes.

    bei hinweis 4 steht nicht mehr im aufgabenblatt.

    M_write(n) soll jeder schreib zugriff auf das Array sein mit dem kostenmaß 1
    m_read(n) soll jeder lesende zugriff auf das Array sein mit kostenmaß 1

    für M_write(n) habe mit einem kumpel rausbekommen
    N−1+∑k=2nn−1k!N-1 + \sum_{k=2}^{\sqrt{n}} \frac{n-1}{k!}
    wir konnten damit auch vorhersagen treffen für steigendes N.

    wir hatten gefunden daß die innere schleife maximal nur wurzel n mal ausgeführt
    wird.

    für die schreibvorgänge hatten wir festgestellt
    wenn wir 2....20 haben
    1. innere schleifendurchlauf 9 x schreiben
    2. innere schleifendurchlauf 3 x schreiben
    danach immer 0 x schreiben

    auf das Ergebnis kommt man auch wenn man:
    19/2 = 9
    9/3 = 3
    3/4 = 0
    das macht 12 Schreibvorgänge

    oder halt mir n-1/k!

    19/2 = 9
    19/6 = 3
    19/24 = 0

    macht auch 12 Schreibvorgänge

    und jetzt noch + n-1 für die erste for-schleife.
    kann ich diese formal für m_write dann stehen lassen?

    oder kann man sich hier an die Formel für harmonische zahlen wenden
    was dann auf ln n hinauslaufen würde?

    wie sieht es für read aus, gelesen wird ja weit aus öfter

    0
  • M

    Also habt ihr für die Schreiboperationen einfach nur für kleine Zahlen ausprobiert, was stimmen könnte? Die n - 1 Schreibvorgänge fürs Nullen des Arrays stimmen schon mal. Danach gibts nur noch in Zeile 14 eine Schreiboperation. Betrachte nun nicht die Schreiboperationen auf dem gesamten Array in einer Iteration, sondern für ein einzelnes Arrayelement während der gesamten Laufzeit. Wie häufig wird für ein festes i der Wert A[i] gesetzt? Hierbei gibt es die Fälle "prim" und "nicht prim". Summiere dann die Werte für alle i.

    Beim Zählen der Leseoperationen gehst du dann wieder pro Iteration vor und nicht pro Arrayelement.

    0
  • A

    Ich hatte in die if-Bedingung einen Zähler eingebaut, der sollte mir ja ausgeben
    die oft A[i] gestetzt wird.

    Wenn es korrekt ist könnte ich vielleicht noch etwas basteln mit N/j;

    mhh ganz schön hart so als erste hausaufgabe....

    0
  • M

    adonis schrieb:

    Ich hatte in die if-Bedingung einen Zähler eingebaut, der sollte mir ja ausgeben
    die oft A[i] gestetzt wird.

    Gewöhn dir diese Vorgehensweise am besten direkt wieder ab. Es bringt zwar manchmal was, den Algorithmus von Hand auszuführen, um ein Gefühl für ihn und seine Laufzeit zu bekommen. Aber von ein paar Messwerten auf das korrekte Wachstum zu kommen, ist äußerst fehleranfällig. Außerdem kannst du in der Zeit, in der du den Zähler in den Code einbaust, bereits mit der eben von mir genannten Überlegung das tatsächliche Wachstum angeben.

    0
  • 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
Anmelden zum Antworten