現在の再発の複雑さを見つける必要があります。
T(n) = 1/(T(n-1) + 1) + 1
アイデアや有用な情報へのリンクを事前に感謝します
1 に答える
1
上記の私のコメントを拡張します...
これは、現実世界の反復関係としては意味がありません。 T(n)サイズの問題を解決するためのランタイムを示しますn。T(n-1)size のランタイムを示します(n-1)。(n-1)サイズの問題を解決する前にサイズの問題を解決する必要があることを考えると(それ以外の場合は再帰ではありません)、実行時間は増加するにつれて必然的に単調nでなければなりません。n
nただし、あなたの表現は;で上下に振動します。これは意味がありません。
この式が意味をなす唯一の方法は、T(n)が で一定であると仮定してn、振動がないようにすることです。これを可能にする定数値があることがわかり、 を設定するだけT(n) = T(n-1)で解決できます。(これも同様に無意味であることに注意してください。通常、 の絶対値については話しませんT(n)。)
于 2010-11-07T10:28:44.260 に答える