c++.de :: Fakultät in logarithmischer Lauftzeit berechnen

Walli Mitglied 23:02:18 05.12.2003 Titel:

Aber dadurch wird es vielleicht schneller, aber nicht logarithmisch... Ich bin immer noch der Meinung, dass die logarithmische Version O(log n) nicht möglich ist. O(n log(n)) dürfte doch die rekursive sein, oder?

CBR-Racer Mitglied 23:08:31 05.12.2003 Titel:

also wie gesagt, mein erster Gedanke war auch,das geht nicht ... aber sicher bin ich mir nicht ... habe jetzt ne Woche Zeit, herauszufinden, ob oder ob nicht ...

kann dir zu deinen letzen Ausführungen nur zustimmen ...

mal sehen, was ich noch so in den nächsten Tagen rausfinde zu dem Prob ...

Gregor Moderator 06:21:50 06.12.2003 Titel:

Ich würde alle Werte vorher berechnen und in eine Tabelle stecken. Das sind ja nicht so viele, weil der Wertebereich einer 32-Bit oder auch 64-Bit Ganzzahl einfach nicht so viel hergibt. Du hast dann zur Laufzeit O(1), was auch O(log(n)) ist, wenn du dir die Definition der O-Notation mal anschaust.

TGGC Mitglied 12:50:11 06.12.2003 Titel:

Du hast nicht zufällig einen Paralellrechner zur Verfügung? ;)

Klingelmann Mitglied 15:25:50 06.12.2003 Titel:

Du könntest vieleicht die Primfaktorzerlegung berechnen und die dann ausmultiplizieren. Für die Fakultät geht die Primfaktorzerlegung relativ schnell. Fragt sicht nur ob relativ schnell schnell genug ist... Ich vermute mal eher nicht.

CBR-Racer Mitglied 16:41:34 06.12.2003 Titel:

Die Idee ist nicht schlecht ... aber denke auch, daß ist nicht die gesuchte Lösung ... werde es aber spasseshalber mal programmieren ...

danke ...

TGGC Mitglied 16:13:57 07.12.2003 Titel:

Und, hat dein Prof mal gesagt, wie der Trick sein soll?

Walli Mitglied 18:22:54 07.12.2003 Titel:

TGGC schrieb:

Und, hat dein Prof mal gesagt, wie der Trick sein soll?

Klar, am Wochenende :rolleyes:

.

volkard Moderator 19:40:46 07.12.2003 Titel:

http://www.luschny.de/mat ....... FactorialSimpleSwing.html

CBR-Racer Mitglied 19:41:23 07.12.2003 Titel:

also sehe meinen Prof wirklich nur sehr selten am We

... aber werde es, wenn dann auch erst nächste Woche Freitag erfahren ... bis dahin habe ich Zeit ... und es wäre absolut genial, wenn ich das irgendwie hinkriegen würde ...