recursion - mastersメソッドが適用されない再発

Question

次のように定義された再発があるとしますT(n) = T(n/2) +1。マスターの方法なしでこれをどのように評価しますか？私がこれまでに持っているもの：

T（n）= T（n / 2）+ 1 T（n / 2）= T（n / 4）+ 1 T（n / 4）= T（n / 8）+ 1 ... T（1） = 1

これはO（logn）のようです。これは、マスターの定理が発生しないこれらの問題を解決する唯一の方法ですか？

Answer 1

どうやってこれを手に入れたのT(1) = 1ですか？
どれどれ：

T(0) = T(0/2) + 1 => 0 = 1!

したがって、T(x)関数には に漸近線がありx=0ます。
次のように再定義できることに注意してください。

T(2^(x+1)) = T(2^x) + 1 
=> 
f(x+1) = f(x) + 1 
=> 
f(x) = x + a
=>
T(n) = Log2(n) + a(n)

ここa(n)で、区間の長さが 1 の関数