Решение рецидивов [закрыто

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).)