给定算法的递归关系？

Question

int print4Subtree(struct Node *root) {
    if (root == NULL)
      return 0;
    int l =  print4Subtree(root->left);
    int r =   print4Subtree(root->right);
    if ((l + r + 1) == 4)
       printf("%d ", root->data);
    return (l + r + 1); }

这个 algorithm/code 找到二叉树中恰好有 4 个节点的子树的数量，它以自下而上的方式工作。我知道这段代码的时间复杂度是 O(n) ， space 复杂度是 O(log n) ，因为它使用递归。

What will be recurrence relation for the code ?

我试着画T(n) = 2T(n-1)+1 ，这显然是错误的！

Answer 1

只有在对树的结构比较了解的情况下，才能单独用n来谈递归关系，比如：

情况一：每个节点只有一个子节点意思 T(n) = T(0) + T(n-1) + k。
情况 2：任何级别的子树都是平衡的，因此 T(n) = 2 T((n -1)/2) + k。

这两种情况都会导致 O(n)，但这两种情况只是极少数可能的树 select。对于更通用的方法，您必须使用像 T(n) = T(a) + T(b)，其中 a 和b 是根据树的结构任意划分为子问题。您仍然可以使用 strong induction.

从这种公式中得出结果

以下是我将使用的确切公式和方法：
T(n) = nk + m_nc，其中 m_n ≤ n + 1。（注意：我使用 k 作为递归步骤的开销，使用 c 作为 base/null 步骤的开销）。

基本情况 (n=0):
对于空节点 T(0) = c 所以 T(n) = kn + m_nc ,
其中 m_n = 1 ≤ n+1 = 1.
电感阶跃(T(x) = xk + m_xc 对于所有 x < n):
大小为 n 的 sub_tree 有两个大小为 a 和 b 的子树（ a 或 b 可能是 0) 这样 n = a + b + 1.
T(n) = T(a) + T(b) + k = ak + m_ac + bk + m_bc + k = (a+b+1)k + (m_a+m_b)c = nk + m_nc ,
其中 m_n = m_a + m_b ≤ a + 1 + b + 1 = n + 1.

使用m_n的原因仅仅是为了使证明更顺利，因为空案例的确切数量是什么实际上是受树结构的影响（前例2是logn）。所以 T(n) 最多是 O(n) 因为 nk 项，并且不会比 O(n) 差，因为在 m_n 上有界c.

给定算法的递归关系？

Recurrence relation for given algorithm?

algorithm

recurrence

binary-tree

time-complexity