BeniBela
27.09.2003, 18:33
Hallo
Gibt es einen Algorithmus der die Fakultät in logarithmischer Zeit berechnen kann?
Benito
Gibt es einen Algorithmus der die Fakultät in logarithmischer Zeit berechnen kann?
Benito
Archiv verlassen und diese Seite im Standarddesign anzeigen : Fakultät in O(log n) berechnen
01Detlef
27.09.2003, 20:53
hi,
was ist denn das, Fakultät in logarithmischer Zeit
detlef
was ist denn das, Fakultät in logarithmischer Zeit
detlef
Lim_Dul
27.09.2003, 21:05
Ich wüsste jetzt keinen und glaub auch nicht, dass das geht.
Aber beweisen kann ich es nicht.
PS: In logarithmischer Zeit heißt, um n! zu berechnen, braucht man nur log(n) schritte (Vereinfach ausgedrückt)
Aber beweisen kann ich es nicht.
PS: In logarithmischer Zeit heißt, um n! zu berechnen, braucht man nur log(n) schritte (Vereinfach ausgedrückt)
upsidedown
27.09.2003, 21:11
Wuerd ich jetzt vom Gefuehl her auch sagen - das einzige was mir jetzt dazu einfaellt waere eine Tabelle von Zwischenergebnissen zu hinterlegen von denen mal aus die Berechnung dann starten kann.
Lim_Dul
27.09.2003, 21:14
Originalnachricht erstellt von upsidedown
Wuerd ich jetzt vom Gefuehl her auch sagen - das einzige was mir jetzt dazu einfaellt waere eine Tabelle von Zwischenergebnissen zu hinterlegen von denen mal aus die Berechnung dann starten kann.
Damit kommt man aber auch nicht auf O(log n), da ich einfach n so groß machen kann, dass die Zwischenergebnisse irrelevant sind.
Wuerd ich jetzt vom Gefuehl her auch sagen - das einzige was mir jetzt dazu einfaellt waere eine Tabelle von Zwischenergebnissen zu hinterlegen von denen mal aus die Berechnung dann starten kann.
Damit kommt man aber auch nicht auf O(log n), da ich einfach n so groß machen kann, dass die Zwischenergebnisse irrelevant sind.
TheoChem
27.09.2003, 21:19
Hallo,
die Fakultät ist n! = 1 * 2 * 3* ... * n (Produkt aller ganzen Zahlen von 1 bis n), wobei n >= 1 und ganz.
Logarithmische Zeit (bzw. Komplexität) bedeutet, dass die Rechenzeit zur Durchführung eines Algorithmus nach einer logarithmischen Funktion bei Vergrößerung der Eingabedatenlänge bzw. -menge zunimmt.
Ich hoffe, mit diesen Ausführungen helfen zu können.
P.S. Ich wollte eigentlich als Dritter vor wenigen Minuten posten :cool:, aber es wurde eine Viertelstunde...;) :eek:
Mit freundlichen Grüßen
TheoChem
die Fakultät ist n! = 1 * 2 * 3* ... * n (Produkt aller ganzen Zahlen von 1 bis n), wobei n >= 1 und ganz.
Logarithmische Zeit (bzw. Komplexität) bedeutet, dass die Rechenzeit zur Durchführung eines Algorithmus nach einer logarithmischen Funktion bei Vergrößerung der Eingabedatenlänge bzw. -menge zunimmt.
Ich hoffe, mit diesen Ausführungen helfen zu können.
P.S. Ich wollte eigentlich als Dritter vor wenigen Minuten posten :cool:, aber es wurde eine Viertelstunde...;) :eek:
Mit freundlichen Grüßen
TheoChem
buba
27.09.2003, 21:25
Originalnachricht erstellt von TheoChem
Hallo,
die Fakultät ist n! = 1 * 2 * 3* ... * n (Produkt aller ganzen Zahlen von 1 bis n), wobei n >= 1 und ganz.
0! = 1 (per definitionem)
Für ungerade n gibt es Näherungen, z.B. die Gamma-Funktion.
Hallo,
die Fakultät ist n! = 1 * 2 * 3* ... * n (Produkt aller ganzen Zahlen von 1 bis n), wobei n >= 1 und ganz.
0! = 1 (per definitionem)
Für ungerade n gibt es Näherungen, z.B. die Gamma-Funktion.
upsidedown
27.09.2003, 22:40
Originalnachricht erstellt von Lim_Dul
Damit kommt man aber auch nicht auf O(log n), da ich einfach n so groß machen kann, dass die Zwischenergebnisse irrelevant sind.
Das war auch ein praktischer, kein theoretischer EInwand ;)
Damit kommt man aber auch nicht auf O(log n), da ich einfach n so groß machen kann, dass die Zwischenergebnisse irrelevant sind.
Das war auch ein praktischer, kein theoretischer EInwand ;)
Marvek
27.09.2003, 23:15
Also ich glaub nicht, dass das geht - höchstens nur als Nährungen wie bereits gesagt.
nobody
28.09.2003, 00:16
Das wäre mit einer Revolution in der Mathematik gleichzusetzen und würde auch andere Bereiche positiv befruchten ...
Es gibt nur Näherungen, aber nix Exaktes.
Es gibt nur Näherungen, aber nix Exaktes.
BeniBela
28.09.2003, 18:44
Schade, trotztdem danke.