使用替换方法求解递归T（n）= T（n / 2）+ O（lg n）？

Question

您如何解决重复性T（n）= T（n / 2）+1是O（lgn）？考虑到T（1）= 1

Answer 1

使用Master定理可以轻松解决许多标准递归关系。它有三种情况。

您的递归关系打破情况＃2，a等于1，b等于2，f（n）等于1。

Answer 2

替换方法建议我们猜测解，然后通过归纳证明。

我们在这里猜测部分解：T（2 ^ k）= k + 1

• 基本情况：T（2 ^ 0）= T（1）= 1。
• k的归纳情况> 0：T（2 ^ k）= T（2 ^（k-1））+1 = k-1 + 1 +1 = k + 1

这使我们对于2的n次幂，T（n）= lg（n）+1。要将其扩展为一个完整的解，令n'为2的最小幂，大于或等于n（对于任意n > 0）。那么T（n）<= T（n'）= lg（n'）+1。由于n'<2n，我们有lg（n'）

因此我们证明了T（n）= O（lg（n））。

Answer 3

它是O(log₂(n))：

                    __
T(n)   = T(n/2) + 1   |
T(n/2) = T(n/4) + 1   | 
T(n/4) = T(n/8) + 1   |-- k operations
...                   |
T(1)   =          1 __|

n/2^k = 1  =>  n = 2^k  =>  k = log₂(n)   (by definition of log₂).