使用递归关系分析时间复杂度

Question

使用递归关系分析时间复杂度

algorithmrecursiontime-complexitycomplexity-theoryrecurrence

4

我是一名复杂度分析新手。

我正在尝试使用下面给出的递归公式来计算递归算法的时间复杂度 -

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

我知道有三种方法可以解决这个问题，但我尝试通过计算每个层级的工作量之和来解决它。

当我绘制递归树时，结构如下：

                        n                          | n work
                     /     \
              4T(n/2)        4T(n/2)               | 2n work
             /     \         /        \
         4T(n/2)   4T(n/2)   4T(n/2)  4T(n/2)      | 4n work

          .          .          .       .
          .          .          .       .
     Theta(1) Theta(1) Theta(1).......Theta(1)     | ???

我在计算总和(n + 2n + 4n + 8n ...)时遇到了困难，因为：

我无法弄清最后一项。
即使我能找出最后一项，我也意识到这是一个公比r>1的等比数列，所以我无法真正计算总和。

请问有人可以帮我理解如何解决这个问题吗？编辑：注意：我在这里找到了这个问题 - http://fileadmin.cs.lth.se/cs/Personal/Rolf_Karlsson/lect1.pdf，其中提供了一个解决方案，但我并没有完全理解它，而且我的表达式至少是正确的，但我不知道如何得出最后一项。

- Raaj

你好，我正在学习这些概念，稍后会回来看看哪个更有意义。我明白这两个答案在说什么，但我还没有完全理解其中的细节。我一定会点赞并接受答案的，放心 :) - Raaj

每个问题会生成4个子问题，但在您的递归树中，每个问题只绘制2个子问题（每个节点2个孩子）。
一个节点应该是“未展开”（形式为“T（...）”），这种情况下它没有子节点（对应于等式的左侧），或者是“已展开”（形式为“c * ...”），这种情况下它应该有4个子节点（对应于等式的右侧）。
此外，第三行应将每个“n/2”的出现替换为“n/4”。

- j_random_hacker

2个回答

0

从根到叶，树的每一层都看到n个半，因此树有log2(n)层。

总和将会是：

n + 2n + ... + 2 ^ (log2(n)) * n
= n * (1 + 2 + ... + 2 ^ log2(n))
= n * (2 ^ (log2(n) + 1) - 1)
= n * (2 * n - 1)
= 2 * n ^ 2 - n
= O(n ^ 2)

以上所有分析都假设n是2的幂，但在大多数情况下，这种假设并不重要。

- zw324

你也可以对此进行更紧密的限制，例如θ(n^2)。不过请检查我的答案，因为它始终将O(n^2)作为上限。 - Am_I_Helpful

1

@shekharsuman 这已经是Theta(n^2)了，但我没有注意到。但当然，你进行了更仔细的分析，这适用于所有情况 :-) - zw324

@ZiyaoWei- 这就是为什么我在你的评论部分提到，这样你如果愿意就可以编辑你的回答。那我会点赞的。 - Am_I_Helpful

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Am_I_Helpful · Accepted Answer

对于元素a，ar，ar² ... arⁿ⁻¹的等比数列求和公式如下：

S(n) = a((r^n)-1)/(r-1)  // in case of r>1

节点深度为i时的子问题大小为n/(2^i)。因此，当n/(2^i)=1时，子问题的大小为1，或等价地，i=log₂n。

每个层级的节点数比上一层级多4倍，因此深度为i的节点数为4^i。

因为从根节点往下走每个层级子问题的大小都减少了一半，所以对于i=0,1,2,...,log₂n-1的节点来说，其成本为c*n/(2^i)。将它们相乘，我们可以看到对于i=0,1,...,log₂n-1的所有节点，总成本为4^i * c * n/(2^i)=(2^i)*c*n。

深度为log₂n的最后一层有4^(log₂n)=n^(log₂4)=(n^2)个元素，每个元素的成本为T(1)，即θ(n^2)。

在所有层面上累加成本，

T(n) = cn + 2cn + 4cn + ... + cn*(2^log₂n-1) + θ(n^2)

 = cn*[(2^log<sub>2</sub>n)-1]/(2-1) + θ(n^2)

 = cn*[(n^log<sub>2</sub>2)-1] + θ(n^2)

 = cn*(n-1)+ θ(n^2)

 = cn^2 - cn + θ(n^2)

 = θ(n^2).    // OR    O(n^2) for an upper bound.

因此，您的递归树的复杂度为 θ(n^2)。您可以很好地认为它的复杂度是 O(n^2)。