如何解决此递归关系：T（n）= 2T（n / 2）+1 [英] How to solve this recurrence relation: T(n) = 2T(n/2) + 1

问题描述

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

I am having trouble with this recurrence relation.

T（n）= 2T（n / 2）+ 1

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

任何人都可以帮助我解释如何解决该问题以获得 O（n）？

Can anyone help me in explaining how one would go about solving this to get to the answer of O(n)?

推荐答案

为了简单起见，我们假设 n 是2的幂。例如，如果 n = 8 并且基本情况 T（0）= 0 那么递归调用树如下所示：

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

树具有 log（n）+ 1 个级别，不计入最低级别，因为该级别中的每个节点的成本均 0 。为了计算 T（n），在这种情况下为 T（8），您必须将所有这些加起来在树上。

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.

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

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 [从i = 0到log（n）] 2 ^ i

这是一个几何序列，其中 a_1 = 1 和 q = 2 ，并且您想知道前 log（n）+ 1 个值的总和。这由以下公式给出：

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

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

希望对您有所帮助。

这篇关于如何解决此递归关系：T（n）= 2T（n / 2）+1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！