[informatik]Komplexitätsanalyse - Sieb des Eratosthenes

adonis

Darum geht es aber nicht, der Algorithmus ist so vorgegeben.
Es geht um die 3 Schleifen, die obere for-Schleife und die 2
geschachtelten while-Schleifen.

Die ganzen zählvariablen sind nur zu analysezwecken drin.
Den ganzen Analyse kram den ich für mich reingeschrieben habe
sind dann 32 Zeilen weniger.

Michael E.

Dein Beitrag ist etwas wirr. Zuerst einmal wäre es nett, wenn du den Code wie in der Aufgabenstellung angibst und nicht mit unzähligen "Analyse"-Zeilen zugespammt. Die Klasse blubPrim kennen wir nicht (und klingt auch nicht sinnvoll), genauso wie ihren Member GrafZahl. So lese ich mir den Code nicht weiter durch. Was sind Mread(N) und Mwrite(N)? Dein vierter Hinweis steht nicht vollständig da.

Überlege dir erst, wie viel Aufwand du mit den Iterationen einer einzelnen Primzahl k hast, wenn du bis zur Zahl n siebst. Dann ersetzt du k durch p_k. Summiere daraufhin über alle Primzahlen bis zur Zahl n. Deine Hinweise sollten dir dabei einer nach dem anderen ins Auge springen.

adonis

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 + \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

Michael E.

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.

adonis

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....

Michael E.

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.

adonis

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.

ta

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

adonis

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
$\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

$\sum_{k=2}^{n} \frac {1}{k \; ln k} \approx ln ln n$

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

Michael E.

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?

adonis

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

adonis

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?

volkard

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

adonis

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

Michael E.

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.

adonis

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

Michael E.

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.

adonis

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

Michael E.

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.

adonis

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.