recursion - 主方法不适用的重复

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 的函数

Answer 2

是什么让您认为主方法不适用？我们有：

T(n) = a T(n/b) + f(n)

和

a = 1, b = 2, f(n) = 1

我们可以看到

c = log_b a = log_2 1 = 0
f(n) = 1 = Theta(1) = Theta(n^0 log^0 n) = Theta(n^c log^k n)

所以我们可以使用结果

T(n) = Theta(n^c log^(k+1) n) = Theta(n^0 log^(0+1) n) = Theta(log n)

这是你的结果。