質問

現在の再発の複雑さを見つける必要があります。

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

有用な情報とのアイデアやリンクを前もってありがとう

役に立ちましたか？

解決

上記の私のコメントを展開しています...

これは、実際の再発関係として意味がありません。 T(n) サイズの問題を解決するためのランタイムを示します n; T(n-1) サイズのランタイムを示します (n-1). 。サイズの問題を解決する必要があることを考えると (n-1) サイズを解く前に n （そうでなければ再帰ではないでしょう）、ランタイムは必ずしも 単調 なので n 増加します。

ただし、あなたの表現は上下に振動します n;これは意味がありません。

この表現が理にかなっている唯一の方法は、私たちがそれを想定している場合です T(n) で一定です n, 、振動がないように。これが起こることを可能にする一定の値があることがわかります。 T(n) = T(n-1), 、そして解決します。 （これは同様に意味がないことに注意してください。私たちは一般的には話しません 絶対 の値 T(n).)

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top