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

[informatik]Komplexitätsanalyse - Sieb des Eratosthenes

  • A

    ich habe den Algorithmus mal in einer Sprache umgesetzt mit
    ein Paar zählvariablen für schreibvorgänge innere schleife etc.

    static void Main(string[] args)
        {
            int myI = 0;
            int myJ = 0;

            int test = 42;

            int schreiben = 0;
            int lesen = 0;
            int schleife_aussen = 0;

            blubPrim[] primArray = new blubPrim[test];

            for (int i = 2; i < primArray.Length; i++)
            {
                primArray[i] = new blubPrim();
                primArray[i].GrafZahl = i;
                primArray[i].IsPrim = true;               
            }

            int schleife_innen = 0;
            myJ = 2;
            int ac = 0;
            int t = 0;
            int z = 0;
            while (myJ <= primArray.Length - 1)
            {
                schleife_aussen++;
                if (primArray[myJ].IsPrim == true)
                {
                    myI = 2 * myJ;
                    while (myI <= primArray.Length - 1)
                    {                        
                        if (primArray[myI].IsPrim == true)
                        {
                            primArray[myI].GrafZahl = myJ;
                            primArray[myI].IsPrim = false;
                            schreiben++;
                        }
                        myI = myI + myJ;
                        schleife_innen++;
                    //Console.WriteLine("myI " + myI + " arraylenght" + primArray.Length);
                    }
                    Console.WriteLine(schreiben + " "+schleife_innen);
                    z+=schreiben;
                    schreiben = 0;
                    t += schleife_innen;
                    if (schleife_innen == 0)
                    {
                        ac++;
                    }
                    schleife_innen = 0;

                }
                myJ++;
            }
            Console.WriteLine(schleife_aussen);
            schreiben += test - 2;
            decimal atock = schreiben / test;
            for (int a = 2; a < primArray.Length; a++)
            {
                if (primArray[a].IsPrim == true)
                {
                    Console.WriteLine(primArray[a].GrafZahl.ToString() + primArray[a].IsPrim.ToString());                    
                }                
            }
            Console.WriteLine(ac + " "+t);
            Console.WriteLine("summe innere schleifen: " + t + " " + "summe schreibvorgänge: " + z); 
        }
    }

    4 aufgaben habe ich dazu.
    a) bestimmten der teilkostenfunktion fürs schreiben Mwrite(N) mit Herleitung
    b) bestimmen der teilkostenfunktion fürs lesen Mread(N) mit Herleitung
    c) gesamtkostenfuntion
    d) komplexitätsklasse angeben

    fürs schreiben habe ich ersteinmal N-1
    fürs das schreiben in der inneren schleifen hab ich
    ∑k=2nn−1k!\sum_{k=2}^{\sqrt{n}} \frac{n-1}{k!}
    beides zusammen
    N−1+∑k=2nn−1k!N-1 + \sum_{k=2}^{\sqrt{n}} \frac{n-1}{k!}

    dann hab ich die gesamten Schreibvorgänge wollen die das überhaupt wissen?

    für b hab ich keine Ahnung für c auch nicht.
    und d) soll sein O(n*ln(ln(n)))
    kein Ahnung wie man darauf kommt.

    hinweise sind:
    1.
    ∑k=2n1k∗ln(k)≈lnlnn\sum_{k=2}^{n} \frac{1}{k*ln(k)} \approx ln\; ln \;n
    2. für pi_n, die anzahl der Primzahlen <= n gilt
    πn≅nlnn\pi _{n}\cong \frac{n}{ln\; n}
    3.
    für die n-te Primzahl gilt: p_n ~= n*ln(n)
    4.
    ln(nln(n)))ln\left ( \frac {n}{ln(n))} \right )

    ich komme mit den hinweisen nicht wirklich klar.
    vielleicht kann mir das jemand mal erläutern.

    danke

    0
  • ?

    Dein Algorithmus ist Müll, das geht viel effizienter in einem Bruchteil der Codezeilen die du hast.

    0
  • A

    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.

    0
  • M

    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.

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