Pottenzieren
-
otze schrieb:
SeppJ schrieb:
Es wird nach jedem Durchgang exp durch zwei geteilt bis exp Null ist, daher werden ~log_2(exp) Durchläufe gemacht.
Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!
Um ganz genau zu sein ist Variante 1 deswegen O(2^n). Bei einer Eingabe der Größe n-Bits braucht der Algorithmus 2^n Rechenschritte. Der andere Algorithmus hingegen ist O(n), da er bei jedem Schritt exakt 1 Bit abarbeitet.
Tatsächlich? Mal wieder was gelernt.
Du hast bei der Analyse jedoch Variante 1 und 2 verwechselt.
-
otze schrieb:
Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!
Es gilt die Größe für die Laufzeitberechnung, die man angibt. Die Größe der Eingabe in Bits ist da nicht unüblich. Kann sein, muß aber nicht.
-
otze schrieb:
Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!
Das kann man machen, wie man will. Du kannst die Laufzeit in Abhängigkeit der Eingabelänge angeben oder einfach in Abhängigkeit des Wert des Exponenten. Hauptsache, es ist klar, was gemeint ist.
Nur für den Fall, dass das noch nicht erwähnt worden ist: Der eine Algorithmus heißt "square and multiply".
kk
-
Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...
-
DocShoe schrieb:
Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...
Ach, dann kann man auch noch kommen, dass jemand komplexe Exponenten will. Oder Matrixexponenten. Oder einen Tensor 15-ter Stufe über den Quaternionen. Mit einer hyperkomplexen Basis.
Lassen wir das Problem doch erstmal einfach.
-
DocShoe schrieb:
Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...
ich hab extra unsigned davor geschrieben, um deutlich zu machen, dass er das nicht sein kann(darf^^) ;P
bb
