复发解决[关闭

Question

我需要找到当前复发的复杂性：

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

先前感谢您的任何想法或链接有用的信息

Answer 1

扩展我上面的评论...

作为现实世界复发的关系，这是没有意义的。 T(n) 表示解决大小问题的运行时间 n; T(n-1) 表示大小的运行时间 (n-1). 。鉴于您必须解决大小的问题 (n-1) 在解决尺寸之前 n （否则它不会是递归），运行时必须是 单调 作为 n 增加。

但是，您的表达与 n;这没有道理。

这种表达方式唯一有意义的方法是，如果我们假设 T(n) 不变 n, ，因此没有振荡。事实证明，有一个恒定值可以发生这种情况，只是设置 T(n) = T(n-1), 和解决。 （请注意，这同样毫无意义；我们通常不会谈论 绝对 值 T(n).)