Zeitaufwand Primfaktorzerlegung

22.03.2014, 00:57

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:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

Eingabe N: Natürliche Zahl
Ausgabe PrimFak: Menge der Prim-Faktoren von N 

PrimFak := {}; 
While N>1 do 
  NächsterTeiler (N,T)
  N := N/T Füge T zu PrimFak


Funktion NächsterTeiler (Eingabe: N, Ausgabe:T) 
  T:=2 
  While N mod T != 0 do T:= T+1

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.

Zitat:

der maximale Aufwand wäre eher: 1+1+1+1+1+1+... und das maximal log(N+1) + n-2 mal.

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):
$[latex]f(N=2^n*(2^n-1))=\frac{1+\sqrt{1+4\cdot N}}{2}+\log_2(\frac{1+\sqrt{1+4\cdot N}}{2})-2[/latex]$
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.

Neue Frage »

Antworten »

Zeitaufwand Primfaktorzerlegung

Verwandte Themen