復發解決

Question

我需要找到當前復發的複雜性：

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

先感謝您的任何想法或鏈接有用的信息

Answer 1

擴展在上面我的意見......

這與現實世界的重複關係無關。 T(n)表示解決尺寸爲n的問題的運行時間; T(n-1)表示大小爲(n-1)的運行時間。鑑於在解決大小n（否則它不會是遞歸）之前，您必須解決大小爲(n-1)的問題，運行時必須爲monotonic，因爲n增加。

但是，您的表情隨着n上下襬動;這沒有意義。

這個表達式唯一有意義的方法是如果我們假設T(n)與n是一致的，這樣就沒有振盪。事實證明，有一個不變的價值，允許這發生，只需設置T(n) = T(n-1)，並解決。 （請注意，這同樣毫無意義;我們通常不會談論絕對值的值T(n)。）