nicht angemeldet
Holladiewaldfee,
Den gibt es nicht. Die Laufzeit fuer einen
Fakultaets-Algorithmus ist bestenfalls linear, mit
etwas pech sogar quadratisch -- je nach dem, wie
du die Verwaltung grosser Zahlen machst. Du kommst
halt nicht drum herum, alle Elemente von 2 bis n
einschliesslich miteinander zu multiplizieren.
Hm, nö.
Die Fakultät ist definiert (!) durch das Integral über die Gammafunktion (Euler-Intergral zweiter Gattung):
x! := Gamma(x+1)
wobei (Maple-Syntax)
Gamma(x) := int(exp(-t) * t^(x-1), t=0..infinity)
also:
x! = int(exp(-t) * t^x, t=0..infinity)
Tja, dieses Integral gehört aber auch zu den Dingen, die wenig Spaß machen. Wenn er es schafft, das halbwegs vernünftig zu lösen könnte er am Ende schneller sein, als wenn er alle Zahlen miteinander multipliziert ;)
Dann gibt's da noch 'ne Näherung, die glaube ich aus der Stirling'schen Formel folgt:
ln(x!) ~ (x + 0.5) * ln(x) - x + ln(sqrt(2*Pi))
Lässt sich umformen zu
x! = exp(-x) * x^x * sqrt(2*Pi*x)
Zumindest das sollte dann schneller gehen als die ganzen Zahlen rauf und runter zu multiplizieren ... vielleicht ;)
Bloß ob der natürlich logarithmisch ist sei mal dahingestellt. Dafür kenn ich mich zu wenig mit so'm Zeug aus ;)
Ciao,
Harry