含任意规模递归调用的算法运行时间分析——二叉搜索树OddNodeSetter

首先直接给结论：主定理确实无法直接用来证明这个算法的时间复杂度为O(n)，不过我们有更合适的方法来完成证明，下面详细解释：

为什么主定理不适用？ #

你提到的递推式T(n) = T(k) + T(n-k-1) + 1（其中1 ≤ k < n）不符合主定理的适用条件。主定理要求递推式必须是形如T(n) = aT(n/b) + f(n)的形式，其中a ≥ 1、b > 1是固定常数，递归调用的子问题规模必须是原问题的固定比例（比如n/2、n/3这类）。

但在你的算法中，k的取值完全取决于二叉搜索树的结构——可能是平衡树的k≈n/2，也可能是极端斜树的k=0（右斜树）或k=n-1（左斜树），子问题规模没有固定的比例关系，所以主定理的三个case都无法直接套用，自然没法用它覆盖所有情况的证明。

可行的证明方法 #

方法1：直接计数节点操作次数（最直观） #

先把你的算法代码贴出来方便分析：

OddNodeSetter(T, x):
    if (T.x == NIL):
        return 0;
    if (T.x.key mod 2 == 1):
        T.x.s = T.x.key + OddNodeSetter(T, x.left) + OddNodeSetter(T, x.right)
    else:
        T.x.s = OddNodeSetter(T, x.left) + OddNodeSetter(T, x.right)

观察代码逻辑就能发现：算法会遍历以x为根的子树中的每一个节点，且每个节点只会被访问一次：

• 每个节点的处理逻辑（判断是否为NIL、判断key奇偶、计算s值）都是O(1)的常数操作
• 不管树的结构是平衡、左斜、右斜还是任意形态，子树总共有n个节点

总操作次数就是n * O(1) = O(n)，这就直接证明了时间复杂度是O(n)。

方法2：替代法（数学归纳法） #

我们可以用数学归纳法来严格证明T(n) = O(n)：

1. 基例：
   • 当n=0（空树）时，T(0)=0，显然满足T(0) ≤ c*0（c为任意正整数）
   • 当n=1（只有根节点）时，T(1)=1，取c≥1，就有T(1) ≤ c*1，成立
2. 归纳假设：假设对于所有m < n，都有T(m) ≤ c*m
3. 归纳步骤：
   对于n个节点的情况，递推式为：

   T(n) = T(k) + T(n-k-1) + 1
   

   根据归纳假设代入：

   T(n) ≤ c*k + c*(n-k-1) + 1 = c*(n-1) + 1 = c*n - c + 1
   

   只要选择c ≥ 1，那么-c + 1 ≤ 0，因此：

   T(n) ≤ c*n
   

   满足归纳假设，因此T(n) = O(n)得证。

方法3：递归树法 #

把递归过程画成递归树：

• 每个递归调用对应树中的一个节点，每个节点的代价是1（对应常数操作）
• 递归树的总节点数恰好等于原二叉搜索树的节点数n（因为每个原树节点只会触发一次递归调用）
• 总代价就是所有节点的代价之和：n * 1 = O(n)

内容的提问来源于stack exchange，提问作者Basir Doost