複数の引数を持つアルゴリズムからクローズドフォームを見つける

Question

function What(n,a,total) 
    if n=0 
     return total 
    elseif n is even and n>0 
     return What(n/2, a+1, total) 
    elseif n is odd 
     return What((n-1)/2, a+1, total + 2^n) 
    endif 
end What 

このアルゴリズムのクローズドフォームを見つける方法がわかりません。これは宿題の問題ではなく、私の今後の最終テストのための以前の試験を勉強するだけです。与えられたマーキング/スペースによれば、それは小さい/単純な解決策でなければならない。 0で

と仮定すると、総開始、

I nが2の累乗である場合、アルゴリズムは、2を返すことがわかります。 は、nが偶数の場合2 ^（n/2）+ 2を返します。 nが奇数の場合は2^n + 2です。

最初のelseifのT（n/2）+ 1時間が得られ、2番目のelseifのT（（n-1）/ 2）+ 2^n + 1（？

全体的に、ここでは閉じたフォームを見つける方法/繰り返しの置換を使用する方法についてはわかりません。

Answer 1

What()関数の複雑さは、それに渡される最初の項にのみ依存するように思えます。検査では、整数> 0 Nはこれを確認するために、実行中の時間がO(lg_2 N + 2)であることを確認することはかなり明白である、単に機能の数が2の最初のいくつかの整数倍を求めて検討してください：

num | # function calls 
2 |   3 = lg_2(2) + 2 
4 |   4 = lg_2(4) + 2 
8 |   5 = lg_2(8) + 2 
16 |   6 = lg_2(16) + 2 

具体的にWhat(n)を呼び出すたびにWhat(floor(n/2))が呼び出されます。つまり、nは再帰の線形ステップごとに半分に分割されます。