la résolution de récurrence [fermée]

Question

Je dois trouver la complexité de la récurrence actuelle:

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

Merci d'avance pour toute idée ou d'un lien avec des informations utiles

Answer 1

Développant mes commentaires ci-dessus ...

Cela n'a pas de sens comme une relation de récurrence dans le monde réel. T(n) désigne le temps d'exécution pour résoudre un problème de taille n; T(n-1) indique le temps d'exécution pour la taille (n-1). Étant donné que vous devez résoudre le problème de la taille (n-1) avant de pouvoir résoudre la taille n (sinon il ne serait pas une récursion), le moteur d'exécution doit nécessairement être monotone avec l'augmentation de n.

Cependant, votre expression et vers le bas oscille avec n; cela n'a pas de sens.

La seule façon cette expression pourrait jamais donner un sens est si nous supposons que T(n) est constante avec n, de sorte qu'il n'y a pas d'oscillation. Il se trouve qu'il ya une valeur constante qui permet que cela se produise, tout ensemble T(n) = T(n-1) et résoudre. (Notez que cela est tout aussi dénuée de sens, on ne parle. Généralement pas absolu valeurs de T(n))