Zeitaufwand Primfaktorzerlegung |
22.03.2014, 00:57 | Auf diesen Beitrag antworten » | |||||
zteve | Zeitaufwand Primfaktorzerlegung Hallo zusammen, ich habe ein Verständnisproblem mit der Lösung, die wir bekommen haben bezüglich des Zeitaufwands zu folgendem Algorithmus:
Bezüglich des Zeitaufwands ist folgende Lösung angegeben: Rechenzeitaufwand für Nächster Teiler ist beim ersten Aufruf höchstens N, beim zweiten Aufruf durch Teilen des Faktors N/T < N/2 beim dritten Aufruf durch weiteres Teilen N/T /T´ < N/2 /2 = N/4 Insgesamt höchstens N* (1 + ½ + ¼ + ..) < N*2 . Ich meine aber, dass das falsch ist: Wenn "NächsterTeiler" den Rechenzeitaufwand von N hat, dann gibt es keinen zweiten Aufruf von "NächsterTeiler" da, durch das Teilen dann N/T = 1 herauskommen würde. Das beim 2. Aufruf maximal N/2 Schritte benötigt werden setzt voraus, dass N halbiert wurde, also der 1. Aufruf 1 Schritt und nicht N Schritte gebraucht wurde, sondern der Teiler 2 die Liste halbiert. Somit würde ich sagen, der maximale Aufwand wäre eher: 1+1+1+1+1+1+... und das maximal log(N+1) + n-2 mal. Beispiel: anhand 56: 1. Primfaktor 2 (Durchlauf NächsterTeiler 1 Schritt) 2. Primfaktor 2 (Durchlauf NächsterTeiler 1 Schritt) 3. Primfaktor 2 (Durchlauf Nächster Teiler 1 Schritt) 4. Primfaktor 7 (Durchlauf Nächster Teiler 5 Schritte) Macht insgesamt: 3 + 5 = 8 Schritte bzw. log(8) + 7-2 = 8 Habe ich hier etwas übersehen, oder wie soll ich nun diese Musterlösung interpretieren? |
|||||
|
||||||
22.03.2014, 08:56 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Ich gebe dir Recht, dass die Lösung falsch ist.
was soll n sein? Das schlechteste Verhalten erreichst du, wenn die zu faktorisierende Zahl eine Primzahl ist. Dann brauchst du in NächsterTeiler N-1 Durchläufe. |
|||||
22.03.2014, 10:40 | Auf diesen Beitrag antworten » | |||||
zteve | Hallo, Danke für die Antwort. Hab mir das nohcmal durch den Kopf gehen lassen. Meine Formel log(n+1) + n-2 macht nur bedingt Sinn. n wäre hier quasi bei 56, die 7 --> 2*2*2*7=56 und 8 * 7 = 56. Also der Primzahlfaktor, der nach den 2ern kommt. Zusätzliche Bedingung, dass die Formel log(n+1) + n-2 stimmt ist aber dann auch, dass n genau eins weniger ist, als das Produkt der 2er ergibt. Also Beispiel: Bei 56 stimmt die formel (8*7 = 56 --> 2*2*2=8 --> 8-1 = 7 --> 8 * (8-1) = 56) Bei 40 stimmts nicht: (8*5 = 40 ---> 2*2*2 = 8 --> 8-3 = 5 --> 8* (8-3) = 40) Ich hoffe du versehst, woraus ich hinaus will. Also die Formel Log(n+1) + (n-2) mit n = der letzte Primfaktor nach den 2er Potenzen gilt nur, wenn sich die Zahl aus 2^x * ((2^x) - 1) zusammensetzen lässt. |
|||||
22.03.2014, 11:56 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Allgemein braucht der Algorithmus Summe(Teiler)-Anzahl(Teiler) modulo-Divisionen Für N=2^n * (2^n-1) und (2^n-1) als Primzahl sind das 2*n+(2^n-1)-(n+1) = 2^n+n-2 Schritte. Nach etwas Termumformung (ich hoffe, ich habe mich nicht verrechnet): für die 56 kommt da übrigens 9 raus, nicht 8. Für den letzten Faktor müss von 2-7 die modulo-Operation 6 mal ausgeführt werden. f(127*128) = 133 ist der nächste Wert der Folge, da 63 nicht prim ist. Unterm Strich bleibt festzustellen, dass es deutlich bessere Algorithmen zur Faktorisierung gibt. |
|||||
Anzeige | ||||||
|
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |