求 T（n） = 2T（n/2） + Logn 的时间复杂度-解网

问：

T（n） = 2T（n/2） + 日志

这是给定的时间复杂度，我正在使用递归树方法来查找它的时间复杂度。

对于它正在执行的第一个调用：Log（n） work

其次，它正在做：Log（n/2） + Log（n/2）

其次，它正在做：Log（n/4） + Log（n/4） + Log（n/4） + Log（n/4）

树的高度将是 log（base2） n。

因此，我将序列求和到 log（base2）n 项以获得时间复杂度：

对数（n） + 2 对数（n/2） + 4 对数（n/4） + 8*对数（n/8） +......直到 log（base2）n 项。

我得到的是 O（logn）时间复杂度，但正确的时间复杂度是：O（n）。

谁能告诉我怎么做？

算法递归数据结构

如果我们以“自下而上”的方式写这个，即从高度为 0 的叶子开始，会更容易。如果我们认为这棵树是一棵完美的二叉树，那么底层有（n+1）/2 个节点，高度为 0，下一层有（n+1）/4 个节点，高度为 1，...等。我们需要将节点的高度计算为其成本（即重复周期中的登录）。例如，如果我们只有一个节点，即叶子，则成本为 log1，即 0。如果我们将这些术语结合起来，我们会得到：

0（n+1）/2 + 1（n+1）/4 + 2（n+1）/8 + 3（n+1）/16 + ...

请注意，这些项现在的顺序与你的顺序相反，系数（0、1、2、3 等）是你在 log（）调用中得到的，而你的系数（2 的幂）在这里表示为 n 的分数。这就是自下而上而不是自上而下的效果。我相信也可以用自上而下的方法完成，但我发现这更容易。

所以一般来说，我们有（n+1）/2^h+1 个高度为 h 的节点，每个节点的成本（系数）为 h：

∑_{_h=0}^{^logn} h（n+1）/2^h+1

我们可以将（n+1）移出这个总和：

（n+1）∑_{_h=0}^{^logn} h/2^h+1

总和具有以下项：0/2 + 1/4 + 2/8 + 3/16 + ...我们可以把它写成几何级数之和，像这样：

1/4 + 1/8 + 1/16 + 1/32 + ...
      1/8 + 1/16 + 1/32 + ...
            1/16 + 1/32 + ...
                   ....

即使有无限项，每条线都是一个收敛的总和。他们每个人都会收敛到这一点：

1/2
1/4
1/8
1/16
...

这又是一个几何级数，它的总和收敛，......更改为 1。由于我们的项数量有限，我们可以确定总和小于 1。

所以。。。包括系数（n+1）在内的总表达式为 O（n）。

上一个：如何（有效地）通过Cypher在递归树中查找子路径（Graph vs Regex）

下一个：“Least Astonishment”和可变的默认参数

求 T（n） = 2T（n/2） + Logn 的时间复杂度

Finding time complexity of T(n) = 2T(n/2) + Logn

评论