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

CBR-Racer Mitglied 20:27:17 05.12.2003 Titel:

Hallo Leute ...
ist mein erster Beitrag und dann gleich sowas kompliziertes ... also als ich diese Aufgabe gestellt gekriegt habe, war meine erster Gedanke, das geht gar nicht :rolleyes:

aber mein Prof sagte, mit einem Trick würde man das hinbekommen ... allerdings muss ich gestehen, den Trick habe ich noch nicht gefunden ...

kann mir von euch jemand nen Tip geben ??

danke schon mal im voraus

benutzername Mitglied 20:30:26 05.12.2003 Titel:

Ich verstehe nicht einmal die Aufgabenstellung. Kannst Du etwas genauer formulieren?

CBR-Racer Mitglied 20:55:58 05.12.2003 Titel:

n! berechnen in zeit O(log n)

:confused:

keine Ahnung wie ich das anders erklären soll ...

Walli Mitglied 20:58:05 05.12.2003 Titel:

Also die Fakultät in logarithmischer Laufzeit berechnen kannst du indem du sie rekursiv implementierst.

Griffin Mitglied 20:58:52 05.12.2003 Titel:

du willst den algorithmus für die fakultät der eine logarithmische laufzeit hat, oder?!
rekursion! die rekursive definition findest du echt in jeden tafelwerk.

Walli Mitglied 21:02:48 05.12.2003 Titel:

Siehe auch: http://www.volkard.de/vcppkold/rekursion.html

CBR-Racer Mitglied 21:11:35 05.12.2003 Titel:

also danke erstmal für eure Antworten ... allerdings sehe ich das etwas anders ...
1) ich hatte es rekursiv programmiert ... und dann kam die Aufgabe, es halt in logarithmischer Laufzeit zu programmieren

2) würde ich behaupten, rekursiv programmiert ist es dann :rolleyes:

logarithmisch zu n! aber nicht zu n

Walli Mitglied 22:12:03 05.12.2003 Titel:

Eine weitere Möglichkeit wäre die iterative. Die hat aber die Laufzeit O(n). Langsam gehen mir aber die Ideen aus. Ich kenne kaum noch Methoden wie man es sonst machen soll.

CBR-Racer Mitglied 22:32:06 05.12.2003 Titel:

tja siehst du, genau das Problem habe ich auch ... also angeblich soll das gehen, halt mit einem Trick ... aber da ich zur Zeit echt keinen Plan habe, wie der Trick aussehen soll, habe ich einfahc mal diesen Beitrag hier geschrieben ...

vielleicht findet sich ja noch jemand, der eine Idee hat ...

aber danke

Walli Mitglied 22:54:50 05.12.2003 Titel:

Du könntest eine Lookup-Table lösung implementieren. Du codierst hart die Fakultäten für z.B. jeden 10. Integer ein, startest bei f[n % 10] aus deinem hartcodierten Array und machst von dort aus weiter. Dadurch kommst du je nach Höhe des n von der Laufzeit auf jeden Fall unter O(n) und O(log n). Der Nachteil ist, dass du die LUT immer an den Wertebereich des Ganzzahltyps anpassen musst.