O-Notation: Fakultät

[Cherrycoke]

Hallo Community,

ich mache mir mein Leben noch etwas mit der O-Notation schwer. Vielleicht könnt ihr mir ja kurz weiterhelfen?

Ich habe folgenden Algorithmus fakultaet( n ) gegeben:

Eingabe: n ist eine natürliche Zahl

Ausgabe: n! = 1 * 2 * ... mit 0! := 1


wenn n = 0

    fak = 1

sonst

    fak = fakultaet( n-1 ) * n

fakultaet = fak

Nun möchte ich hierzu die Zeitkomplexität bestimmen. Folgendes habe ich mir dazu gedacht:

Innerhalb einer If-Abfrage interessiert mich nur der "Teil", der Zeitintensiver ist, also in diesem Fall fak = fakultaet( n-1 ) * n.

Doch hier weiß ich schon nicht mehr, wie ich den Zeitaufwand dieser Zeile bestimme.

Könnte mir das jemand vielleicht kurz erklären?

Vielen Dank!

[flashpixx]

Also generell ist die Landausymbolik eine Schrankentheorie, d.h. Du möchtest ermitteln wie lange ein Algorithmus im worst-case laufen wird. Das ganze zeigt man formal mit einem Induktionsbeweis.

Letztendlich musst Du jede Operation die Du durchführst bewerten, d.h. z.B. nimmt man für Zuweisungen die Zeit "1" und summiert das eben über den ganzen Code auf. Für die Rekursion musst Du eben in der Rekursion absteigen und eben das ganze so lange machen, bis die Rekursion abbricht und dann die Zeit entsprechend aufsummieren

[Cherrycoke]

Leider war Theorie noch nie so wirklich meine Stärke. Zur O-Notation habe ich schon einige Texte gelesen, allerdings scheitert es bei mir an der praktischen Anwendung.

Also kann man für mein Beispiel sagen:

T(0) = O(1) + O(1)

Da bei der 0 als Eingabe Eine Zuweisung in der zweiten Zeile und eine Zuweisung in der fünften Zeile stattfindet?

Aber was wäre dann T(1)?

Da das Ganze rekursiv abläuft, müsste T(1) irgendwas + T(0) sein, also:

T(1) = x + T(0)

Aber ich verstehe nicht ganz, was die Zeile

fak = fakultaet( n-1 ) * n

für einen Zeitaufwand hat.

Kann mir hier nochmal wer auf die Sprünge helfen?

[flashpixx]

Also der Ansatz ist schon so richtig, Du bist bei dem Schritt "n" und nun gehst Du in die Rekusion, d.h. zum Schritt n-1 und da wieder zu n-2 ....

Wie so eine Art Schleife, der Abbruch findet dann bei n==0 statt (obwohl Du Dir hier noch eine Rekursion sparen könntest, da mathematisch gilt fak(1) == fak(0) == 1)

D.h. Du gehst n mal in die Rekursion denn n-n=0 erfüllt ja Deine Abbruchbedingung. Als Tipp, schreib die Fakultät einmal als iterative Form und berechne da die Komplexität und wenn Du das hast, mach es mit Rekursion

[lupo49]

EDIT: flashpixx war schneller.

[Cherrycoke]

Als Tipp, schreib die Fakultät einmal als iterative Form und berechne da die Komplexität und wenn Du das hast, mach es mit Rekursion

Hmm, da beginnt es ja schon bei mir. *peinlich* Wie berechne ich denn die Komplexität der Fakultät in iterativer Form?

Folgendes wäre ja iterativ, oder?

1! = 1

2! = 1 * 2

3! = 1 * 2 * 3

Ich habe wirklich keine Idee, wie ich denn nun die Komplexität berechne...

Okay, da bei 1 nichts berechnet werden muss, würde ich für n = 1 sagen 0(1) = 1.

Aber was wäre die Komplexität von n = 2?

[flashpixx]

Hmm, da beginnt es ja schon bei mir. *peinlich* Wie berechne ich denn die Komplexität der Fakultät in iterativer Form?

Der Code für die Fakultät wäre wohl so:

int fakultaet(int p) {

   int f=1;

   for(int i=1; i<=p; ++i)

         f = f*i;

   return f;

}

[/PHP]

Überlege Dir doch jetzt einfach was diese Routine an Zeit "kostet" für ein beliebiges p. Wenn Du dann die worst-case Abschätzung haben willst würde man das p im Limes gegen unendlich laufen lassen.

[Cherrycoke]

Hier sind meine Gedanken:

Die Schleife wird p-mal durchlaufen.

Vor der Schleife steht eine Zuweisung, also würde ich hier sagen 1*O(1).

Für die Schleife selbst muss p-mal überprüft werden ob i <= p ist, was ein Aufwand von O(1) ist.

Dann findet noch eine Zuweisung statt (i++) was auch p * O(1) entspricht.

Was hätte denn f = f* i für einen Aufwand?

Bisher hätte ich also 1 * O(1) + p * ( O(1) + O (1) + x).

Da mich ja nur eine obere Schranke interessiert hätte ich dann p*(O(1) + x)? (x ist der Teil f = f * i, da ich nciht weiß, wie man diesen Aufwand berechnet)

[flashpixx]

Vor der Schleife steht eine Zuweisung, also würde ich hier sagen 1*O(1).

Für die Schleife selbst muss p-mal überprüft werden ob i <= p ist, was ein Aufwand von O(1) ist.

Nein, das ist nicht O(1). Wie oft muss die Booleanbedingung überprüft werden?

Dann findet noch eine Zuweisung statt (i++) was auch p * O(1) entspricht.

das ist okay

Was hätte denn f = f* i für einen Aufwand?

Was ist das, das ist eine Multiplikation und eine Zuweisung.

Im einfachsten Fall schätzt man die Schranken ab, d.h. eine exakte Berechnung wird, wenn Du nicht den Maschinencode analysierst und die CPU Optimierung beachtest eh nicht möglich sein. Du betrachtest sowieso im Limes die Schranke, wobei es da nicht auf +1 oder selbst einen linearen Faktor kaum ankommt. D.h. schätze Deine Anweisungen sinnvoll ab, stelle die Summe auf und gehe in die Limesbetrachtung. Ob man im lim n -> inf (n+1) oder n hat, spielt dabei keine Rolle.

[Cherrycoke]

Nein, das ist nicht O(1). Wie oft muss die Booleanbedingung überprüft werden?

Wenn ich noch einmal genauer darüber nachdenke, muss die Bedingung p+1-mal überprüft werden.

Aber was wäre dann die Komplexität? Ich bin jetzt total verwirrt!

Wäre die Komplexität dann O(p+1)?

Was ist das, das ist eine Multiplikation und eine Zuweisung.

Naja, genau das weiß ich ja nicht. Aber ich würde jetzt mal sagen O(1), da es eine Basisoperation ist, die nicht auf die Eingabegröße zugreifen muss.

[flashpixx]

Mach Dir doch bitte mal ganz einfach Beispiele:

i=0;

wäre ein "c", d.h. ein Konstanterfaktor, meistens nimmt für eine einfache Zuweisung eine 1

i++;

wäre anders ausgedrückt

i=i+1;

d.h. ein Addition und eine Zuweisung, d.h. 2. Natürlich kann man sich darüber streiten ob eine Multiplikation nicht mehr Zeit in Anspruch nimmt als eine Addition, aber bei der Abschätzung macht man später einen Limesübergang, wobei lineare Faktoren völlig hinfällig wären, denn ein O(cn) bzw c*O(n) ist immer noch linearkomplex, ob man da nun noch einen skalaren Faktor hat oder nicht, ist egal. Letztendlich musst Du in der Abschätzung - und nur das ist relevant - unterscheiden, ob Du lineare, quadratische oder exponentielle Laufzeiten für Deine Anweisungen hast, denn diese sind relevant, zeitlich konstante Anweisungen spielen keine Rolle im Limes.

for(int i=0; i < p; ++i)

spielt es keine Rolle ob nun das ++i einen Aufwand von 1, 2, oder 10 hat, weil es als Skalar eingeht: O(1*p) ~ O(10*p) ~ O(100*p) ist immer noch O(c*p), d.h linearkomplex im Limes

[Cherrycoke]

Wenn ich dir jetzt richtig folgen konnte, bedeutet das, dass die iterative Fakultätfunktion eine Komplexität von O(n) hat. Habe ich das richtig verstanden?

Rekursiv wäre es n*O(n), wobei n eine Konstante ist, und ich dann auch O(n) erhalte?

Da muss doch ein Fehler drin sein - sonst würde das ja bedeuten, dass sowohl die iterative Variante, als auch die rekursive Variante die gleiche Laufzeit hätten? *verwirrt sei*

[flashpixx]

Rekursiv wäre es n*O(n), wobei n eine Konstante ist, und ich dann auch O(n) erhalte?

Nein, das ist falsch, bitte schlag die Gesetze für die Landau Symbole nach (http://de.wikipedia.org/wiki/Landau-Symbole). Die iterative Variante ist O(n), d.h. lineare Komplexität.