Laufzeit Probedivision und AKS-Test

Neue Frage »

ichbinneu Auf diesen Beitrag antworten »
Laufzeit Probedivision und AKS-Test
Guten Tag,

die Probedivision hat in der naiven Methode, alle Zahen bis zur Wurzel der Eingabe zu überprüfen eine laufzeit von O(n^(1/2) ).
Aber damit liegt doch polynomialzeit vor. Warum wird gesagt, der AKS-Test wäre der erste gewesen?
Die Probedivision ist ja schließlich auch deterministisch.

Danke und Gruß
g4lois Auf diesen Beitrag antworten »

Hallo,

du hast zwei Denkfehler. Sein die zu testende natürliche Zahl.

Man muss zwar maximal Divisionen durchführen, darf die Divisionszeit in diesem Fall aber nicht als konstant annehmen. Eulikds Algorithmus beispielsweise hat eine Laufzeit von , die zusätzlich beachtet werden muss.

Der zweite Fehler ist aber viel gravierender. Die Laufzeit wird über die Eingabebits definiert, d.h. bzw. . Also mit exponentiellem Wachstum.
ichbinneu Auf diesen Beitrag antworten »

g4lois, vielen Dank. Sehr interessant.

Zu deinem ersten Punkt: Was ist genau mit der Divisionszeit gemeint?
Wenn ich das richtig interpretiere, so aus der Luft hinaus, die Anzahl der "Iterationen", um zwei Zahlen zu dividieren? Und diese ist also nicht konstant?
Auch sehr interessant zu wissen, ging ich doch davon aus, dass zur Laufzeitbestimmung hier die Anzahl der Divisionen (und nicht nochmal deren Zeit) gemessen wird.

Das die Laufzeit mit den benötigten Bits gemessen wird habe ich oft gelesen, aber das es der Definition entspricht, war mir fremd. Hab vielen Dank für diese aufschlussreiche Antwort.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »