6

我在寻找这个java方法的递归公式时有点卡住了

void printInorder(Node<T> v) {
    if(v != null) {
        printInorder(v.getLeft());
        System.out.println(v.getData());
        printInorder(v.getRight());
    }
}

一些标准：

  • 它是一个完整的二叉树（每个内部结有 2 个孩子，每个叶子都具有相同的深度）
  • 这棵树有 n 个结，复杂度为 O(n)

我必须找到与depth h树相关的递归公式n knots，作为额外的奖励，我需要从中推断出导致 O(n) 的显式公式。

现在，这就是我得到的：

d = depth of the tree
c = constant runtime for execution of the method itself
d = 1: T(n) = c
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c

我使用示例 d = 3 来为自己澄清事情，我很难进一步分解它。我的假设是否正确？

编辑：下一次尝试

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number
d = 1: T(d) = 1
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1)))

1: T(h)  = T(i = 0) + T(i = 1) + ... T(i = h-1)
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2)))
3: T(h)  = n + n + ... + n
4: T(h)  = (h-1)n
5: T(h)  = O(n)

因为树的每一层深度恰好包含 2^(h-1) 个节点，所以第 4 行中的 h 因子可​​以忽略，因为 n 与最终结果更相关。

4

2 回答 2

4

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

  • 0 级有 1 次操作。

  • 级别 1 有 2 个操作。

  • 2 级有 4 个操作。

  • 级别 k 有 2^k 次操作。

  • 树的深度是 lgn。

1+2+...+2^lgn=
2^0+2^1+2^2+...+2^lgn=
(2^(lgn + 1)-1)/(2-1)= 2*2^lgn=
2n。

于 2012-07-09T12:56:22.637 回答
2

这是使用平滑规则的替代方法（Levitin，算法的设计与分析，第 2 版，481-82），它允许将诸如此类的递归关系表示为指数。

平滑规则的演示。

任何一种方法——前向或后向替换——都适用于这个问题。我发现在许多情况下向后替换更容易消化。

于 2012-07-09T13:42:30.107 回答