Primzahlalgorithmus- O-Notation

16.05.2011, 11:48

Struppii

Primzahlalgorithmus- O-Notation

Meine Frage:
Hallo!
Und zwar beschäftige ich mich mit diesem Algorithmus zur Bestimmung ob eine Zahl prim ist oder nicht.[attach]19641[/attach] Ich verstehe auch die einzelnen Schritte und weiß warum er funktioniert etc. Leider habe ich ein Problem mit der O-Notation. Und zwar steht da, dass er $\begin{eqnarray*} O(\sqrt{n} ) \end{eqnarray*}$ Schritte benötigt... Wo kommt das her und warum bedeutet das, dass der Algorithmus eine exponentielle Komplexität hat? Außerdem verstehe ich nicht, warum der Algorithmus nur 10 Speicherplätze benötigt?

Meine Ideen:
Für Ideen wäre ich sehr dankbar!

16.05.2011, 12:50

René Gruber

Auf diesen Beitrag antworten »

Irgendwie fehlt da die Angabe des Wertes $\begin{eqnarray*} d_2 \end{eqnarray*}$ , nicht wahr? verwirrt

16.05.2011, 12:59

Struppii

Auf diesen Beitrag antworten »

Das ist ein Tippfehler, entschuldige. Richtig heißt es:
[attach]19645[/attach]

16.05.2011, 13:06

René Gruber

Auf diesen Beitrag antworten »

Ok, kommen wir zu weiteren Kritikpunkten. Bei 4. sollte m.E. nach eher while (p<m) statt while (p<m) stehen, aber das verbuche ich mal noch unter Schreibfehler. Viel gravierender ist folgendes:

Was liefert der Algorithmus, wenn man ihn auf die Zahl $\begin{eqnarray*} n=73^2 \end{eqnarray*}$ loslässt: Primzahl!!! unglücklich

M.E. ist dein "Radalgorithmus" nur zu retten, wenn man eine weitere Zahl $\begin{eqnarray*} d_7=6 \end{eqnarray*}$ anfügt, und in der Konsequenz das $\begin{eqnarray*} i\leftarrow i+1 \bmod 7 \end{eqnarray*}$ im Schritt 4 durch $\begin{eqnarray*} i\leftarrow i+1 \bmod 8 \end{eqnarray*}$ ersetzt. Erst dadurch ist das ja wohl zugrunde liegende Konstruktionsprinzip gewahrt, dass $\begin{eqnarray*} p \end{eqnarray*}$ alle die Zahlen durchläuft, die weder durch 2,3 oder 5 teilbar sind.

16.05.2011, 13:14

Struppii

Auf diesen Beitrag antworten »

Das mit dem kleiner/ gleich Zeichen ist mir auch schon aufgefallen und habs geändert. Also ich kenn mich leider nicht so aus mit Algorithmen (studiere Mathe im 2. Semester), ich muss nur mein Proseminar darüber halten und bin daher mal davon ausgegangen, dass der Author schon dafür sorgt, dass der funktioniert. Und ich finde die Schritte auch logisch, also kann ich mir nicht erklären, warum da was falsches rauskommt? unglücklich

16.05.2011, 13:17

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Struppii
also kann ich mir nicht erklären, warum da was falsches rauskommt? unglücklich

Hast du mal $\begin{eqnarray*} n=73^2 \end{eqnarray*}$ damit durchgerechnet, oder hast du es nicht?

16.05.2011, 13:38

Struppii

Auf diesen Beitrag antworten »

Also laut der Bemerkung davor ist es so, dass wenn p eine Primzahl ist, p entweder 2,3,5 ist oder $\begin{eqnarray*} p \equiv 1,7,11,13,17,19,23,29 \end{eqnarray*}$ (mod 30)
Wegen diesen Abständen setzen wir ja die d's. Wenn wir jetzt $\begin{eqnarray*} d_7=6 \end{eqnarray*}$ setzen, sind wir aber ja wieder bei 7. Und wir haben ja schon geprüft ob 7 ein Teiler ist...
Wie kann ich denn $\begin{eqnarray*} n=72^2 \end{eqnarray*}$ nachrechnen? Kann ich den Algorithmus irgendwo eingeben?

16.05.2011, 13:40

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Struppii
Wenn wir jetzt $\begin{eqnarray*} d_7=6 \end{eqnarray*}$ setzen, sind wir aber ja wieder bei 7.

wohl eher bei 37, 67, ...

Und genau dieser Schritt ist noch nötig! Wenn du das nicht begreifst, hast du das Konstruktionsprinzip des Algorithmus nicht verstanden.

16.05.2011, 15:12

Struppii

Auf diesen Beitrag antworten »

Du hattest Recht! ich hatte das Prinzip noch nicht verstanden! Vielen, vielen Dank! Das erklärt nun auch auf jeden Fall die 10 Speicherplätze und die $\begin{eqnarray*} O(\sqrt{n} ) \end{eqnarray*}$ Schritte.
Jetzt müsste ich nur noch verstehen, warum man dann von exponentieller Zeitkomplexität spricht. Der Begriff ist im Zusammenhang mit einem Vorherigem Logerithmus gefallen, der $\begin{eqnarray*} O( \frac{\sqrt{n}}{log \sqrt{n}} \end{eqnarray*}$ ) Schritte benötigt. Aber da der Radalgorithmus noch mehr Schritte hat, müsste er doch auch exponentielle Zeitkomplexität haben oder?
Ich weiß, dass es etwas mit der Länge der Eingabekette zu tun hat, aber ich kann mich nicht so richtig etwas darunter vorstellen.
Vielen, vielen Dank auf jeden Fall schonmal für die Hilfe!

16.05.2011, 15:27

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Struppii
Aber da der Radalgorithmus noch mehr Schritte hat, müsste er doch auch exponentielle Zeitkomplexität haben oder?

Da bin ich überfragt, da ich die Definition von "exponentieller Zeitkomplexität" nicht kenne. Irgendwie hätte ich von der Namensgebung her da aber eher an etwas gedacht, was sämtliche polynomiellen Komplexitäten $\begin{eqnarray*} O(n^k) \end{eqnarray*}$ übersteigt, was ja hier klarerweise nicht der Fall ist. verwirrt

EDIT: Ok, die Namensgebung wäre erklärbar, wenn die Bezugsgröße dieser Komplexitätsbezeichnung nicht $\begin{eqnarray*} n \end{eqnarray*}$ , sondern die Bitlänge $\begin{eqnarray*} \log_2(n) \end{eqnarray*}$ der Eingangsgröße $\begin{eqnarray*} n \end{eqnarray*}$ ist. verwirrt

16.05.2011, 15:52

Struppii

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
EDIT: Ok, die Namensgebung wäre erklärbar, wenn die Bezugsgröße dieser Komplexitätsbezeichnung nicht $\begin{eqnarray*} n \end{eqnarray*}$ , sondern die Bitlänge $\begin{eqnarray*} \log_2(n) \end{eqnarray*}$ der Eingangsgröße $\begin{eqnarray*} n \end{eqnarray*}$ ist. verwirrt

Könntest du das nochmal genauer erklären? Woher weiß ich denn was die Bezugsgröße ist?

16.05.2011, 15:57

René Gruber

Auf diesen Beitrag antworten »

Nochmal: Ich kenne eure Definition der "exponentiellen Zeitkomplexität" nicht, ich habe nur Mutmaßungen darüber angestellt. Wie soll ich also etwas erklären, was ich nur geraten habe? Augenzwinkern

Wenn das also alles auf eine serösere Grundlage gestellt werden soll, musst du mit entsprechenden Definitionen rüberkommen.

16.05.2011, 20:13

Struppii

Auf diesen Beitrag antworten »

Also alles was ich dazu noch in dem Buch gefunden hab war
[attach]19662[/attach] und [attach]19663[/attach] Und davor wurde noch gesagt, dass $\begin{eqnarray*} log(n) \end{eqnarray*}$ immer als $\begin{eqnarray*} log_2 (n) \end{eqnarray*}$ aufgefasst werden soll. Das war aber alles seehr viel weiter vorn im Buch und hat damit soweit ich das sehen kann nichts zu tun. Mh Schade. Dann lass ich das einfach weg in meinem Vortrag...

17.05.2011, 03:00

Kai__

Auf diesen Beitrag antworten »

In dem Zusammenhang ist m.E. nach relevant, dass n unaer aufgefasst wird, und damit der Zeitbedarf exponentiell wird.

Ohne Gewaehr! Augenzwinkern

Neue Frage »

Antworten »

Primzahlalgorithmus- O-Notation

Verwandte Themen