Wiederholung Lösung [geschlossen]

Question

Ich brauche die Komplexität der aktuellen Wiederholung zu finden:

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

Vielen Dank im Voraus für jede Idee oder einen Link mit nützlichen Informationen

Answer 1

Die Erweiterung auf meine Ausführungen oben ...

Das macht keinen Sinn, als reale Wiederholung Beziehung machen. T(n) bezeichnet die Laufzeit ein Problem der Größe n zu lösen; T(n-1) bezeichnet die Laufzeit für die Größe (n-1). Vorausgesetzt, dass Sie das Problem für Größe (n-1) lösen müssen, bevor Sie für die Größe n lösen kann (sonst wäre es nicht eine Rekursion sein), muss die Laufzeit sein muss, monotoner als n erhöht.

Allerdings schwingt Ihr Ausdruck nach oben und unten mit n; dies macht keinen Sinn.

Der einzige Weg, dieser Ausdruck könnte immer sinnvoll ist, wenn wir die T(n) konstant mit n übernehmen, so dass es keine Schwingung ist. Es stellt sich heraus, dass es einen konstanten Wert ist, der dies nur Satz T(n) = T(n-1) passieren können, und lösen. (Beachten Sie, dass dies ist ebenso sinnlos,. Wir im Allgemeinen nicht darüber reden, absolute Werte von T(n))