自分が書いた再帰プログラムのパフォーマンスを分析しようとしています。
基本的なコードは
Cost(x)
{
1 + MIN(Cost(x-1), Cost(x-2), Cost(x-3))
}
Cost（）に対して行われた呼び出しの数の漸化式を記述したいと思います。どうやってこれを始めますか？
のようなものT(x) = T(x/2)。しかし、私はそれが正しくないと思います
編集：これを、Cost（）への3つの再帰呼び出しのそれぞれに対して分岐係数が3のツリーとして表すことができます。それで、それはより正確になりT(x) = T(x/3)ますか？
あなたは本当に再帰的な解決策を書きましたか?(線形反復と比較するための割り当てであることを願っています)
おもう
T(X) = T(X-1)+T(X-2)+T(X-3)+C
C is small constant
Cost() の呼び出し回数は次のようになります。
C(x) = 1 + C(x-1) + C(x-2) + C(x-3)
したがって、入力xの場合、Cost() は 1 回呼び出され、さらにx-1、x-2、およびで呼び出された回数になりx-3ます。これは、ソリューションがメモ化を使用しないことを前提としています。再帰関係はきれいではありません: http://www.wolframalpha.com/input/?i=T(x)+%3D+1+%2B+T(x-1)+%2B+T(x-2 )+%2B+T(x-3)
ただし、メモ化を使用すると、と の間で一度C(x) = xだけ評価する必要があるため、 「呼び出し回数」は になります。(初期条件によってはかもしれません)C(i)i0xC(x) = x + 1