4. Fakultät in logarithmischer Lauftzeit berechnen

Fakultät in logarithmischer Lauftzeit berechnen

  • W

    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?

    0
  • C

    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 ...

    0
  • G

    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.

    0

  • Du hast nicht zufällig einen Paralellrechner zur Verfügung? 😉

    0
  • K

    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.

    0
  • C

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

    danke ...

    0

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

    0
  • W

    TGGC schrieb:

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

    Klar, am Wochenende 🙄 😃 .

    0
  • V

    http://www.luschny.de/math/factorial/SrcJava/FactorialSimpleSwing.html

    0
  • C

    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 ...

    0

  • 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.

    0
  • V

    TGGC schrieb:

    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.

    korrekt. hat lineare. dabei sah das so schnell aus.
    ich überleg morgen den ganzen tag, aber ich fürchte, da find ich nix.

    @CBR-Racer: was habt ihr gerade an vorlesungsstoff dran? vielleicht gibt das uns nen tip.

    0
  • W

    Ich weiß nun nicht genau, wie die Laufzeit berechnet wird. Ich denke mal, dass es die Anzahl der Multiplikationen in Abh. von n sind. Dann habe ich auf jeden Fall einen Algo gefunden, der die Fakultät in O(n/2) ausrechnet (wenn man das Multiplizieren mit 2 nicht mitrechnet 🙄 ). Es ist ja z.B.

    8! = 5 * ((5-1)(5+1)) * ((5-2)(5+2)) * ((5-3)(5+3))
   = 5 * (25-1²) * (25-2²) * (25-3²)

    Mit q = (n/2 + 1) gilt allgemein

    n! = q * (q²-1²) * (q²-2²) * ... * (q²-(q-2)²)

    Setzen wir nun
    ak=q2−k2,a_k = q^2 - k^2,
    dann gilt
    ak+1=(q2−k2)−2k−1=ak−(2k+1).a_{k+1} = (q^2 - k^2) - 2k - 1 = a_k - (2k + 1).
    Wenn wir nun die Multiplikation mit 2 vernachlässigen, so können wir also ak+1 aus ak ohne Aufwand berechnen. Da nun
    n! = q \cdot a\_1 \cdot a\_2 \cdot \dots \cdot a_{q-2},
    haben wir
    q−2=n2+1−2=n2−1q-2 = \frac{n}{2} + 1 - 2 = \frac{n}{2} - 1
    Multiplikationen.

    EDIT: Bei ungeradem n kommt noch eine Multiplikation mit n dazu.

    0
  • S

    WebFritzi schrieb:

    Ich weiß nun nicht genau, wie die Laufzeit berechnet wird. Ich denke mal, dass es die Anzahl der Multiplikationen in Abh. von n sind. Dann habe ich auf jeden Fall einen Algo gefunden, der die Fakultät in O(n/2) ausrechnet (wenn man das Multiplizieren mit 2 nicht mitrechnet 🙄 ).

    Bin jetzt zu muede, die genaue Definition nachzuschlagen, aber auf jedenfall ist O(n/2) = O(n). Und damit sind wir wieder am Anfang.

    0
  • W

    SG1 schrieb:

    Bin jetzt zu muede, die genaue Definition nachzuschlagen, aber auf jedenfall ist O(n/2) = O(n). Und damit sind wir wieder am Anfang.

    Na jut, dann ist das wohl diese lineare Geschichte.
    O(n)={f:N→R∣∃a,b∈Rmitf(n)=an+b}O(n) = \{f: \mathbf{N}\to\mathbf{R}\,|\, \exists a,b\in\mathbf{R}\;mit\; f(n) = an + b\}

    0
  • G

    Ich weiß garnicht, warum hier jeder irgendwas kompliziertes berechnen will. Es ist vollkommen legitim und natürlich, bei einer Funktion, die nur für etwa 20 Werte sinnvolle Ergebnisse liefert, die Ergebnisse einfach direkt in den Quellcode zu schreiben. Schreib sie in ein Array, dann kriegst du O(1), wenn dir das zu schnell ist und du nichts schnelleres als O(log(n)) haben möchtest (wobei O(1) eigentlich in O(log(n)) liegt), dann schreib sie halt in nen Baum und such sie dir mit binärer Suche raus. 😉

    Oder sollt ihr die Funktion für einen Datentyp schreiben, der ein paar hundert Stellen lange Zahlen erlaubt?

    0
  • G

    WebFritzi schrieb:

    SG1 schrieb:

    Bin jetzt zu muede, die genaue Definition nachzuschlagen, aber auf jedenfall ist O(n/2) = O(n). Und damit sind wir wieder am Anfang.

    Na jut, dann ist das wohl diese lineare Geschichte.
    O(n)={f:N→R∣∃a,b∈Rmitf(n)=an+b}O(n) = \{f: \mathbf{N}\to\mathbf{R}\,|\, \exists a,b\in\mathbf{R}\;mit\; f(n) = an + b\}

    Deine Definition ist falsch. Die O-Notation ist wie folgt definiert:

    O(g(n)) = {f:N->R | Es gibt ein c aus R+ und es gibt ein n0 aus N, so dass für alle n >= n0 gilt: |f(n)| <= c|g(n)|}

    0
  • W

    Na gut. Ist ja so ähnlich. Also
    O(n)={f:N→R∣∃a,b∈R+mit∣f(n)∣≤an+b}O(n) = \{f: \mathbf{N}\to\mathbf{R}\,|\, \exists a,b\in\mathbf{R}^+\;mit\; |f(n)| \le an + b\}

    0
  • C

    also vom Thema kommt man leider auch nicht auf die Lösung, weil Thema ist ganz einfach Einführung in C ... und da ich da schon mal nen Vorlesung drüber hatte, kriege ich jetzt regelmäßig schwierigere Aufgaben ... die anderen müssen das ganze nur rekursiv programmieren ... echt schwer 😡 ... naja was solls ...

    @ Gregor ... nein nichts mit Datentyp oder so, aber ich denke, das ist auch nicht der Trick, den der prof meinte ... wenn es überhaupt einen Trick gibt ...vielleicht soll ich ja auch einfach nur drauf kommen, daß es so einen Algorithmus gar nicht gibt ... 😕

    @ WebFritzi ... das ist leider auch wieder linear, aber sah echt interessant aus die Rechnung ... muss ich mri auf jedenfall merken ...

    0
  • ?

    Ich würde für alle n<=10 die Werte in eine Tabelle schreiben. Für n>10 kann man die Stirling-formel benutzen, aus der sich ergibt:

    ln(n!) ~ (n+1/2) * ln n - n + ln(2*PI)

    Für n>10 liefert das sehr genaue Werte und sollte in logarithmischer Zeit laufen ... denk ich ...

    Gruß

    0
Anmelden zum Antworten