algorithm - 如何解决这个递归关系：T(n) = 2T(n/2) + 1

Question

我在这种重复关系上遇到了麻烦。

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

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

Answer 1

Let's assume for simplicity that n is a power of 2. For example, if n = 8 and the base case T(0) = 0 then the tree of recursive call looks like that:

                       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

The tree has log(n) + 1 levels not counting the lowest level, because each node in this level has cost 0. In order to calculate T(n), in this case T(8), you have to sum up all ones in the tree.

Notice that on the depth i there are 2^i nodes, each with cost equal 1.

So the formula for a sum of ones in the tree is:

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

this is a geometric series with a_1 = 1 and q = 2, and you want to know the sum of first log(n) + 1 values. This is given by the formula:

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

So for n = 8, the result is 15.

I hope this helps you.

Answer 2

Cormen 等人的“算法简介”中对这种关系进行了很好的解释。那本书中的主定理 4.1 处理了 T(n) = aT(n/b) + f(n) 形式的所有循环关系。对于 f、a 和 b 的各种组合。该定理中的一种情况，即情况 2。可以应用于您的示例，给出 O(n) 估计。因此，要回答您的问题，您不能仅仅在执行一些常规计算以渐近结束的意义上解决这种关系，而是您观察到您的情况属于存在估计的一类关系。

Answer 3

这种类型的递归是使用Master theorem解决的。

在你的情况下a = 2，b = 2和f(n) = 1。所以c = log2(2) = 1and O(n^1) > O(1)，这意味着我们属于第三种情况，因此复杂性是O(n)。