再帰関数解析

Question

私が書いた再帰的プログラムのパフォーマンスを分析しようとしています。

基本的なコードは、私は（）をコストに行われたコールの数の漸化式を書きたい

Cost(x) 
{ 
1 + MIN(Cost(x-1), Cost(x-2), Cost(x-3)) 
} 

です。どのように私はこれを始めるだろうか？

のようなものT(x) = T(x/2)。しかし、私はそれが正しいとは思わない

編集：これは、3回の再帰的な呼び出しであるCost（）に対する分岐係数が3のツリーとして表現できます。それでもっと正確にT(x) = T(x/3)になるでしょうか？

Answer 1

（コストのために行われたコールの数を考える

（私はその割り当てが線形反復と比較するために願っています）：？

だから、入力 xため、コストが（）を1回と呼ばれていたプラス倍の量は、それが x-1のために呼ばれた、

C(x) = 1 + C(x-1) + C(x-2) + C(x-3) 

10、およびx-3。これはあなたの解決策がメモを使用しないと仮定しています。あなただけ0とxの間のすべてのiに一度C(i)を評価する必要があるためしかし、あなたの「呼び出しの数は、」C(x) = xになり、メモ化を使用して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 + 1となる場合があります）

Answer 2

は、あなたは本当に再帰的なソリューションを書いたのだろう）私は

T(X) = T(X-1)+T(X-2)+T(X-3)+C 
C is small constant