sayuviech Geschrieben 29. November 2010 Geschrieben 29. November 2010 Guten Morgen, Ich habe eine Aufgabe zum Thema Primzahltest und Komplexität zu lösen: Z ist die Zahl, für die getestet werden soll, ob sie eine Primzahl ist. n ist die Anzahl der Dezimalstellen (zb. 17 hat 2 Dezimalstellen). Für jede Zahl T von 2 bis Wurzel Z wird geprüft, ob sie eine Primzahl ist, indem der Rest der Zahl Z durch T mit der Null verglichen wird (ist dieser Null, so ist ein Teiler von Z gefunden). Ich soll nun die Komplexität dieses Algorithmus in Abh. von den Dezimalstellen in O-Notation angeben und begründen, wie ich darauf gekommen bin... Ich weiß, dass die Komplexität Wurzel Z wäre, aber ich darf sie nicht in Abh der Zahl sondern nur in Abh der Dezimalstellen (n) angeben... könnt ihr mir vll helfen??? lg Maya Zitieren
Klotzkopp Geschrieben 29. November 2010 Geschrieben 29. November 2010 Die Anzahl der Stellen einer Zahl ist proportional zu ihrem Logarithmus. Zitieren
sayuviech Geschrieben 29. November 2010 Autor Geschrieben 29. November 2010 und das heißt??? ich habe mir schon überlegt, dass vielleicht O(n) = 10^n sein könnte... aber ich weiß nicht, ob das stimmt und wenn ja, wieso... Zitieren
Klotzkopp Geschrieben 29. November 2010 Geschrieben 29. November 2010 und das heißt???Das ist der Zusammenhang zwischen n und Z, der dir offenbar fehlt. Dein Algorithmus braucht offenbar Wurzel(Z) Operationen. Jetzt ersetzt du das Z durch einen passenden Ausdruck, der n enthält, und dann hast du's doch schon. Zitieren
sayuviech Geschrieben 29. November 2010 Autor Geschrieben 29. November 2010 Das ist der Zusammenhang zwischen n und Z, der dir offenbar fehlt. Dein Algorithmus braucht offenbar Wurzel(Z) Operationen. Jetzt ersetzt du das Z durch einen passenden Ausdruck, der n enthält, und dann hast du's doch schon. genau das ist mein problem... ich habe keine ahnung was ich stattdessen angeben könnte... wuzel Z hatte ich zunächst auch, aber ich darf die laufzeit leider nicht in abh von der zahl angeben, sondern nur in abh ihrer dezimalstellen... Zitieren
sayuviech Geschrieben 29. November 2010 Autor Geschrieben 29. November 2010 ich glaube ich habs: Wurzel (10^n), also 10^(n/2) liefert genau die Werte die ich brauche jetzt muss ich mir nurnoch überlegen, wie ich die 10^n begründe... Zitieren
Klotzkopp Geschrieben 30. November 2010 Geschrieben 30. November 2010 jetzt muss ich mir nurnoch überlegen, wie ich die 10^n begründe...10^n ist eine obere Schranke für eine n-stellige Zahl, denn 10^n ist die kleinste n+1-stellige Zahl. Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.