Fakultät in logarithmischer Lauftzeit berechnen
-
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
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
-
Ich verstehe nicht einmal die Aufgabenstellung. Kannst Du etwas genauer formulieren?
-
n! berechnen in zeit O(log n)
keine Ahnung wie ich das anders erklären soll ...
-
Also die Fakultät in logarithmischer Laufzeit berechnen kannst du indem du sie rekursiv implementierst.
-
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.
-
Siehe auch: http://www.volkard.de/vcppkold/rekursion.html
-
also danke erstmal für eure Antworten ... allerdings sehe ich das etwas anders ...
-
ich hatte es rekursiv programmiert ... und dann kam die Aufgabe, es halt in logarithmischer Laufzeit zu programmieren
-
würde ich behaupten, rekursiv programmiert ist es dann
logarithmisch zu n! aber nicht zu n
-
-
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.
-
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
-
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.
-
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?
-
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 ...
-
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.
-
Du hast nicht zufällig einen Paralellrechner zur Verfügung?
-
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.
-
Die Idee ist nicht schlecht ... aber denke auch, daß ist nicht die gesuchte Lösung ... werde es aber spasseshalber mal programmieren ...
danke ...
-
Und, hat dein Prof mal gesagt, wie der Trick sein soll?
-
TGGC schrieb:
Und, hat dein Prof mal gesagt, wie der Trick sein soll?
Klar, am Wochenende
.
-
-
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 ...
-
volkard schrieb:
http://www.luschny.de/math/factorial/SrcJava/FactorialSimpleSwing.html
Wie kann das logarithmische Laufzeit haben? Das for in swing() läuft doch mit O(n), weil die Schleife n Schritte macht. Zwar nicht auf einmal, aber insgesamt schon, da m ja nur im Schleifenkopf geändert wird.
