Frage zu Beispiel mit der O-Notation

[buzz_lightzyear]

Hallo,

ich habe folgendes Beispiel vor mir liegen; es geht um die rekursive Berechnung der Fakultät:

FAKULTAET_REKURSIV(n)

1: IF n= 1 THEN

2:      RETURN 1

3: ELSE

4:      RETURN(n*FAKULTAET_REKURSIV(n-1))

Soweit alles klar :-)

Dann gehts zur Rekursionsgleichung:

T(n) = O(1) + T(n-1)

O(1): konstante Zeit, die die Zeilen 1-3 benötigen

T(n-1): Laufzeit um eins verringert, da die Funktion ja mit (n-1) aufgerufen wird

-> auch noch klar :-)

Dann wird die Rekursionsgleichung gelöst und eine allgemeine Formel hergeleitet:

k*O(1) + T(n-k)

-> ja, das ist auch noch klar! :-)

Aber jetzt kommt das Problem:

Man will eine Lösung unabhängig von k. In dem Beispiel vor mir hab ich nun:

"Mit T(1) = T(n-k) bekommt man n-k = 1 => k = n - 1 und setzt das in die obige allgemeine Formel ein."

Warum setzt man hier T(1) = T(n-k)?? das ist ja mMn nicht das Gleiche?!?

Kann mir vllt jemand erklären warum das so ist?

Thx & Lg

buzzzzzz

 

 

Bearbeitet 3. Mai 2017 von buzz_lightzyear

[arlegermi]

Deine Methode ist doch einfach O(n), oder übersehe ich da was?

Deine Rekursion ist im Grunde nichts anderes als eine for (1 .. n) - Schleife.

(Für O(n) nehme ich natürlich an, dass Multiplikation tatsächlich O(1) ist, was man zumindest diskutieren kann)

Bearbeitet 3. Mai 2017 von arlegermi

[buzz_lightzyear]

Hallo,

danke für deine Antwort, ja es ist O(n). Trotzdem weiß ich eben nicht, wo das  T(1) = T(n-k) herkommt... Unser Prof. nimmt das eben immer als so einfach an, dass sowas nicht erwähnt werden muss. -.-

Thx & Lg