Ich habe einen Algorithmus entwickelt, um Faktoren einer bestimmten Zahl zu finden. So hilft es auch herauszufinden, ob die gegebene Zahl eine Primzahl ist. Ich denke, das ist der schnellste Algorithmus zum Auffinden von Faktoren oder Primzahlen.
Dieser Algorithmus findet heraus, ob eine gegebene Zahl im Zeitrahmen von 5 * N prim ist (wobei N die eingegebene Zahl ist). Ich hoffe, ich kann das einen linearen Zeitalgorithmus nennen.
Wie kann ich überprüfen, ob dies der schnellste verfügbare Algorithmus ist? Kann jemand in dieser Angelegenheit helfen? (schneller als GNFS und andere bekannt)
Algorithmus ist unten angegeben
%Vor%Bitte geben Sie Ihre Kommentare .. zögern Sie nicht, mich für weitere Informationen zu kontaktieren.
Danke, Harish Ссылка
"Lineare Zeit" bedeutet Zeit proportional zur Länge der Eingangsdaten: die Anzahl der Bits in der Anzahl, die Sie in diesem Fall zu faktorisieren versuchen. Ihr Algorithmus läuft nicht in linearer Zeit oder irgendetwas in der Nähe davon, und ich fürchte, es ist viel langsamer als viele existierende Factoring-Algorithmen. (Einschließlich z.B. GNFS.)
Die Größe der Eingabe ist in diesem Fall nicht n , sondern die Anzahl der Bits in n , sodass die Laufzeit Ihres Algorithmus in der Größe exponentiell ist die Eingabe. Dies ist bekannt als Pseudopolynomialzeit .
Ich habe Ihren Algorithmus nicht näher betrachtet, aber Primzahltests sind normalerweise schneller als O (n) (wobei n die Eingangsnummer ist). Nehmen Sie zum Beispiel diesen einfachen:
%Vor%Hier wird in O (sqrt (n)) bestimmt, ob n prim ist oder nicht, indem einfach alle möglichen Faktoren bis sqrt (n ) .
Tags und Links algorithm complexity-theory primes factorization