如何求解这个递推关系：T(n) = 2T(n/2) + 1

Question

我在这种递归关系上遇到了麻烦。

T(n) = 2T(n/2) + 1

谁能帮我解释一下如何解决这个问题以获得答案O(n)？

Answer 1

为了简单起见，我们假设它n是 2 的幂。例如，ifn = 8和 then 的基本情况T(0) = 0，递归调用树如下所示：

                       1                                n = 8, depth 0
                      / \
                     /   \
                    /     \
                   /       \
                  /         \
                 /           \
                /             \
               /               \
              /                 \
             /                   \
            /                     \
           1                       1                    n = 4, depth 1
          / \                     / \
         /   \                   /   \
        /     \                 /     \
       /       \               /       \
      /         \             /         \
     1           1           1           1              n = 2, depth 2
    / \         / \         / \         / \
   /   \       /   \       /   \       /   \
  1     1     1     1     1     1     1     1           n = 1, depth 3
 / \   / \   / \   / \   / \   / \   / \   / \
0   0 0   0 0   0 0   0 0   0 0   0 0   0 0   0         n = 0, depth 4

该树的log(n) + 1级别不包括最低级别，因为该级别中的每个节点都有成本0。T(n)在这种情况下，为了计算T(8)，您必须将树中的所有值相加。

请注意，在深度上i存在2^i节点，每个节点的成本等于1。

所以树中的总和的公式是：

sum [from i = 0 to log(n)] 2^i

a_1 = 1这是一个包含和的几何级数q = 2，您想知道第一个值的总和log(n) + 1。这由以下公式给出：

(1 - 2^(log(n) + 1)) / (1 - 2) = 2n - 1

所以对于n = 8，结果是15。

我希望这可以帮助你。